정글사관학교 18일차 TIL: MOO 게임(#5904), 문자열 폭발(#9935), 스카이라인(#1933)

오늘 2주차 시험에서는 1시간 반 동안 겨우 1문제 풀었다. 공부할 때도 엄청 빡셌지만 어찌어찌 익혔다는 느낌이 없잖았는데 결과가 이러니 참담하다 싶지만..! 그래도 한 문제 푼 게 어딘가! 아자자! 잘했다! 한 걸음씩 가는 거지!

 

1. MOO 게임(#5904)

문제 링크는 여기.

 

도저히 어떻게 접근해야 좋을지 몰라, 맨 처음에는 아예 수열 자체를 구해버리려고 했다. 10^9를 넘는 가장 작은 수열을 뽑으려고 해봤는데 대략 n이 10~20 사이에서 될 것 같더라! 문제는 n=12를 넣을 때부터 연산이 뻗는다는 느낌이 들기 시작하더니 n=15쯤 가니 허송세월하고 있더라. 이렇게는 도저히 못 풀겠다 확신만 하고 끝남..^_^

 

지훈이의 풀이를 공부한 내용을 정리하자면, 이 문제는 재귀로 이루어진 점화식을 길이를 구하는 코드로 변환한 뒤, 분할정복을 이용한다. 재귀는 점화식으로 표현하는 것과 동치인 개념이다. 따라서 먼저 수식으로 문제를 표현한 다음, 이를 코드로 짜는 식으로 진행했다. (엄청 간단하게 적었지만 나도 잘 모르겠다..)

 

문제에서는 어느 정도 힌트를 줬는데, "S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다." 라고 했다. 즉, 점화식은

 

s(k) = s(k-1) + "m" + (k+2)*"o" + s(k-1)

 

이다. 이를 s(k)의 문자 길이에 관한 식으로 바꾸면

 

len(s(k)) = len(s(k-1)) + k+3 + len(s(k-1)) = 2* len(s(k-1)) + k + 3

 

이다.

이를 문제에 적용해본다.

 

문제에서 s(k)에 대해 leng = len(s(k))라고 하자.

s(0)의 경우 leng = 3 ("moo")이다.

 

이 leng(s(k)의 문자열 길이)이 문제에서 구하려는 N번째 문자가 위치한 길이 N보다 작다면, 그보다 크거나 같아질 때까지 계속해서 leng의 길이를 늘린다. 즉, 점화식에서 k값을 계속해서 +1 씩 해주면 leng의 길이가 늘어나고 어느 순간 N보다 크거나 같아지는 순간에 이를 멈춘다.

 

from sys import stdin
n = int(stdin.readline())

k = 0
leng = 3 # S(0)에서 moo의 길이

while leng < n: # leng은 s(k)의 길이, n은 문제에서 구하려는 문자의 위치
    k += 1
    leng = 2*leng + (k+3)

 

다음에는 분할정복에 관한 함수 DAC(x, l, n)을 짠다. 여기서 x = k의 차수, l = s(k)의 길이, n: 우리가 찾고자 하는 글자의 위치다.

 

분할정복이니 먼저 종료 조건부터 선언한다. 만약 x, 그러니까 k값이 0이면 (=s(0)에 해당) 문자열은 "moo"다. 당연히 n의 범위는 1~3.

n이 1이라면 "m"을, 그 외는 "o"를 출력한다.

 

x가 0이 아니라면 k값을 1로 낮추고 leng(k) 역시 leng(k-1)로 내린다. 이는 len(s(k)) =  2* len(s(k-1)) + k + 3로 바꾸는 작업이다.  

 

s(k) = s(k-1) + "m" + (k+2)*"o" + s(k-1)이라고 했으니, 경우의 수는 세 가지이다.

 

위치 N이

1) 앞의 s(k-1) 쪽에 있을 경우 => 분할정복: DAC(x, l, n)

2) "m" + (k+2)*"o" 사이에 있을 경우

 2-1) 'm'일 때 (n == l+1)

 2-2)'o'일 때(else)

3) 뒤의 s(k-1) 쪽에 있을 경우 (n > l + x + 4)

 

이를 비교하는 코드를 짜면 구할 수 있다.

 

def DAC(x, l, n):
    if x == 0:
        if n == 1:
            return 'm' #
        else:
            return 'o'

    l = (l-3-x) // 2
    x -= 1

    if n <= l:
        return DAC(x, l, n)
    elif n == l + 1:
        return 'm'

    elif n > l + x + 4: #
        return DAC(x, l, n-l-x-4)
    else:
        return 'o'

 

