연습 문제

다음 다섯 문제는 이 안내서를 위해 만든 문제입니다. 모두 기발한 요령보다 알맞은 자료구조를 고르는 것으로 풀립니다. 풀이를 읽기 전에 먼저 시도해 보세요.

문제 1: 브라우저 뒤로 가기와 앞으로 가기

작은 브라우저가 홈 페이지에서 시작합니다. 명령은 세 가지입니다. visit url 은 새 페이지를 열고, back 은 이전 페이지로 돌아가며, forward 는 back 을 되돌립니다. 새 페이지를 방문하면 앞으로 가기 기록은 지워집니다. 갈 곳이 없는 back 이나 forward 는 무시합니다. 모든 명령을 처리한 뒤의 현재 페이지를 돌려주세요.

풀이: 스택 두 개를 둡니다. back_stack 에는 현재 페이지 뒤쪽의 페이지를, forward_stack 에는 앞쪽의 페이지를 쌓습니다. 뒤로 가면 현재 페이지를 앞으로 가기 스택에 넣고, 새로 방문하면 앞으로 가기 스택을 비웁니다. 명령 하나가 O(1)입니다.

def browse(home, commands):
    current, back_stack, forward_stack = home, [], []
    for command in commands:
        if command.startswith("visit "):
            back_stack.append(current)
            current = command[6:]
            forward_stack.clear()
        elif command == "back" and back_stack:
            forward_stack.append(current)
            current = back_stack.pop()
        elif command == "forward" and forward_stack:
            back_stack.append(current)
            current = forward_stack.pop()
    return current

cmds = ["visit a", "visit b", "back", "back", "back", "forward", "visit c", "forward"]
print(browse("home", cmds))  # c

문제 2: 최근 1분 동안의 요청 수

서버가 요청 시각(초)을 감소하지 않는 순서로 기록합니다. 요청이 올 때마다 최근 60초 동안 들어온 요청 수를 현재 요청까지 포함해 알려 주세요(시각 t - 59 부터 t 까지).

풀이: 창 안에 남아 있는 시각을 큐에 담습니다. 새 시각이 오면 넣고, 맨 앞의 시각이 t - 59 보다 오래되었으면 앞에서 꺼냅니다. 시각 하나는 한 번 들어가고 한 번 나가므로 전체 비용은 O(n)입니다.

from collections import deque

def recent_counts(timestamps, window=60):
    inside = deque()
    result = []
    for t in timestamps:
        inside.append(t)
        while inside[0] <= t - window:
            inside.popleft()
        result.append(len(inside))
    return result

print(recent_counts([1, 10, 59, 60, 61, 125]))  # [1, 2, 3, 4, 4, 1]

t = 61 일 때 창은 2부터 61까지이므로 1초의 요청이 빠집니다. t = 125 일 때 창은 66부터 125까지라 현재 요청만 남습니다.

문제 3: 처음으로 다시 나온 주문 번호

주문 번호가 문자열 목록으로 들어옵니다. 두 번째로 나타난 위치가 가장 빠른 번호를 돌려주고, 모두 서로 다르면 None 을 돌려주세요. 답을 찾기 전까지 본 서로 다른 번호의 수도 함께 알려 주세요.

풀이: 이미 본 번호를 집합에 기억합니다. 왼쪽부터 훑다가 집합에 이미 있는 번호를 처음 만나면 그것이 답입니다. 검사와 삽입이 평균 O(1)이므로, 모든 쌍을 비교하는 O(n 제곱) 대신 O(n)에 끝납니다.

def first_repeat(order_ids):
    seen = set()
    for order_id in order_ids:
        if order_id in seen:
            return order_id, len(seen)
        seen.add(order_id)
    return None, len(seen)

print(first_repeat(["A7", "B2", "C9", "B2", "A7"]))  # ('B2', 3)
print(first_repeat(["X1", "X2"]))                    # (None, 2)

문제 4: 구간마다 가장 높은 기온

시간별 기온과 구간 크기 k 가 주어질 때, 연속한 k 시간마다 가장 높은 기온을 돌려주세요.

풀이: 덱에 인덱스를 담되, 그 기온이 내림차순이 되도록 유지합니다. 인덱스 i 를 넣기 전에 새 기온보다 낮거나 같은 기온의 인덱스를 뒤에서 모두 꺼냅니다. 그런 값은 다시는 최댓값이 될 수 없기 때문입니다. 구간 밖으로 밀려난 인덱스는 앞에서 꺼냅니다. 그러면 덱의 맨 앞이 언제나 현재 구간의 최댓값입니다. 인덱스마다 넣기와 빼기가 많아야 한 번씩이므로 O(nk) 대신 O(n)입니다.

from collections import deque

def window_max(temps, k):
    candidates = deque()   # 인덱스, 기온은 내림차순
    result = []
    for i, t in enumerate(temps):
        while candidates and temps[candidates[-1]] <= t:
            candidates.pop()
        candidates.append(i)
        if candidates[0] <= i - k:
            candidates.popleft()
        if i >= k - 1:
            result.append(temps[candidates[0]])
    return result

print(window_max([12, 15, 11, 9, 14, 18, 13, 10], 3))  # [15, 15, 14, 18, 18, 18]

문제 5: 같은 글자로 된 단어 묶기

서로 애너그램인 단어끼리 묶되, 묶음의 순서는 각 묶음의 첫 단어가 나온 순서를 따르세요.

풀이: 두 단어는 글자를 정렬한 결과가 같을 때 정확히 애너그램이므로, 정렬한 글자를 딕셔너리 키로 씁니다. Python 딕셔너리는 넣은 순서를 지키므로 요구한 묶음 순서가 저절로 나옵니다.

def group_anagrams(words):
    groups = {}
    for word in words:
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

print(group_anagrams(["listen", "stone", "silent", "notes", "enlist", "tones", "cat"]))
# [['listen', 'silent', 'enlist'], ['stone', 'notes', 'tones'], ['cat']]

정리

되돌리기와 다시 하기는 스택, 시간 창은 큐, "이미 본 적 있나?"는 집합, "키별로 묶거나 세기"는 딕셔너리가 어울립니다. 이중 반복문이 모든 쌍을 비교하고 있다면, 안쪽 반복이 매번 다시 계산하는 것을 해시 테이블이나 단조 덱이 기억해 줄 수 없는지 생각해 봅니다.