[CLASS 3]백준 5525번, 18870번, 1074번

5525번 : IOIOI

 

별로 어려워보이지 않는 문자열 문제이다. 무난하게 풀 수 있었다.

 

내 코드:

n,m,s = int(input()),int(input()),input()

ls = list(s)
# 직전에 뽑은 글자가 O였는지 확인
wasO = True
# 2회 이전에 I가 있었는지 확인
isOpen = False
tempCount = 0
realCount = 0
while ls:
    char = ls.pop()
    # I를 뽑았는데 직전이 O였다면
    if char == 'I' and wasO:
        wasO = False
        # 2회 이전에 I가 있었다면
        if isOpen:
            tempCount += 1
        else:
            isOpen = True
    # O를 뽑았는데 직전에 O가 아니었다면(I였다면)
    elif char == 'O' and not wasO:
        wasO = True
    # 규칙이 깨졌다면
    else:
        # 1회 이상의 Pn을 만들었다면
        if tempCount != 0:
            # n회 이상의 패턴이 연속되었다면
            if tempCount - n >= 0:
                realCount += tempCount - n + 1
            tempCount = 0
        # OO의 형태로 끝났다면
        if char == 'O':
            isOpen = False

if tempCount - n >= 0:
    realCount += tempCount - n + 1

print(realCount)

 

분기를 잘 나눠서 풀면 되긴 하는데... 생각보다 코드가 많이 지저분하다. 변수선언도 많고 뭔가 난잡한 느낌을 지울 수 없다.

 

맞은 분들의 깔끔한 코드를 찾아보니 정규 표현식을 사용한 것을 알 수 있다.

 

먼저 정규 표현식이란...

 

정규 표현식 또는 정규식은 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어이다. 정규 표현식은 많은 텍스트 편집기와 프로그래밍 언어에서 문자열의 검색과 치환을 위해 지원하고 있으며, 특히 펄과 Tcl은 언어 자체에 강력한 정규 표현식을 구현하고 있다.

위키백과

 

특정한 규칙을 찾는 문자열의 집합을 표현하기 위해 사용하는 것이라고 한다. 즉 이 문제에서는 IOI이라는 규칙이 연속되는 것을 찾기 위해 정규 표현식을 사용한다.

 

yoon_1318님의 코드:

import re

n = int(input())
_ = input()
string = input()

ioi = re.findall('I(?:OI)+', string)
count = 0

for k in ioi:
	c = len(k) // 2 - n + 1
	if c > 0:
		count += c

print(count)

 

먼저 파이썬에서 정규 표현식을 사용하기 위해 re를 import 해준다. 그리고 findall함수를 사용해준면 된다.

 

findall('패턴','문자열'[,'플래그]) 의 형태로 사용할 수 있으며, 문자열 내에서 해당하는 패턴을 모두 찾아서 리스트로 반환해주는 역할을 한다.

 

해당 코드의 ioi변수에는 IOI 패턴을 가지고 있는 연결된 모든 문자열이 담긴 리스트가 저장된다. 예) ['IOIOIOIOIOI','IOI']

 

이제 해당 리스트에서 문자열을 하나씩 뽑아서 길이를 2로 나눈 몫(O의 개수)에 n-1을 빼주었을 때 0을 넘는다면 해당 개수만큼 카운트 변수에 추가된다.

 

정규 표현식은 배울 때는 어렵지만 잘 써먹을줄만 안다면 어려운 문제도 날먹(?)가능 할 것 같다.

 

18870번 : 좌표 압축

 

솔직히 이게 왜 실버2 문제인지 모르겠다. 딕셔너리 자료형을 사용할 수 있다면 브론즈급으로 쉽게 풀 수 있다.

 

내 코드:

input()
# 입력 저장
li = list(map(int,input().split()))
# 정렬
srtLi = sorted(li)
# 해당 좌표의 압축값을 저장할 dict
di = {}

count = 0
di[srtLi[0]] = 0
for i in range(1,len(srtLi)):
    if srtLi[i] > srtLi[i-1]:
        count += 1

    di[srtLi[i]] = count

for num in li:
    print(di[num],end=' ')

 

다만 조금 주의할 점은, 정렬하고 압축한 뒤 출력할때 원래 입력받은 순서대로 출력하기 위해 기존 순서를 기억하고 있어야 한다는 점이다.

 

1074번 : Z

 

재귀로 풀기 위해 바로 코드를 작성하였다. 생긴게 너무 재귀함수를 쓰고 싶게 생겼기 때문이었다.

 

내 코드(시간 초과):

n,r,c = map(int,input().split())

# 탐색 회수
count = 0
def find(startR,startC,n):
    global count,r,c
    if n > 1:
        # 좌상단
        find(startR,startC,n//2)
        # 우상단
        find(startR,startC + n//2,n//2)
        # 좌하단
        find(startR + n//2,startC,n//2)
        # 우하단
        find(startR + n//2,startC + n//2,n//2)
    else:
        # r행 c열에 도달했을 경우
        if startR == r and startC == c:
            print(count)
            exit()
        count += 1

find(0,0,2**n)

 

그러나 바로 시간 초과를 먹었다... N이 최대 15이기 떄문에 count가 증가하는 연산을 엄청나게 많이 수행해야 해서 그런 것 같다.

 

그래서 이렇게 풀면 안되고, 어떤 사분면에 있는지에 따라 이전 서분면들의 수를 미리 더해서 값을 구해야 한다.

 

내 코드:

n, r, c = map(int, input().split())
num = 0
while n > 0:
	# 1/4크기의 정사각형 우측 하단 수
    temp = (2 ** (n-1))
    if n >= 1:
    	# 상단 우측 영역일 때
        if r < temp and c >= temp:
            num += temp ** 2
            c -= temp
        # 하단 좌측 영역일 때
        elif r >= temp and c < temp:
            num += (temp ** 2) * 2
            r -= temp
        # 하단 우측 영역일 때
        elif r >= temp and c >= temp:
            num += (temp ** 2) * 3
            r -= temp
            c -= temp
    
    n -= 1
print(num)

 

먼저 r과 c, 그리고n값을 받은 후, (2**n)X(2**n) 크기의 판에서 해당 점이 어느 영역에 있는지에 따라 분기하여 수를 더해주는 것이다.

 

예를 들어 n이 2라면 4X4 판에서 해당 점이 어디 있는지 판단한다. 만약 r과 c가 각각 (2,3) 이라면 하단 우측 영역에 해당하고, (1/4의 면적(4))X3을 num변수에 더해준뒤 r과 c를 2X2판으로 축소한다. 그러면 r과 c는 (0,1)이 되고, 이는 상단 우측 영역이다. 이때 1/4의 면적인 1을 더해주면 13이 나오게 된다.