Python - [백준 12789] 도키도키 간식드리미 (feat. 스택)

 

2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)

[자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)

 

 

 

BOJ_12789_도키도키 간식드리미

 

1. 문제 설명

백준 12789 - 도키도키 간식드리미 문제는 간식을 순서대로 나눠주는 상황을 시뮬레이션하는 문제입니다. 줄을 서 있는 사람들에게 번호가 있고, 간식을 받을 때 반드시 1번, 2번, 3번, ..., N번 순서로 간식을 받아야 합니다.
줄의 순서대로 간식을 줄 수 없을 경우, 임시로 스택에 보관할 수 있지만 규칙을 어기면 "Sad"를 출력해야 합니다.

---

2. Checkpoint

 

알고리즘 문제를 C언어로 풀다가 python에 적응하기 위해 다시 스택부터 구현 중이나,
STL의 활용이나 간소화된 문법에 적응하지 못하고 C언어로 다 푼다음에 python으로 옮겨서 풀었습니다...

그마저 ChatGPT의 답안과 거리가 멀었는데, 이유는 즉슨, 

 

C언어의 배열 활용을 그대로 가져와서 리스트의 pop과 apeend 함수만 적용해 python 코드로 변환한 제 코드와 달리,

ChatGPT는 STL을 활용해 줄을 queue 형태로, 임시 대기 장소를 list(stack) 로 처리하였습니다.

 

python에 deque, queue에 대한 STL을 모르고 있던지라 해당 내용을 따로 학습할 계획입니다.

하단의 설명은 Chatgpt의 답안대로 설명하되, 최하단에는 제가 구현한 코드를 별도 첨부하겠습니다.

알고리즘의 흐름은 동일합니다.

 

+ 상단의 노란색 줄은 STL을 활용한 것이며, 파란색 줄은 제 코드 실행결과입니다.

문제 접근 방법

1. 줄을 관리하기 위해 큐(queue)를 사용합니다.
2. 임시 대기 장소로 스택(stack)을 활용합니다.
3. 현재 간식을 받을 순서와 비교하여 다음과 같은 방식으로 처리합니다.
   • 줄에서 간식을 받을 차례가 맞으면 간식을 줍니다.
   • 차례가 맞지 않으면 스택에 대기시킵니다.
   • 스택에서 대기 중인 사람이 받을 순서가 되면 스택에서 간식을 줍니다.
4. 모든 사람이 순서대로 간식을 받으면 "Nice"를 출력하고, 순서를 지킬 수 없으면 "Sad"를 출력합니다.

---

3. 코드 구현

from collections import deque

# 입력 처리
N = int(input())
line = deque(map(int, input().split()))

# 변수 초기화
stack = []
current = 1  # 현재 간식을 받을 순서 번호

# 시뮬레이션 시작
while line or stack:
    # 줄에서 간식을 받을 수 있는 경우
    if line and line[0] == current:
        line.popleft()
        current += 1
    # 스택에서 간식을 받을 수 있는 경우
    elif stack and stack[-1] == current:
        stack.pop()
        current += 1
    # 줄에서 간식을 받을 수도, 스택에서 받을 수도 없는 경우
    else:
        if line:
            stack.append(line.popleft())
        else:
            break

# 결과 출력
if current > N:
    print("Nice")
else:
    print("Sad")

---

4. 코드 설명

1. 변수 및 데이터 구조 초기화
   • line: 줄에 서 있는 사람들의 번호를 저장하는 큐입니다.
   • stack: 임시로 대기하는 사람들을 저장하는 스택입니다.
   • current: 현재 간식을 받을 순서 번호입니다.
2. 반복문 실행
   • 줄에서 간식을 받을 순서가 맞으면 바로 간식을 줍니다.
   • 줄에서 간식을 줄 수 없을 경우 해당 사람을 스택에 넣어 대기시킵니다.
   • 스택의 맨 위에 있는 사람이 받을 차례가 되면 간식을 줍니다.
3. 결과 출력
   • 모든 사람이 순서대로 간식을 받았다면 "Nice"를 출력합니다.
   • 중간에 순서가 꼬여 간식을 줄 수 없으면 "Sad"를 출력합니다.

---

5. 예제 입력 및 출력

예제 입력 1

5
1 2 5 3 4

예제 출력 1

Nice

예제 입력 2

5
1 2 4 3 5

예제 출력 2

Sad

---

6. (별도) STL 없이 구현한 코드

N = int(input())
arry = list(map(int, input().split()))
start = 0
stack = []
for i in range(1,N):
    target = i
    temp = 0
    for j in range(start, N):
        if target != arry[j] :
            stack.append(arry[j])
        else:
            start = j+1
            temp = 1
            break
    if temp == 0:
        while(stack):
            if target != stack[-1]:
                stack.pop()
            else:
                temp = 1
                break
    if temp == 0:
        print("Sad")
        exit()

print("Nice")

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.