[Baekjoon] 12789 - 도키도키 간식드리미 (Python 파이썬)

백준, 12789- 도키도키 간식드리미 파이썬(Python) 풀이

 

안녕하세요. 백준 실버3 문제인 '12789 - 도키도키 간식드리미' 문제를 파이썬으로 풀어보았습니다.

최근 작성한 스택 개념 글과 이어지는 코드로 파이썬으로 스택 구현 방법을 알고 싶다면

https://akatsuki.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack-Python-%EA%B5%AC%ED%98%84-%EB%B0%B1%EC%A4%80-10828

[자료구조] 스택(Stack) Python 구현 (백준 - 스택: 10828)

를 참고해주세요.

문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다.

 

백준, Baekjoon

 

문제 링크

https://www.acmicpc.net/problem/12789

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

 

---

문제 설명

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

이해를 돕는 그림이 링크 들어가보면 있기 때문에 링크에서 문제 확인해보는 것을 추천드립니다.

---

제한사항

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

출력

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

---

문제 해결

우선, 기본적인 스택 형태를 구현해주었습니다. 이전에 구현한 empty, size는 필요하지 않을 것 같아 뺐습니다.

두 개의 루프로 나누어 처리를 진행했습니다. 첫번째 루프에선 대기열의 각 번호를 처리하는데 사용하도록 구성했습니다. 숫자를 저장하고, 맨 위 숫자를 기대 값과 일치할 때까지 숫자를 제거하며 기대값을 증가 시켜 순서대로 줄을 서는지 확인 합니다.

두번째 루프에선 대기열에서 처리 후 남은 숫자들을 하나씩 빼며 기대값과 비교해 순서대로 서있는지 확인하도록 코드를 구성해봤습니다.

---

코드

#12789

import sys

class Stack:
    def __init__(self):
        self.stack = []
        
    def push(self, x):
        self.stack.append(x)
        
    def pop(self):
        if self.stack:
            return self.stack.pop()
        return -1
    
    def top(self):
        if self.stack:
            return self.stack[-1]
        return -1

def check_order(n, queue):
    stack = Stack()
    exp = 1 # 원하는 번호
    
    for num in queue:
        # 스택 비어있지 않고, 맨 위가 기대값이면 pop 하고 exp 1 증가
        while stack.stack and stack.top() == exp:
            stack.pop()
            exp += 1
        
        # 현재 번호가 기대값이면 다음 번호로
        if num == exp:
            exp += 1
        # 아니면 스택에 현 번호 추가
        else:
            stack.push(num)
    
    #가장 위 번호를 빼서 기대값과 비교 후 다르면 순서대로가 아님       
    while stack.stack:
        if stack.pop() != exp:
            return "Sad"
        exp += 1
        
    return "Nice"

n = int(sys.stdin.readline())
queue = list(map(int, sys.stdin.readline().split()))

print(check_order(n, queue))

---

사용한 개념

스택, Stack

https://akatsuki.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack-Python-%EA%B5%AC%ED%98%84-%EB%B0%B1%EC%A4%80-10828

[자료구조] 스택(Stack) Python 구현 (백준 - 스택: 10828)