전체 코드는 여기. n을 아래에서는 m이라고 적었는데 구별하려고 다르게 적었음.

 

from sys import stdin
m = int(stdin.readline())


k = 0
leng = 3 # S(0)에서 moo의 길이

while leng < m: 
    k += 1
    leng = 2*leng + (k+3) 

def DAC(x, l, n):
    if x == 0:
        if n == 1:
            return 'm' #
        else:
            return 'o'

    l = (l-3-x) // 2
    x -= 1

    if n <= l:
        return DAC(x, l, n)
    elif n == l + 1:
        return 'm'

    elif n > l + x + 4: #
        return DAC(x, l, n-l-x-4)
    else:
        return 'o'
print(DAC(k, leng, m))

 

2. 문자열 폭발(#9935)

시험에서 풀었던 유일한 문제. 그마저도 막판에 겨우겨우 풀었다. 코드 자체는 간단한데 뭔가 복잡하게 구현해야 할 것만 같은 느낌에 처음에는 손도 못댔다. 하지만 스택을 쓴다고 생각한 다음, 한 글자씩 스택에 넣는다고 생각해보면 그 글자 중 하나의 트리거만 캐치하면 기능을 발동하도록 짜면 쉽게 풀 수 있다.

 

논리는 이렇다.

 

1. 빈 리스트를 하나 만든다.

2. 주어진 문자열을 받아 for문을 돈다. 문자열에 대해 for문을 돌면 한 글자씩 i로 받아 다음 스텝으로 넘어간다.

3. 위에서 말했던 트리거는 폭탄 문자열의 마지막 단어를 말한다. 폭탄 문자열의 다른 단어는 생각할 필요가 없다. 우리는 폭탄 문자열이 무엇인지 그 글자도 알고 그 길이도 안다.

4. 마지막 글자가 들어왔을 때만 감지하도록 하고, 감지되고 나면 일단 그 마지막 글자를 스택에 먼저 삽입한다(append).

5. 이때, 지금까지 쌓여있던 스택을 거꾸로 폭탄 문자열 길이만큼 스캔한다. 그래서 똑같은 글자가 있다고 하면 , 그만큼 길이를 지우면 된다.

6. for문을 다 돌고 나서 stack의 길이가 0이면 "FRULA"를 출력하도록 하고 그렇지 않으면 stack을 문자열로 변환해 출력한다.

 

폭탄 문자열의 마지막 글자를 기준으로 그 전까지 폭탄 길이만큼만 스캔하면 된다는 개념이 핵심인데, 이는 어제 정리했던 철로 문제의 풀이 논리와 엇비슷한 면이 있다. (오른쪽 끝에서부터 왼쪽으로 스캔한다는 점..? 이렇게 적고 보니 크게 공통점이 있는 것 같지는 않은데 문제 풀 때 철로가 떠올랐던 건 왜일까) TIL 열심히 정리한 보람이 있었다!

 

 코드 전문은 아래.

from sys import stdin

str = stdin.readline().strip()
bomb = stdin.readline().strip()

# 우리는 bomb의 문자열 길이를 안다 =>
stack = []
for i in str:
    if i != bomb[-1]:
        stack.append(i)
    else: # 끝글자와 같으면
        stack.append(i) # 일단 삽입하고
        if "".join(stack[-len(bomb):]) == bomb: # bomb랑 같은 애 나오면 지워
            del stack[-len(bomb):]

if len(stack) == 0:
    print("FRULA")
else:
    print("".join(stack))

 

3. 스카이라인(#1933)

얘는 진짜 손도 못대겠던 문제. 정리를 하기는 했는데..다시 풀라고 하면 풀 수 있을지 모르겠다. 일단 정리해본다.

 

이 문제는 힙큐에다가 그때그때 가장 높은 높이를 저장해놓고서 푸는 문제다. 내용이 기니 끊어가면서 설명한다.

 

먼저 문제에서 주어진 조건을 받아오자. 건물의 개수를 n이라고 하자. 그리고 우리는, 건물의 왼쪽과 오른쪽을 분리할 것이다. 정확히는, 건물의 왼쪽 위 끝점과 오른쪽 아래끝점으로 분리할 것이다. 왜 이렇게 하냐? 결국 우리가 얻고 싶은 건 스카이라인, 즉 왼쪽 위 끝점부터 시작해서 가장 높은 선만 주루룩 연결한 애들을 구하는 게 목적이다. 최고 높이를 저장해놓고 있다가 끊어지는 지점에서 새로운 높이로 갈아타야 하는데, 이 끊어지는 지점은 결국 왼쪽 위 끝점 혹은 아래쪽 끝점이므로 이를 분리해서 생각하자는 것이다. 뒤쪽에 가면 이 개념이 좀 더 쉽게 와닿을 것이다. (이 아이디어를 떠올리는 게 이 문제에서 가장 어려운듯..)

 

여기서 우리는 각 지점을 리스트에 저장할텐데, 우리가 구하고 싶은 건 최고 높이이므로 힙큐에 저장할 때 높이에 -를 붙여서 저장한다. (이에 대해 자세한 내용은 여기 "heapq로 최대 힙 만들기" 링크 참조)

 

여기까지를 코드로 짜면 아래와 같다.

 

from sys import stdin
import heapq

n = int(stdin.readline()) # 건물 개수

events = [] # 건물 지점 저장하는 곳
for i in range(n):
    L, H, R = map(int, stdin.readline().split())
    events.append([L, -H, R]) # 시작지점: 건물의 왼쪽 위 끝점을 넣는다.
    events.append([R, 0, 0]) # 건물이 끝나는 지점: 오른쪽 아래 점을 따로 하나 더 저장 => 얘는 건물에 해당하지 X: 높이가 0이니.

events.sort()
print(events)

 

다음은 정답을 저장할 리스트와 최고 높이를 저장할 힙큐를 만든다. 정답을 출력할 리스트의 형식을 생각하는 것도 중요한데, 예제의 정답을 보면 (왼쪽 끝 위치, 높이, 왼쪽 끝 위치, 높이, ...)이런 식으로 문자열이 나열되므로 정답 리스트에 들어갈 형식 역시 [[x, height]]으로 맞춘다.

 

힙큐에도 마찬가지인데, heapq 형식이니 (-height, x)형식으로 값이 들어간다. 이때, x는 해당 높이를 갖는 x좌표를 뜻한다.

이 힙큐는 가장 높은 높이 값이 오른쪽 아래끝점에 도달할 때까지 유지된다(중간에 다른 빌딩과 겹치지 않는 이상).

 

이 정답 리스트와 힙큐는 항상 최소로 하나의 값을 조회할 수 있어야 하기 때문에 더미로 값을 넣어준다.

 

# res: result로 정의 => [x, height] => y값으로 height! 위에서 height를 -값을 붙여서 저장했으니 여기서는 다시 -붙여서 바꿔줘야!
# live: heapq, (-height, x) 형식으로 => live에는 가장 높이가 큰 건물인 애를 가져오는! 방식으로 해줄 것. 그래서 빌딩 높이를 -로 저장! heapq는 최소 힙이니. 튜플 값에는 높이와 그 높이의 x좌표 값이 들어간다.

res = [[0, 0]] # 최소한 하나의 값을 출력해야 하니 더미값을 넣어준다!
live = [(0, float('inf'))] # 항상 최소로 하나의 값을 조회할 수 있어야 하기 떄문에! => 높이는 0이고 x좌표 위치는 무한대인 더미를 하나 넣어준다. 이 더미는 가장 오른쪽에 위치하겠지.

# live는 힙큐 => 높이가 가장 높은 애로 right까지 유지된다. right의 기간이 만료되면 heapq엣 값을 뺀다.

 

이제 진짜 마지막..위에서 건물의 양 끝점을 저장해둔 event 리스트에 대해 for문을 돌며 각 점의 x좌표, 높이, 오른쪽 끝값을 가져온다.

 

이때 총 세 스텝으로 나뉘는데,

 

Step 1: 이미 지나간 좌표값을 제거한다. 힙큐에 저장된 높이 중 가장 높은 높이의 x좌표(그러니까 가장 높은 건물 왼쪽 끝점 x값)가 새로 들어온 점의 x좌표보다 작다면, 즉 건물이 겹친다면 (아래 이미지에서 빨간색 건물 오른쪽까지 오면 초록색 왼쪽 끝 지점은 필요가 없고, 초록색 오른쪽 끝지점까지 오면 파란색 오른쪽 끝점은 필요가 없는 식) heapq에서 이제까지 가장 높았던 점을 pop한다.

 

for pos, negH, R in events: # 위에서 L, -H, R이라고 저장한 애들의 이름을 각각 pos = L, negH = -H, R = R => 모든 건물에 대해 돌려본다! 가 아니라 LR 구분 없이 전부 포지션! 그러려고 위에서 [R, 0, 0]을 이벤트에 추가한 것!
    # step1: 이미 지나간 좌표값 => 제거하는 작업
    print("현재 live: ", live)
    while live[0][1] <= pos: # 현재 살아있는 포지션 중에서 가장 높은 빌딩의 포지션이 지금 배치하려는 포지션의 위치보다 더 작은 곳에 있다면
        print(live[0][1], "이", pos, "보다 작아서 지나간 좌표를 제거합니다.")
        heapq.heappop(live) # live라는 heapq 데이터에서 가장 작은(여기서는 -를 붙였으니 높이가 가장 큰!)애를 뽑아온다.

 

Step 2: 이제 건물을 하나씩 heap에 저장한다. 이때 heap에 저장하는 애들은 오른쪽 끝점은 제하고 높이가 있는 왼쪽 위끝 점만 저장한다.

    if negH:
        heapq.heappush(live, (negH, R)) # 힙에는 해당 점의 높이와 포지션(x좌표)을 넣는다. => 끝나는 지점인 R을 기준으로! 한 건물의 높이는 R에서 끝남!
        print("힙에 저장합니다:", (negH, R))
        # 시작하는 지점에서 힙큐에다가 높이랑 끝나는 지점을 명시!해줘서 높이가 유지되는 걸 명시해줘야.

Step 3: 마지막 높이가 가장 높은 높이랑 다른 경우에만 결과 리스트에 넣어준다. 같으면 그대로 쭉 연결되니까.

 

    if res[-1][1] != -live[0][0]: # res에는 height이 양수로 저장되어 있고 live(heap)에는 음수로 저장되어 있으니 -를 붙인다! 가장 큰 height만 활용.
        print("res의 끝값", res[-1], "live의 최대 높이", -live[0][0])
        res.append(f'{pos} {-live[0][0]} ')

 마지막으로 결과값을 출력하는데, 앞에서 더미 값을 넣었으니 그걸 제하고 출력한다.

 

print("".join(res[1:]))

 

코드 전문은 아래와 같다.

 

from sys import stdin
import heapq

n = int(stdin.readline()) # 건물 개수

events = []
for i in range(n):
    L, H, R = map(int, stdin.readline().split())
    events.append([L, -H, R]) # 시작지점: 건물의 왼쪽 위 끝점을 넣는다.
    events.append([R, 0, 0]) # 건물이 끝나는 지점: 오른쪽 아래 점을 따로 하나 더 저장 => 얘는 건물에 해당하지 X: 높이가 0이니.

events.sort()
print(events)

res = [[0, 0]] # 최소한 하나의 값을 출력해야 하니 더미값을 넣어준다!
live = [(0, float('inf'))] # 항상 최소로 하나의 값을 조회할 수 있어야 하기 떄문에! => 높이는 0이고 x좌표 위치는 무한대인 더미를 하나 넣어준다. 이 더미는 가장 오른쪽에 위치하겠지.


for pos, negH, R in events: # 위에서 L, -H, R이라고 저장한 애들의 이름을 각각 pos = L, negH = -H, R = R => 모든 건물에 대해 돌려본다! 가 아니라 LR 구분 없이 전부 포지션! 그러려고 위에서 [R, 0, 0]을 이벤트에 추가한 것!
    # step1: 이미 지나간 좌표값 => 제거하는 작업
    while live[0][1] <= pos: # 현재 살아있는 포지션 중에서 가장 높은 빌딩의 포지션이 지금 배치하려는 포지션의 위치보다 더 작은 곳에 있다면
        print(live[0][1], "이", pos, "보다 작아서 지나간 좌표를 제거합니다.")
        heapq.heappop(live) # live라는 heapq 데이터에서 가장 작은(여기서는 -를 붙였으니 높이가 가장 큰!)애를 뽑아온다.
    # step2. 건물을 하나씩 heap에 저장! (negH !=0: 높이가 0이 아니면 건물에 해당하니) => live에 넣어준다
    if negH:
        heapq.heappush(live, (negH, R)) # 힙에는 해당 점의 높이와 포지션(x좌표)을 넣는다. => 끝나는 지점인 R을 기준으로! 한 건물의 높이는 R에서 끝남!
         
    # step3. 마지막 높이가 highest height과 다른 경우에만 결과값에 넣어준다 (res에다가)
    if res[-1][1] != -live[0][0]: # res에는 height이 양수로 저장되어 있고 live(heap)에는 음수로 저장되어 있으니 -를 붙인다! 가장 큰 height만 활용.
        res.append(f'{pos} {-live[0][0]} ')
print("".join(res[1:]))

*추가: heapq를 쓰지 않고 bisect를 이용해 푼 풀이도 함께 링크로 소개! (엄청 간단하더라..)