https://www.acmicpc.net/problem/12789
문제
인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.
그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
이미지출처: 백준(https://www.acmicpc.net/problem/12789)
입력
입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.
다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.
풀이과정
번호표 1번부터 N번까지 차례대로 간식을 받을 수 있어야하는 것 같다. 예제 이미지를 보면 5, 4, 1, 3, 2 이렇게 주어져있는데, 이들이 올바른 번호표에 도달하기 위해선 다음과 같은 단계를 걸쳐야 한다.
이렇게 순서가 엉키지 않고 전부 간식을 받을 수 있다면 "Nice"를 출력하고 받지 못한다면 "Sad"를 출력한다.
처음 시도한 풀이는 아래와 같다.
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 사람 수
int N = Integer.parseInt(br.readLine());
// 스택
int[] stack = new int[N];
// 현재 인덱스(공간에 가장 앞에 서 있는 사람을 구하기 위함)
int nowIndex = -1;
// 현재 번호
int nowNum = 1;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
while( N-- > 0){
// 번호표
int num = Integer.parseInt(st.nextToken());
// 만약 번호표(num)이 현재 차례(nowNum)과 같다면
// 현재 차례에서 +1 해준다.
if( num == nowNum ){
nowNum++;
}
// 공간(스택)이 비지않고
else if ( nowIndex != -1 ){
// 공간 가장 앞에 서 있는 사람이
// 현재 차례라면
if( stack[nowIndex] == nowNum ){
// 공간 가장 앞에 서 있는 사람을 내보내고
// num을 저장한다.
stack[nowIndex] = num; nowNum++;
}else
// 아니라면 맨 앞에 num을 저장한다.
stack[++nowIndex] = num;
}
// 위의 두 조건 다 일치하지 않는다면
// 스택(공간) 맨 앞에 num을 저장한다.
else{
stack[++nowIndex] = num;
}
}
boolean canEat = true;
// 스택(공간)이 빌 때까지 반복한다.
while( nowIndex != -1 ){
// 만약 스택(공간) 맨 앞에 서있는 사람이
// 현재 번호(차례)와 일치하지 않는다면
// 순서가 꼬였다는 뜻이므로 canEat를 false로 저장하고 반복문을 벗어난다.
if( stack[nowIndex--] != nowNum++ ) {
canEat = false;
break;
}
}
System.out.println( canEat ? "Nice" : "Sad" );
}
}
처음에 위의 코드로 작성해서 제출했지만 틀렸다. 여러 반례를 생각하며 이유를 찾았다.
이유는
// 공간(스택)이 비지않고
else if ( nowIndex != -1 ){
// 공간 가장 앞에 서 있는 사람이
// 현재 차례라면
if( stack[nowIndex] == nowNum ){
// 공간 가장 앞에 서 있는 사람을 내보내고
// num을 저장한다.
stack[nowIndex] = num; nowNum++;
}else
// 아니라면 맨 앞에 num을 저장한다.
stack[++nowIndex] = num;
}
이 부분에서 찾을 수 있었는데, 공간 가장 앞에 서 있는 사람(스택의 맨 위)이 현재 차례라면 내보내고 다음 사람인 num을 저장한다고 하였다.
이 구문은 다음 반례로 틀림이 입증된다.
6
5 4 1 2 3 6
내가 작성한 코드대로 실행하면 다음과 같이 실행될 것이다.
3번 단계에서 명백히 오류가 발생한다. 스택에 4, 5 순으로 저장되어있으므로 4를 내보낸다음에 바로 5를 내보내야하는데 4를 내보내고 5번 다음에 6을 줄을 세워버렸다.
중간에 반복문을 추가하여 해당 오류를 수정하니 잘 통과된 것을 볼 수 있었다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] stack = new int[N];
int nowIndex = -1;
int nowNum = 1;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
while( N-- > 0){
int num = Integer.parseInt(st.nextToken());
if( num == nowNum ){
nowNum++;
}else if ( nowIndex != -1 ){
if( stack[nowIndex] == nowNum ){
// 스택(공간)이 빌 때까지 반복한다.
while (nowIndex != -1){
if(stack[nowIndex] == nowNum){
nowIndex--; nowNum++;
}else
break;
}
stack[++nowIndex] = num;
}else
stack[++nowIndex] = num;
}else{
stack[++nowIndex] = num;
}
}
boolean canEat = true;
while( nowIndex != -1 ){
if( stack[nowIndex--] != nowNum++ ) {
canEat = false;
break;
}
}
System.out.println( canEat ? "Nice" : "Sad" );
}
}