묘공단 (코딩 테스트 합격자 되기 파이썬편)
스택
1. 스택의 개념
스택
스택(stack)의 어원은 쌓는다 이다. 어원에서 짐작할 수 있듯이 스택은 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 비유를 하자면 물티슈와 같다고 볼 수 있다. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 선입후출 또는 FILO(First In Last Out)이라고 한다. 이때 스택에 삽입하는 연산을 푸시(push), 꺼내는 연산을 팝(pop)이라고 한다.
스택의 동작 원리
- 초기에는 빈 스택이 있다.
- 여기에 데이터 ‘1’을 푸시해보자. 그럼 다음의 그림과 같다.
- 여기에 데이터 ‘2’를 푸시하면 1위로 2가 올라간다.
- 팝을하면 가장 위에 있는 데이터인 ‘2’가 빠져나오게 된다.
- 다시 데이터 ‘3’을 푸시하면 ‘1’ 위에 ‘3’이 위치하게 된다.
- 다시 데이터 ‘3’을 푸시하면 ‘1’ 위에 ‘3’이 위치하게 된다.
ADT?
ADT(Abstract Data Type)는 우리말로 추상 자료형이라는 뜻이며 인터페이스만 있고 실제로 구현은 되지 않은 자료형이다. 일종의 자료형의 설계도라고 생각하면 된다.
* 언어에 따라 스택 제공여부는 다르다.
파이썬의 경우 리스트 메서드인 append().push() 로 스택을 대체 가능함
스택의 ADT?
스택에서는 1푸시, 2 팝, 3 가득 찼는지 확인, 4 비었는지 확인과 같은 연산을 정의해야 합니다.
추가로 스택은 최근 삽입한 데이터의 위치를 저장할 변수인 탑도 존재해야함.
구분 | 정의 | 설명 |
연산 | boolean ifFull( ) | 스택이 가득 차 있다면 True, 아니면 False를 반환함 |
연산 | boolean ifEmpty( ) | 스택이 비어있다면 True, 데이터가 하나라도 있다면 False를 반환함 |
연산 | void push(Item Type item) | 스택에 데이터를 푸시함 |
연산 | ItemType pop() | 스택에서 최근에 푸시한 데이터를 팝하고, 그 데이터를 반환함 |
상태 | Int top | 스택에서 최근에 푸시한 데이터의 위치를 기록함 |
상태 | ItemType data[maxsize] | 스택의 데이터를 관리하는 배열. 최대 maxsize개의 데이터를 관리함 |
이 그림은 스택의 ADT를 나타낸것
스택 구현하기
stack = [ ] # 스택 리스트 초기화
max_size = 10 # 스택의 최대 크기
def isFull(stack): # 스택이 가득 찼는지 확인하는 함수
return len(stack) == max_size
def isEmpty(stack): # 스택이 비었는지 확인하는 함수
return len(stack) == 0
def push(stack, item): # 스택에 데이터를 추가하는 함수
if isFull(stack):
print("스택이 가득 찼습니다.")
else:
stack.append(item)
print("데이터가 추가되었습니다.")
def push(stack): # 스택에서 데이터를 꺼낸는 함수
if isEmpty(stack):
print("스택이 비어 있습니다.")
return None
else:
return stack.pop()
파이썬은 리스트 크기를 동적으로 관리하기 때문에 max_size나 isFull(), isEmpty()는 실제 문제를 풀때 구현하지 않는다.
이번 코드를 보면 max_size,isFull()함수는 사용하지 않고 is Empty 함수는 len(stack)==0으로 검사한다.
stack = [ ]
def push(stack, item):
stack.append(item)
print("데이터가 추가되었습니다.")
def pop(stack):
if len(stack) == 0:
print("스택이 비어 있습니다.")
return None
else:
return stack.pop()
하지만 push함수, pop함수를 보면 실에 이 함수들은 리스트의 append,pop를 호출 하는것이 전부임
그러하여 push함수와 pop 함수는 다음과 같이 구현하지 않아도 된다.
stack = []
스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)
스택에 데이터 꺼냄
top_element = stack.pop()
nest_element = stack.pop()
스택의 크기를 구함
stack_size = len(stack)
top_element : 3
next_element: 2
3. 몸풀기 문제
8. 괄호 짝 맞추기
열린괄호나 닫힌괄호가 마구 뒤섞인 문자열에서 소괄호가 정상으로 열고 닫혔는지 판별하는 solution() 함수를 구현해라. 소괄호가 정상적으로 닫혔다면 True, 그렇지 않다면 False를 반환해라.
제약 조건
- 열린 괄호는 자신과 가장 가까운 괄호를 만나면 상쇄된다.
- 상쇄 조건은 열린 괄호가 먼저 와야하고, 열린 괄호와 닫힌 괄호 사이에 아무것도 없어야 한다.
- 더 상쇄할 괄호가 없을 때까지 상쇄를 반복한다.
s | 반환값 |
( ( ) ) ( ) | True |
( ( ( ) ) ( ) | False |
def solution(s):
stack = []
for c in s:
if c == "(":
stack.append(c)
elif c == ")":
if len(stack) == 0:
return False
else:
stack.pop()
if len(stack) == 0:
print(True)
else:
print(False)
s = "(())()"
#s = "((())()"
solution(s)
9. 10진수를 2진수로 변환하기
10진수를 입력받아 2진수로 변환해 반환하는 solution() 함수를 구현해라.
제약 조건
- 제약 조건 없음
decimal | 반환값 |
10 | 1010 |
27 | 11011 |
12345 | 11000000111001 |
def solution(decimal):
stack = []
while decimal > 0:
a = decimal % 2
stack.append(str(a))
decimal //= 2
result = ' '
while stack:
result += stack.pop()
print(result)
decimal = 10
#decimal = 27
#decimal = 12345
solution(decimal)
10. 괄호 회전하기
대괄호, 중괄호, 소괄호로 이루어진 문자열 s가 매개변수로 주어진다. 이 s를 왼쪽으로 x칸 만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게하는 x의 개수를 반환하는 solution() 함수를 완성하세요.
제약 조건
- s의 길이는 1 이상 1,000 이하이다.
s | result |
“[ ] ( ) { }” | 3 |
“} ] ( ) [ {” | 2 |
“[ ) ( ]” | 0 |
“} } }” | 0 |
def solution(s):
answer = 0
n = len(s)
for i in range(n):
stack = []
for j in range(n):
c = s[(i+j)%n]
if c == "(" or c == "[" or c == "{":
stack.append(c)
else:
if not stack:
break
if c == ")" and stack[-1] == "(":
stack.pop()
elif c == "]" and stack[-1] == "[":
stack.pop()
elif c == "}" and stack[-1] == "{":
stack.pop()
else:
break
else:
if not stack:
answer += 1
print(answer)
s = "[](){}"
#s = "}]()[{"
#s = "[)(]"
#s = "}}}"
solution(s)
11. 짝지어 제거하기
알파벳 소문자로 구성된 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 짝을 찾은 다음 그 둘을 제거한뒤 앞 뒤 문자열을 붙입니다. 이 과정을 반복하여 문자열을 모두 제거한다면 1을 아니라면 0을 반환하는 solution()을 완성해라
제약 조건
- 문자열 길이 : 1,000,000 이하의 자연수
- 문자열은 모두 소문자로 이루어져 있음
s | result |
“baabaa” | 1 |
“cdcd” | 0 |
def solution(s):
first_pop = ""
second_pop = ""
w = []
stack = []
for i in s:
stack.append(i)
for j in range(len(stack)//2):
for k in range(len(stack)-1):
if stack[k] == stack[k+1]:
w = []
w.append(k)
if len(w) > 0:
stack.pop(w[0])
stack.pop(w[0])
if len(stack) > 1:
print(0)
elif len(stack) == 0:
print(1)
s = 'baabaa'
solution(s)
12. 주식 가격
초단위로 기록된 주식 가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇초인지 반환하도록 solution()을 완성해라
제약조건
- prices의 가격은 1 이상 10,000 이하의 자연수.
- prices의 길이는 2 이상 100,000 이하이다.
def solution(prices):
stack = []
result = []
count = 0
for i in prices:
stack.append(i)
for j in range(len(stack)):
count = 0
for k in range(j+1, len(stack)):
if stack[k] >= stack[j]:
count += 1
result.append(count)
print(result)
prices = [1,2,3,2,3]
solution(prices)