[백준 / C언어] Day12. 도키도키 간식드리미 (12789)

2024. 05. 29 - 코딩테스트 스터디 Day12

 

 

 

01. 문제

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

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

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

현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

 

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

 

 

 

 

02. 입력

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

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

 

 

03. 출력

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

 

 

04-1. 예제 입력 1

5
5 4 1 3 2

 

 

04-2. 예제 출력 1

Nice

 

 

 

05. 풀이 및 답

#include <stdio.h>

int main() {
    int n, num; // 앞에 서 있는 학생 수, 학생들의 번호
    int stack[1000]; 
    int top = -1;
    int compare = 1;
    
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (num != compare) { // 스택에 push
            stack[++top] = num;
        }
        else { // 스택에서 pop
            compare++;
            while (top != -1 && stack[top] == compare) {
                top--;
                compare++;
            }
        }
    }
    
    if (top == -1) {
        printf("Nice");
    }
    else {
        printf("Sad");
    }
    return 0;
}

이번 문제도 스택을 활용하여 해결해줬다.

승환이의 앞에 서 있는 학생의 수를 n, 각 학생들의 번호를 num이라는 변수로 선언해 줬다.

compare는 지금 당장 간식을 받을 수 있는 번호이다.

 

scanf 문으로 n을 입력받고, n의 횟수만큼 반복문을 돌며, 각 학생들의 번호를 입력받는다.

만약 각 학생들의 번호 num이 compare과 일치하지 않는다면, 스택에 해당 번호를 push 한다.

일치한다면, compare를 1만큼 증가시켜 준다. 

(이 부분에서 top도 감소시켜줘야 하는 것으로 조금 헷갈렸는데 그 자리에 새로 들어올 num값을 덮어쓰면 되므로 top을 감소시키지 않는다.)

스택이 비어있지 않고, 1만큼 증가한 compare가 stack의 최상위 데이터와 일치하는 동안 top을 1 감소시키고, compare를 1 증가시키는 작업을 반복한다.

(compare와 num이 한번 일치한 이후에도 연속으로 stack의 최상위 데이터와 compare가 일치할 가능성도 있기 때문이다.)

 

for문을 모두 돌고 난 후, 스택이 비어있다면 "Nice"를, 아니면 "Sad"를 출력해 준다.

 

 

정답!!

 

 

 

 

---

코드를 작성하기 전에 문제를 확실히 이해하기 위하여 그림을 그려보고 시작했다.

 

 

 

형편없는 그림이라 업로드하기에 민망하지만,, 그래도 코드 짜는데 도움을 받았기 때문에 나중을 위해서라도 우선 첨부해 둔다.

이렇게 그림을 그려보고 코드를 짜니까 그냥 문제만 읽었을 때는 생각하지 못했을 여러 경우들과 반례를 놓치지 않을 수 있었던 것 같다.