묘공단 (코딩 테스트 합격자 되기 파이썬편)

스택 
1. 스택의 개념 

 스택

스택(stack)의 어원은 쌓는다 이다. 어원에서 짐작할 수 있듯이 스택은 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 비유를 하자면 물티슈와 같다고 볼 수 있다. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 선입후출 또는 FILO(First In Last Out)이라고 한다. 이때 스택에 삽입하는 연산을 푸시(push), 꺼내는 연산을 팝(pop)이라고 한다. 

 

스택의 동작 원리

 

1. 초기에는 빈 스택이 있다.

   

2. 여기에 데이터 ‘1’을 푸시해보자. 그럼 다음의 그림과 같다.

   

3. 여기에 데이터 ‘2’를 푸시하면 1위로 2가 올라간다.

   

4. 팝을하면 가장 위에 있는 데이터인 ‘2’가 빠져나오게 된다.

   

5. 다시 데이터 ‘3’을 푸시하면 ‘1’ 위에 ‘3’이 위치하게 된다.

   

6. 다시 데이터 ‘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)