[백준] java 12789 도키도키 간식드리미

Sundae·2023년 12월 21일
0

백준

목록 보기
44/63
post-custom-banner

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 이렇게 주어져있는데, 이들이 올바른 번호표에 도달하기 위해선 다음과 같은 단계를 걸쳐야 한다.

  1. 5, 4번이 자신의 차례가 아니므로 공간에 들어간다.
  2. 1번은 자신의 차례이므로 간식을 받는다.
  3. 3번은 자신의 차례가 아니므로 공간에 들어간다.
  4. 2번은 자신의 차례이므로 간식을 받는다.
  5. 공간에 남아있던 사람들을 확인해보니 3, 4, 5로 올바른 순서로 간식을 받을 수 있다.

이렇게 순서가 엉키지 않고 전부 간식을 받을 수 있다면 "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

내가 작성한 코드대로 실행하면 다음과 같이 실행될 것이다.

  1. 5, 4가 현재 차례가 아니므로 스택에 들어간다.
  2. 1, 2, 3까지 올바른 순서이므로 간식을 받는다. 현재 차례(nowNum)은 4이다.
  3. 위의 구문을 통해 공간 가장 앞에 서 있는 사람(4)이 현재 차례라면 내보내고 다음 사람인 num(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" );
    }
}
profile
성장 기록 / 글에 오류가 있다면 댓글 부탁드립니다.
post-custom-banner

0개의 댓글