[백준/BOJ] 12789번 도키도키 간식드리미 (C/C++)

백준 온라인 저지(BOJ) 12789번 도키도키 간식드리미

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

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

* 사용언어 : C언어, C++

 

1. 문제

번호표를 들고 줄 서있는 N명의 사람들이 LIFO로 들어갈 수 있는 공간을 활용하여

번호표 순서대로 라인에 들어갈 수 있으면 Nice 아니면 Sad 출력

 

2. 풀이

문제 설명이 매우 길고 불필요한 정보가 많은데

요약하면 Stack 하나를 활용해서 주어진 숫자 배열을 1부터 순서대로 나열할 수 있는지를 묻는 문제라고 보면 됩니다.

 

 

설계를 하면서 효율적인 방법을 몇 가지 떠올리고 곧바로 구현했었는데

자꾸 오답이 나고 코드가 점점 복잡해지길래 우선 단순한 형태로 구현을 해봤습니다.

 

 

소스 코드는 2중 반복문으로 구성했습니다.

바깥 쪽 반복문(for문)은 숫자를 N번 입력받으며 처리하기 위한 반복문이고,

안 쪽 반복문(while문)은 Stack의 top 숫자를 확인하면서 순서(order)가 된 경우 pop하는 반복문입니다.

 

우선 주어지는 입력은 for문을 통해 하나 씩 입력받으며 처리했습니다.

입력된 숫자가 대기열 순서(order)와 같으면 라인을 통과한 것으로 보고 order를 증가시켰고,

그렇지 않으면 그 숫자를 Stack에 넣어주었습니다.

 

그리고 위와 같이 숫자를 하나 씩 처리할 때마다

while 문을 통해 Stack의 top 숫자가 order와 같은지 확인하면서 하나 씩 pop했습니다.

 

그렇게 for문을 마친 후에는 N명의 사람들이 모두 라인을 통과했는지를 확인하여

Nice 혹은 Sad를 출력했습니다.

 

 

정답을 제출한 후에 처음 생각했었던 효율화를 다시 적용해봤는데도 오답이 나왔습니다.

여기서 시간을 꽤 많이 들이며 계속 고민한 결과, 결국 오답인 이유를 알 수 있었습니다.

 

예제 입력만 보고 Stack에도 숫자가 순차적으로 들어가야한다고 생각하고 설계를 했었는데,

사실 그렇지 않고 오히려 아래 반례에서 Nice가 나올 수 있다는 것을 알 수 있었습니다.

 

5

5 3 1 2 4

 

 

문제에 불필요한 설명이 많다는 이유로 제대로 이해하지 않고 넘어가다가 발생한 실수 같습니다.

 

예제 입출력만 보면서 요구사항을 넘겨짚지 말고

문제를 꼼꼼히 읽으면서 제대로 파악해야겠다는 교훈을 얻을 수 있었습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
12789_도키도키 간식드리미
1120KB	0ms
*/
#include <cstdio>

const int LM = 1000;
int st[LM], top = -1, N, n, order = 1;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &n);
		if (n == order) ++order;
		else st[++top] = n;

		while (top >= 0 && st[top] == order) {
			++order;
			--top;
		}
	}

	if (order - 1 == N) printf("Nice\n");
	else printf("Sad\n");

	return 0;
}