스택 개념을 이해하고, 이를 바탕으로 스택의 ADT를 작성하고 구현할 수 있습니다. 스택을 활용해 주어진 문제를 풀 수 있습니다.
총 2편으로 준비했습니다.
2. 스택 몸풀기 문제
지금까지 배운 내용을 활용해서 문제 2개를 풀어보겠습니다. 여기서는 왜 스택을 사용하는지, 스택을 어떤 식으로 활용하는지에 집중하며 학습하기 바랍니다.
문제 1. 괄호 짝 맞추기 ⭐️⭐️
- 저자 권장 시간: 30분
- 권장 시간 복잡조: O(N)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/08.py
소괄호는 짝을 맞춘 열린 괄호 ‘(’와 닫힌 괄호 ‘)’로 구성합니다. 문제에서는 열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열을 줍니다. 이때 소괄호가 정상으로 열고 닫혔는지 판별하는 solution( ) 함수를 구현하세요. 만약 소괄호가 정상적으로 열고 닫혔다면 True를, 그렇지 않다면 False를 반환하면 됩니다.
제약 조건
- 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄됩니다.
- 상쇄 조건은 열린 괄호가 먼저 와야 하고, 열린 괄호와 닫힌 괄호 사이에 아무것도 없어야 합니다.
- 더 상쇄할 괄호가 없을 때까지 상쇄를 반복합니다.
입출력의 예
01단계 다음은 짝이 맞지 않는 괄호의 예입니다. 한눈에 봐도 괄호의 짝이 맞지 않습니다. 닫힌 괄호가 먼저 왔으므로 더 이상 상쇄가 되지 않으며, 결과적으로 괄호가 전부 없어지지 않습니다.
02단계 다른 예도 봅시다. 이 역시도 괄호의 짝이 맞지 않습니다. 첫 괄호의 짝은 맞아 상쇄할 수 있지만 마지막 괄호는 짝이 없으므로 상쇄할 수 없습니다.
03단계 그러면 이번에는 괄호의 짝이 맞아 모두 상쇄되는 예를 봅시다. 다음의 경우 괄호의 짝이 맞아서 상쇄되어 모두 사라졌습니다.
04단계 이 경우도 괄호의 짝이 맞는 경우입니다. 그림에서 보듯 항상 첫 번째 짝만 괄호가 맞아야 할 필요는 없습니다.
문제 분석하고 풀기
이런 괄호 짝 맞추기를 해결하려면 어떻게 해야 할까요? 바로 스택을 사용하면 됩니다. 스택을 어떻게 적용할 수 있는지 알아보겠습니다. 여러분이 문제 조건에서 주목해야 할 내용은 닫힌 괄호가 임의 위치의 열린 괄호와 상쇄되는 것이 아니라 닫힌 괄호가 나오기 바로 전의, 즉, 가장 가까운(최근) 열린 괄호와 상쇄된다는 겁니다. 가장 가까운(최근)이라는 키워드를 보고 스택을 떠올리는 감각이 있어야 합니다. 스택과 함께 이 문제를 풀려면 다음과 같은 과정으로 괄호를 상쇄하면 됩니다.
- 문자열을 앞에서 하나씩 보며 열린 괄호가 나오면 푸시
- 닫힌 괄호가 나오면 팝 연산을 통해 문자열에서 열린 괄호, 닫힌 괄호 한 쌍을 상쇄
- 1~2를 마지막 문자열까지 반복해 스택에 열린 괄호가 남아 있다면 짝이 맞지 않은 것(False)이고, 괄호가 남아 있지 않다면 짝이 맞은 것(True)으로 판단
실제 데이터와 함께 위 과정을 연습해봅시다.
괄호의 짝이 맞는 경우
01단계 우선은 짝이 맞는 경우를 봅시다. ➊ 크기가 6인 배열에 괄호를 배치하고 스택을 준비합니다. ➋ 그런 다음 인덱스 0은 열린 괄호이므로 스택에 푸시하고 다음을 봅니다. ➌ 다음의 값은 닫힌 괄호이므로 스택에서 팝하고 다음을 봅니다. 이 단계를 마치면 스택에는 아무것도 없으므로 지금까지 본 인덱스 0~1에 한해서는 괄호를 상쇄했다고 보아도 됩니다.
02단계 ➊ 인덱스 2는 열린 괄호이므로 푸시하고 다음을 봅니다. ➋ 인덱스 3은 열린 괄호이므로 다시 푸시하고 다음을 봅니다. ➌ 이번엔 닫힌 괄호이므로 스택에서 팝하고 다음을 봅니다. ➍ 인덱스 5는 닫힌 괄호이므로 팝하고 연산을 마칩니다. 모든 탐색을 끝냈을 때 스택이 비어 있으므로 배열의 괄호는 모두 짝이 맞습니다.
괄호의 짝이 맞지 않는 경우
01단계 이번엔 짝이 맞지 않은 경우를 봅니다. ➊ (, ), ( 순서로 괄호가 배치되어 있습니다. ➋ 처음은 열린 괄호이므로 푸시하고 그다음을 봅니다.
02단계 ➌ 인덱스 1은 닫힌 괄호이므로 팝하고 다음을 봅니다. ➍ 인덱스 2는 열린 괄호이므로 푸시합니다. 이렇게 하고 보면 모든 데이터를 탐색했으므로 스택에는 열린 괄호가 남아 있습니다. 즉, 짝이 맞지 않습니다.
이제 코드로 문제를 풀어봅니다. 코드는 아주 간단합니다.
def solution(s):
stack = [ ]
for c in s:
if c == "(":
stack.append(c)
elif c == ")":
if not stack:
return False
else:
stack.pop( )
if stack:
return False
else:
return True
시간 복잡도 분석하기
N은 s의 길이입니다. s를 순회하며 괄호의 쌍을 확인하므로 시간 복잡도는 O(N)입니다. 참고로 괄호 쌍을 확인할 때 append( ) 메서드와 pop( ) 메서드의 시간 복잡도는 O(1)입니다.
문제 2. 10진수를 2진수로 변환하기 ⭐️
- 저자 권장 시간: 30분
- 권장 시간 복잡조: O(logN)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/09.py
10진수를 입력받아 2진수로 변환해 반환하는 solution( ) 함수를 구현하세요.
제약 조건
제약 조건 없음
입출력의 예
문제 분석하고 풀기
우선 10진수를 2진수로 표현하는 과정을 봅시다. 10진수를 2진수로 표현하는 과정은 다음과 같으며, 이 과정은 이미 수학적으로 증명된 것이므로 별도로 설명하지 않겠습니다.
- 10진수 N을 2로 나눈 나머지, 즉, %2 연산을 한 값을 저장하고, N은 2로 나눔
- 몫이 0이 아니라면 나머지를 버리고 다시 1을 수행
- 모든 과정이 끝나고 1에서 저장한 수를 뒤부터 순서대로 가져와 붙이기
십진수를 2진수로 변환하는 과정
십진수 13을 위 과정대로 변경하는 모습은 다음과 같습니다. 13을 2로 나누면서 나눈 나머지를 순서대로 저장합니다. 이 과정을 0이 될 때까지 반복합니다. 몫이 0이 되면 저장한 값을 뒤부터 순서대로 읽으면 1101으로 이진수 변환이 완료됩니다.
이 문제도 스택으로 쉽게 풀 수 있습니다. 스택에 저장할 데이터가 무엇인지 정의하면 됩니다. 그림의 왼쪽을 보면 10진수 N을 2로 나누며 나머지를 표시했는데 이 나머지를 거꾸로 읽으면 우리가 원하는 이진수가 됩니다. 즉, 나머지를 스택에 쌓고, 하나씩 꺼내면 답이 나옵니다.
01단계 다음 그림을 보며 이해해봅시다. 초기에는 13으로 시작합니다. 이것을 2로 나누고 나머지를 스택에 푸시합니다. 13을 2로 나눈 나머지가 1이므로 1을 푸시했습니다.
02단계 그다음도 같은 작업을 계속합니다. 6을 2로 나눈 나머지는 0이므로 0을 푸시하고, 3을 2로 나눈 나머지는 1이므로 1을 푸시합니다.
03단계 십진수 13을 몫이 0이 될 때까지 나눈 결과로 스택에는 1, 0, 1, 1이 쌓였습니다.
04단계 연산이 끝난 후 스택에서 팝한 값을 나열하면 13을 이진수로 변환한 1101이 됩니다.
지금까지 설명한 내용을 바탕으로 코드를 작성하면 다음과 같습니다.
def solution(decimal):
stack = [ ]
while decimal > 0:
remainder = decimal % 2
stack.append(str(remainder))
decimal //= 2
binary = ""
while stack:
binary += stack.pop( ) # 이 문제에서는 스택 활용을 보여주기 위해 pop()을 했지만 문자열에 계속해서 문자를 더할 때는 join() 메서드가 더 효율적입니다.
return binary
시간 복잡도 분석하기
N은 이진수로 변환할 숫자입니다. N을 이진수로 변환하는 과정은 N이 1이 될 때까지 2로 계속 나누므로 연산 횟수는 O(logN)입니다. 하지만 문자열의 += 연산자는 수행할 때마다 객체를 새로 생성합니다. 따라서 시간 복잡도는 O((logN)2)이 됩니다.
※ join( ) 메서드를 활용하면 시간 복잡도를 O(logN)으로 낮출 수 있습니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
1 Comment