스택구조 문제풀이 (백준 28278번, 4949번, 12789번)

백준 28278번: 스택 2

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3: 스택에 들어있는 정수의 개수를 출력한다.
4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

 

10828번 스택 문항과 굉장히 유사하다. 사실상 command가 문자열에서 숫자로 바뀐 것 말고는 똑같은 문제이다. 마찬가지로 시간 초과에 주의해야 하기에 input() 대신 sys 내장모듈을 이용하여 sys.stdin.readline()을 사용하였고, try-except 구문을 쓰지 않았다.

import sys
stack = []
for _ in range(int(sys.stdin.readline())):
    a = sys.stdin.readline()
    b = int(a[0])
    if b==1:
        _, x = a.strip().split()
        stack.append(x)
    elif b==2:
        if stack:
            print(stack.pop())
        else:
            print(-1)
    elif b==3:
        print(len(stack))
    elif b==4:
        print(int(not bool(stack)))
    elif b==5:
        if stack:
            print(stack[-1])
        else:
            print(-1)

 

백준 4949번: 균형잡힌 세상

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

 

입력:
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력:
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

 

왼쪽 괄호와 오른쪽 괄호의 균형을 맞추어 세계의 균형을 유지해 보자.네네 9012번 괄호 문제와 유사하지만, 소괄호 대괄호로 구분되어 있는 것이 다르다. 그리고 문자열이 괄호만 주어지는 것이 아니라 아래와 같이 알파벳과 공백 등도 섞여 있다. 가장 아랫줄에 보이는 마침표만 있는 것도 균형잡힌 문자열이다.

또한 이 문제는 몇 줄의 입력이 들어오는지 주어져 있지 않다. 따라서 무한루프를 돌다가 "."이 들어오면 break로 빠져나가는 식으로 구성해야 한다. sys.stdin.readline()은 문자열에 더해, "\n"까지 문자열로 인식하기 때문에 무한루프를 break하기가 성가시다. 반면, input()은 "\n"을 제외하고 문자열로 인식하므로 그냥 input() 과 "." 를 비교하면 된다.  따라서 아래와 같이 작성하였다.

def world_balance(string):
    stack = []
    for chars in string:
        if chars in ["(", "["]:
            stack.append(chars)
        elif chars == ")":
            if stack:
                if stack[-1] == "(":
                    stack.pop()
                else:
                    return "no"
            else:
                return "no"
        elif chars == "]":
            if stack:
                if stack[-1] == "[":
                    stack.pop()
                else:
                    return "no"
            else:
                return "no"
        else:
            continue
    return "yes" if not stack else "no"

while True:
        line = input()
        if line == '.':
            break
        else:
            print(world_balance(line))

 

백준 12789번: 도키도키 간식드리미

 

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 
그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다.

입력:
입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.
다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

출력:
승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.

 

처음에는 "한 명씩만 설 수 있는 공간"을 스택으로 생각하여 리스트를 만들고, 간식 받는 곳을 리스트로 만들어 아래와 같이 로직을 구성하였다.

N = int(input())

numbers = list(map(int, input().split()))

treats = []
waits = []
answer = "Nice"

for number in numbers:
    if number == max_number:
        waits.append(number)
    elif number == 1:
        treats.append(number)
    elif treats and number == treats[-1]+1:
        treats.append(number)
    elif waits and number == waits[-1]-1:
        waits.append(number)
    else:
        answer = "Sad"
        break

print(answer)

 

하지만, 이렇게 할 경우 좁은 공간 스택이 중간에 비워지는 케이스에서 예외가 난다. 예를 들어, n=5일 때 3 2 1 4 5가 들어오면 3과 2가 좁은 공간으로 들어가고 1이 간식을 받은 후 2와 3이 간식을 받고 4와 5가 받을 수 있다. 이를 해결하기 위해, 간식을 받는 사람은 무조건 1, 2, 3... 순서로 받아야 함에 착안하기로 했다.

 

이때, 좁은 공간은 스택 구조이지만, 원래 줄을 서는 곳인 numbers는 큐(queue)구조이다. 큐 구조에 대해서는 다음 포스팅에서 다루고자 한다.

N = int(input())

numbers = list(map(int, input().split()))
max_number = max(numbers)

treat = 1
stack = []
while numbers:
    if numbers[0] == treat:
        numbers.pop(0)
        treat+=1
    else:
        stack.append(numbers.pop(0))
    while stack:
        if stack[-1]==treat:
            stack.pop()
            treat+=1
        else:
            break
    
if stack:
    print("Sad")
else:
    print("Nice")