코딩 테스트 합격자 되기 | 06 스택 학습 기록
이번에는 스택의 개념과 정의부터 문제 08~14까지 한 번에 정리했다. 첨부 PDF의 파일명은 ‘올바른 괄호’였지만, 실제 대화 내용은 문제 13 크레인 인형뽑기 게임과 문제 14 표 편집이었다. 문제 13·14는 내가 작성한 코드와 질문을 중심으로, 문제 08~12는 책의 스택 학습 범위에 맞춰 기본 풀이와 다른 풀이를 함께 정리했다.
06 스택: 이번 글의 범위
| 구분 | 내용 | 이번 글의 반영 |
|---|---|---|
| 06-1, 06-2 | 스택 개념과 정의 | LIFO/FILO, push, pop, top, 파이썬 리스트 |
| 06-3 | 문제 08, 09 | 괄호 짝 맞추기, 10진수를 2진수로 변환하기 |
| 06-4 | 문제 10~14 | 괄호 회전, 짝지어 제거, 주식 가격, 크레인, 표 편집 |
1. 스택의 개념과 정의
스택은 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 자료구조다. 접시를 차곡차곡 쌓아 올린 뒤 맨 위 접시부터 꺼내는 모습과 같다. 이 동작을 LIFO(Last In, First Out) 또는 FILO(First In, Last Out)라고 부른다. 표현은 다르지만 같은 구조를 말한다.
push: 스택 맨 위에 데이터를 넣는 동작
pop: 스택 맨 위 데이터를 꺼내는 동작
top: 꺼내지 않고 맨 위 데이터를 확인하는 위치. 파이썬 리스트에서는 stack[-1]으로 본다.
파이썬에서는 별도의 Stack 클래스를 만들지 않아도 리스트를 그대로 스택처럼 쓸 수 있다. append()가 push, pop()이 pop 역할을 한다. 두 메서드는 리스트의 끝에서 동작하므로 보통 O(1)이다.
stack = []
stack.append("A") # push
stack.append("B")
top = stack[-1] # "B"를 확인하지만 꺼내지는 않음
last = stack.pop() # "B"를 꺼냄
if not stack:
print("스택이 비어 있습니다.")stack.pop(-1)과 stack.pop()은 마지막 원소를 꺼낸다는 점에서 같다. 인자를 생략한 pop()이 스택의 의도를 더 자연스럽게 보여 준다. 반대로 빈 리스트에서 pop()을 호출하면 IndexError가 나므로, 필요하면 먼저 if stack: 또는 if not stack:으로 확인한다.
2. 문제 08 - 괄호 짝 맞추기
소괄호 문자열이 정상적으로 열리고 닫혔는지 판별하는 문제다. 닫는 괄호를 만났을 때 짝이 되는 대상은 가장 최근에 나온 여는 괄호다. ‘가장 최근’이라는 말이 나오면 스택을 떠올릴 수 있다.
기본 풀이: 여는 괄호를 스택에 저장
def solution(s):
stack = []
for char in s:
if char == "(":
stack.append(char)
else:
if not stack:
return False
stack.pop()
return not stack여는 괄호는 스택에 넣는다. 닫는 괄호를 만났는데 스택이 비어 있으면, 닫을 대상보다 닫는 괄호가 먼저 나온 것이므로 바로 False다. 마지막까지 처리한 뒤 스택이 비어 있어야 남은 여는 괄호가 없으므로 True다.
다른 풀이: 소괄호 하나만 있을 때는 개수로도 가능
def solution(s):
balance = 0
for char in s:
if char == "(":
balance += 1
else:
balance -= 1
if balance < 0:
return False
return balance == 0balance는 아직 닫히지 않은 여는 괄호 수다. 다만 이 방식은 괄호 종류가 소괄호 하나일 때만 안전하다. ([)]처럼 여러 종류의 괄호 순서까지 확인해야 하면 개수만으로는 부족하므로 스택을 사용해야 한다.
검산: "()()"는 True, "())("는 중간에 balance가 음수가 되므로 False, "(()"는 마지막 balance가 1이므로 False다.
3. 문제 09 - 10진수를 2진수로 변환하기
10진수를 2로 나눈 나머지를 차례대로 기록하면 나머지는 뒤에서부터 읽어야 이진수가 된다. 예를 들어 13은 나머지가 1, 0, 1, 1 순서로 나오고, 역순으로 읽으면 1101이다. 나중에 기록한 값을 먼저 꺼내야 하므로 스택이 자연스럽다.
기본 풀이: 나머지를 push한 뒤 pop하기
def solution(decimal):
stack = []
while decimal > 0:
stack.append(str(decimal % 2))
decimal //= 2
result = []
while stack:
result.append(stack.pop())
return "".join(result)decimal % 2는 나머지, decimal //= 2는 소수점 아래를 버린 몫으로 갱신하는 연산이다. 나머지를 문자열로 바꿔 넣어 두면 마지막의 "".join(result)로 바로 이어 붙일 수 있다.
다른 풀이 1: 리스트를 뒤집어 한 번에 붙이기
def solution(decimal):
digits = []
while decimal > 0:
digits.append(str(decimal % 2))
decimal //= 2
return "".join(reversed(digits))나머지를 쌓는 리스트 자체를 스택처럼 보되, pop으로 하나씩 꺼내지 않고 reversed()로 역순 순회하는 방법이다.
다른 풀이 2: 파이썬 내장 함수
def solution(decimal):
return bin(decimal)[2:]bin(13)은 "0b1101"을 반환한다. 앞의 0b를 제외하려고 슬라이싱 [2:]을 쓴다. 코딩 테스트에서 변환 과정을 직접 구현하라는 의도라면 기본 풀이를 먼저 이해한 뒤 이 방법을 쓰는 편이 좋다.
4. 문제 10 - 괄호 회전하기
문자열을 왼쪽으로 한 칸씩 회전하며, 각 회전 결과가 올바른 괄호 문자열인지 세는 문제다. 괄호 종류가 (), [], {} 세 가지이므로 ‘스택이 비었는지’뿐 아니라 맨 위 여는 괄호의 종류도 확인해야 한다.
기본 풀이: 회전 문자열을 만든 뒤 검사하기
def is_valid(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for char in text:
if char in "([{":
stack.append(char)
else:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return not stack
def solution(s):
answer = 0
for i in range(len(s)):
rotated = s[i:] + s[:i]
if is_valid(rotated):
answer += 1
return answerpairs는 닫는 괄호가 왔을 때 스택 맨 위에 있어야 하는 여는 괄호를 저장한 딕셔너리다. 예를 들어 현재 문자가 ]이면 스택 맨 위가 [여야 한다. 한 회전마다 새 문자열을 만드는 방식은 읽기 쉽다.
다른 풀이: 문자열을 실제로 만들지 않고 인덱스로 회전하기
def solution(s):
pairs = {")": "(", "]": "[", "}": "{"}
answer = 0
n = len(s)
for start in range(n):
stack = []
for offset in range(n):
char = s[(start + offset) % n]
if char in "([{":
stack.append(char)
elif not stack or stack[-1] != pairs[char]:
break
else:
stack.pop()
else:
if not stack:
answer += 1
return answer(start + offset) % n은 인덱스가 문자열 끝을 넘으면 다시 0으로 돌아가게 한다. 예를 들어 길이 6에서 start가 4이고 offset이 3이면 7 % 6이 1이므로 1번 인덱스를 읽는다.
여기서 for ... else의 else는 조건문 if의 else가 아니다. 반복문이 break 없이 끝까지 실행되었을 때만 실행된다. 중간에 잘못된 괄호를 만나 break했다면 else는 실행되지 않는다.
실수 방지: 닫는 괄호를 만났을 때 스택이 비었는지 먼저 확인해야 한다. 또 모든 문자를 읽었다고 바로 정답이 되는 것은 아니다. 스택에 여는 괄호가 남아 있으면 아직 짝이 맞지 않는다.
5. 문제 11 - 짝지어 제거하기
같은 알파벳 두 개가 붙으면 제거하고, 제거 뒤에 새로 붙은 두 글자도 다시 제거한다. 문자열 길이가 최대 1,000,000이므로 문자열을 계속 잘라 붙이는 방식은 느릴 수 있다. 현재 문자와 바로 직전의 살아 있는 문자만 비교하면 되므로 스택으로 O(N)에 처리한다.
기본 풀이: 새 문자를 넣기 전에 맨 위와 비교
def solution(s):
stack = []
for char in s:
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return 1 if not stack else 0예를 들어 "baabaa"를 읽으면 b를 넣고, a를 넣고, 다음 a에서 맨 위 a와 같으므로 pop한다. 그러면 b와 b가 다시 이웃이 되어 다음 b에서 pop할 수 있다. 실제 문자열을 이어 붙이지 않아도 스택에 남은 값이 현재 살아 있는 문자열 역할을 한다.
다른 풀이: 남은 문자열을 명시적으로 만들기
def solution(s):
remained = []
for char in s:
if remained and remained[-1] == char:
remained.pop()
else:
remained.append(char)
return int(len(remained) == 0)알고리즘은 같지만 변수 이름을 remained로 두면 ‘제거되고 남은 문자열’이라는 역할이 더 잘 보일 수 있다. int(True)는 1, int(False)는 0이다. 초보자라면 첫 번째의 명시적인 return이 더 읽기 쉽다.
6. 문제 12 - 주식 가격
각 시점의 가격이 처음으로 떨어질 때까지 몇 초가 걸리는지 구한다. 예시 [1, 2, 3, 2, 3]의 답은 [4, 3, 1, 1, 0]이다. 가격이 바로 다음 초에 떨어져도 그 한 초는 기간에 포함된다는 점이 핵심이다.
처음 풀이로 확인하기: 이중 반복문
def solution(prices):
answer = []
for i in range(len(prices)):
seconds = 0
for j in range(i + 1, len(prices)):
seconds += 1
if prices[j] < prices[i]:
break
answer.append(seconds)
return answer각 가격 뒤를 직접 탐색하므로 논리는 가장 쉽다. 다만 가격 수가 100,000개이고 계속 오르는 경우에는 뒤쪽을 반복해서 살피므로 O(N²)이 되어 효율성 테스트를 통과하기 어렵다. 답을 먼저 확인하기 위한 풀이로는 좋지만, 최종 풀이는 개선이 필요하다.
최종 풀이: 아직 기간이 확정되지 않은 인덱스를 스택에 저장
def solution(prices):
answer = [0] * len(prices)
stack = []
for i, price in enumerate(prices):
while stack and prices[stack[-1]] > price:
previous = stack.pop()
answer[previous] = i - previous
stack.append(i)
while stack:
previous = stack.pop()
answer[previous] = len(prices) - 1 - previous
return answer여기서 스택에는 가격 자체가 아니라 인덱스를 넣는다. 구해야 하는 것은 가격이 아니라 기간이므로, 나중에 i - previous를 계산하려면 시작 위치가 필요하기 때문이다.
새 가격이 들어왔을 때 스택 맨 위 가격보다 작으면, 맨 위 가격은 바로 지금 처음 떨어진 것이다. 따라서 pop하며 기간을 확정한다. 끝까지 가격이 떨어지지 않은 인덱스는 마지막 시점까지의 기간을 계산한다. 각 인덱스는 한 번 push되고 최대 한 번 pop되므로 O(N)이다.
7. 문제 13 - 크레인 인형뽑기 게임
문제에서 받은 board의 각 열은 위쪽 인형만 뽑을 수 있으므로 하나의 스택처럼 볼 수 있다. 크레인이 뽑은 인형을 담는 바구니도 마지막에 넣은 인형부터 비교하므로 스택이다. PDF에는 내가 작성한 아래 풀이와 pop(-1) 질문이 있었다.
내 풀이: board를 위에서부터 바로 탐색
def solution(board, moves):
stacklist = []
answer = 0
for i in moves:
for j in range(len(board)):
if board[j][i - 1] != 0:
stacklist.append(board[j][i - 1])
board[j][i - 1] = 0
if len(stacklist) > 1:
if stacklist[-1] == stacklist[-2]:
stacklist.pop(-1)
stacklist.pop(-1)
answer += 2
break
return answeri는 문제에서 1부터 시작하는 열 번호다. 파이썬의 열 인덱스는 0부터 시작하므로 i - 1을 사용한 것이 맞다. 안쪽 반복문은 선택한 열을 맨 위 행부터 내려가며 처음 만나는 0이 아닌 인형을 찾는다.
인형을 바구니에 넣자마자 원래 board 위치를 0으로 바꿔야 다음 move에서 같은 인형을 다시 뽑지 않는다. 또 인형 하나를 찾은 뒤에는 그 열의 더 아래 칸을 보면 안 되므로 break가 필요하다.
바구니에 넣은 뒤 마지막 두 인형을 비교하는 방식도 맞다. 다만 stacklist[-2]를 읽기 전에는 인형이 두 개 이상 있는지 확인해야 한다. 그래서 len(stacklist) > 1이 안전장치 역할을 한다.
내 풀이를 조금 다듬은 버전
def solution(board, moves):
basket = []
answer = 0
for move in moves:
column = move - 1
for row in range(len(board)):
doll = board[row][column]
if doll == 0:
continue
board[row][column] = 0
if basket and basket[-1] == doll:
basket.pop()
answer += 2
else:
basket.append(doll)
break
return answer이 버전은 새 인형을 넣기 전에 basket 맨 위와 비교한다. 같은 인형이면 기존 맨 위만 pop하면 되고 새 인형은 애초에 넣지 않는다. if basket은 basket이 비어 있지 않은지 확인하는 조건이다. pop(-1) 대신 pop()을 써도 마지막 원소가 빠진다.
다른 풀이: board의 각 열을 미리 스택으로 바꾸기
def solution(board, moves):
lanes = [[] for _ in range(len(board[0]))]
for row in range(len(board) - 1, -1, -1):
for column in range(len(board[0])):
doll = board[row][column]
if doll != 0:
lanes[column].append(doll)
basket = []
answer = 0
for move in moves:
lane = lanes[move - 1]
if not lane:
continue
doll = lane.pop()
if basket and basket[-1] == doll:
basket.pop()
answer += 2
else:
basket.append(doll)
return answer각 열은 서로 독립적이므로 lanes에 열별 스택을 만든다. board의 아래 행부터 위로 읽어야 위쪽 인형이 리스트의 마지막에 놓이고, 이후 pop()으로 바로 뽑을 수 있다. 0은 빈칸이므로 스택에 넣지 않는다. 내 풀이처럼 매 move마다 위에서 찾는 방식과, 먼저 열별 스택으로 바꾸는 방식 모두 문제 제한에서는 가능하다.
8. 문제 14 - 표 편집
U X는 X칸 위로, D X는 X칸 아래로 이동한다. C는 현재 행을 삭제하고 아래 행을 선택하되 마지막 행을 지웠다면 위 행을 선택한다. Z는 가장 최근에 삭제한 행을 복구하며 현재 커서는 움직이지 않는다. 최종적으로 원래 행 순서에 맞춰 살아 있는 행은 O, 삭제된 행은 X로 표시한다.
n이 최대 1,000,000이다. 일반 리스트에서 중간 행을 pop(k)하거나 insert(k, value)하면 뒤 원소를 전부 옮겨야 한다. 그래서 실제 행을 지우거나 끼워 넣는 대신, 각 행의 바로 위와 아래 행 번호만 바꾸는 이중 연결 리스트 방식으로 해결한다.
먼저 이해할 세 변수: up, down, deleted
up[i]는 i번 행 바로 위의 살아 있는 행 번호, down[i]는 바로 아래의 살아 있는 행 번호다. deleted는 삭제한 행 번호를 담는 스택이다. Z는 가장 최근 C를 되돌리므로 append와 pop이 정확히 맞는다.
삭제 C: 삭제할 행의 위와 아래를 직접 연결한다.
복구 Z: 삭제된 행에 남아 있는 원래 위·아래 정보를 이용해 양옆을 다시 연결한다.
중요: 삭제할 때 up[k]와 down[k]는 지우지 않는다. 이 정보가 있어야 Z에서 위치 탐색 없이 복구할 수 있다.
기본 풀이: 경계를 if로 확인하는 이중 연결 리스트
def solution(n, k, cmd):
up = [i - 1 for i in range(n)]
down = [i + 1 for i in range(n)]
up[0] = -1
down[n - 1] = -1
deleted = []
for command in cmd:
if command[0] == "U":
x = int(command.split()[1])
for _ in range(x):
k = up[k]
elif command[0] == "D":
x = int(command.split()[1])
for _ in range(x):
k = down[k]
elif command == "C":
deleted.append(k)
prev_node = up[k]
next_node = down[k]
if prev_node != -1:
down[prev_node] = next_node
if next_node != -1:
up[next_node] = prev_node
k = next_node if next_node != -1 else prev_node
else: # command == "Z"
restore_node = deleted.pop()
prev_node = up[restore_node]
next_node = down[restore_node]
if prev_node != -1:
down[prev_node] = restore_node
if next_node != -1:
up[next_node] = restore_node
answer = ["O"] * n
for node in deleted:
answer[node] = "X"
return "".join(answer)U와 D: k는 이동 횟수가 아니라 현재 위치
action, num = command.split()
if action == "U":
for _ in range(int(num)):
k = up[k]PDF에서 질문했던 것처럼 k = up[k]는 ‘k만큼 위로 이동’이 아니다. k는 현재 선택한 행 번호이고, 이 대입은 한 칸 위로 가는 동작이다. 실제 이동 횟수는 num이다.
예를 들어 현재 k가 5이고 명령이 U 3이면 반복문이 세 번 실행된다. 첫 번째에는 k = up[5]라서 4, 두 번째에는 k = up[4]라서 3, 세 번째에는 k = up[3]라서 2가 된다. 한 칸 이동을 num번 반복하는 구조다.
C 삭제: 양옆 두 행을 직접 연결하기
prev_node = up[k]
next_node = down[k]
down[prev_node] = next_node
up[next_node] = prev_node위 코드의 마지막 두 줄은 k가 중간 행일 때의 핵심만 보여 준 것이다. k가 3이고 위가 2, 아래가 4라면 down[2] = 4, up[4] = 2가 된다. 즉 2와 4가 서로 이웃이 되어 3을 건너뛴다. 기본 풀이에는 맨 위와 맨 아래 예외가 있으므로 실제로는 prev_node와 next_node가 -1인지 if로 확인한다.
Z 복구: 왜 전체 표를 다시 찾지 않아도 될까
restore_node = deleted.pop()
down[up[restore_node]] = restore_node
up[down[restore_node]] = restore_node2 - 3 - 4에서 3을 삭제하면, 살아 있는 연결은 2 - 4가 된다. 하지만 삭제된 3의 up[3]은 2, down[3]은 4로 그대로 남아 있다. Z에서 restore_node가 3이면 down[up[3]] = 3, 즉 down[2] = 3이 된다. 이어서 up[down[3]] = 3, 즉 up[4] = 3이 된다. 3의 원래 양옆 정보를 보존했기 때문에 처음부터 표를 탐색할 필요가 없다.
PDF에는 C와 Z로 화살표 변화를 확인하는 시뮬레이터 안내도 있었지만, 실제 시뮬레이터 소스는 PDF에 포함되어 있지 않았다. 그래서 존재하지 않는 코드를 임의로 넣지 않고, 위의 2 - 3 - 4 예시로 삭제와 복구 과정을 직접 검산했다.
양 끝에서 생기는 문제와 down[-1]의 정확한 의미
맨 위 실제 행 0을 삭제한다고 하자. 기본 연결 정보는 up[0] = -1, down[0] = 1이다.
up[down[0]] = up[0]
up[1] = -1첫 줄은 자연스럽다. 0이 사라졌으니 1은 새로운 맨 위가 되고, 1의 위에는 아무도 없다는 뜻으로 -1을 기록한다.
down[up[0]] = down[0]
down[-1] = 1여기서 PDF 대화 속 설명 중 하나는 바로잡아야 한다. 파이썬에서 down[-1]은 IndexError가 아니다. 음수 인덱스 -1은 리스트의 마지막 원소를 가리킨다. 따라서 맨 위 삭제에 이 식을 그대로 적용하면 프로그램이 멈추는 대신 마지막 행의 down 값을 1로 바꿔 연결을 조용히 망가뜨릴 수 있다. 기본 풀이가 경계에서 if를 쓰는 이유다.
다른 풀이: 더미 노드로 양 끝 예외를 없애기
더미 노드는 실제 행이 아닌 가상의 경계 행이다. 앞 더미를 내부 0번, 실제 행을 내부 1번부터 n번, 뒤 더미를 내부 n + 1번으로 둔다. 실제 양 끝에도 항상 이웃이 생기므로 삭제와 복구에서 if 없이 같은 연결식을 쓸 수 있다.
def solution(n, k, cmd):
deleted = []
up = [i - 1 for i in range(n + 2)]
down = [i + 1 for i in range(n + 1)]
k += 1
for cmd_i in cmd:
if cmd_i.startswith("C"):
deleted.append(k)
up[down[k]] = up[k]
down[up[k]] = down[k]
k = up[k] if n < down[k] else down[k]
elif cmd_i.startswith("Z"):
restore = deleted.pop()
down[up[restore]] = restore
up[down[restore]] = restore
else:
action, num = cmd_i.split()
if action == "U":
for _ in range(int(num)):
k = up[k]
else:
for _ in range(int(num)):
k = down[k]
answer = ["O"] * n
for row in deleted:
answer[row - 1] = "X"
return "".join(answer)n + 2는 실제 행 n개와 양끝 더미 2개를 위한 공간이다. 앞 더미가 내부 0번을 차지하므로 문제에서 주는 실제 행 0번은 내부 1번이 된다. 그래서 시작 위치에 k += 1을 한다.
up[down[k]] = up[k]는 ‘내 아래 행의 위를 내 위 행으로 바꾼다’는 뜻이다. down[up[k]] = down[k]는 ‘내 위 행의 아래를 내 아래 행으로 바꾼다’는 뜻이다. 삭제 행 k 자체의 up과 down은 건드리지 않으므로 Z에서 그대로 사용한다.
k = up[k] if n < down[k] else down[k]에서 down[k]이 n + 1이면 아래 더미를 가리킨다. 즉 실제 마지막 행을 삭제한 경우라 위 행으로 커서를 옮긴다. 그렇지 않으면 문제 조건대로 아래 행으로 이동한다.
deleted에는 더미 때문에 1이 더해진 내부 인덱스가 들어 있다. 반면 answer는 실제 행 0부터 n - 1만 가진다. 따라서 최종 X 표시에는 answer[row - 1] = "X"가 필요하다.
표 편집의 시간 복잡도
up과 down 배열 초기화는 O(N)이다. C와 Z는 연결 두 개만 갱신하므로 O(1)이다. U와 D는 한 칸 이동을 반복하지만, 문제에서 모든 X의 합이 1,000,000 이하로 제한된다. 따라서 전체 시간은 O(N + 모든 이동 횟수의 합 + 명령어 수)이며, 문제의 제한에서는 O(N)으로 볼 수 있다.
9. 스택 단원 마무리
괄호 문제에서는 가장 최근의 여는 괄호를 기억하려고 스택을 쓴다.
2진수 변환에서는 먼저 나온 나머지를 나중에 읽기 위해 스택을 쓴다.
짝지어 제거하기와 크레인에서는 가장 최근에 남은 문자·인형을 비교하려고 스택을 쓴다.
주식 가격에서는 아직 기간이 확정되지 않은 인덱스를 쌓는다.
표 편집에서는 최근 삭제 행을 Z에서 되돌리기 위해 스택을 쓰고, 이동과 삭제·복구는 이중 연결 리스트로 처리한다.
이번 단원에서 가장 중요한 습관은 ‘최근에 들어온 값’ 또는 ‘최근에 삭제한 값’을 다시 확인해야 하는지 문제 문장에서 찾는 것이다. 그 조건이 보이면 리스트의 끝을 활용한 스택 풀이를 먼저 검토해 볼 수 있다.