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

문제 해석

• 문제는 보자마자 '아 복잡하겠다' 싶었는데 아니나 다를까 복잡하다.
• 하지만, 문제 설명이 잘되어 있어서 따로 더 설명은 필요할 것 같진 않았다.
• 해석은 아래와 같다.
• 첫번째 줄에 승환이가 앞에 서있는 학생들의 수(N)을 입력받고, 두번째 줄에는 1~N 순서로 앞에서 뒤 순서대로 주어진다.
  
  
• 위의 사진과 같이 받은 순서표대로 나와야하는데 스택 구조를 잘 생각해서 '한명씩만 설 수있는 공간'과 '현재 줄 서있는 곳'을 잘 왔다갔다하면서 뽑으면 된다.
• 즉 간단하게 말하자면 받아야할 순서면 받고 빠지고, 받아야할 순서가 아니면 일단 Stack에 대기하는 사람과 비교해보고, 그 사람도 순서가 아니면 Stack에 넣으면 된다.
• 승환이가 간식을 받을 수 있으면 "Nice"출력 아니면 "Sad"를 출력하면 된다.

코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); //승환이 앞에 서있는 학생 수

        int[] lineStack = new int[N]; //승환이 앞에 서있는 학생들의 수만큼 순서 저장하는 배열

        //승환이 앞에 서있는 모든 학생들의 번호표 앞 -> 뒤로 주어짐
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            lineStack[i] = Integer.parseInt(st.nextToken());
        }

        br.close();
        bw.write(solution(lineStack));
        bw.flush();
        bw.close();
    }

    //승환이가 받을 수 있는지 확인하여 결과(받을 수 있으면 Nice, 아니면 Sad)를 반환하는 메서드
    static String solution(int[] stack){
        int orderValue = 1; //첫번째로 뽑아야하는 값

        // 해당 값이 다를경우 임시로 저장할 stack
        Stack<Integer> tmpStack = new Stack<>();

        // stack.length : 승환이 앞에 있는 학생 수
        for(int i = 0; i < stack.length; i++){
            if(stack[i] != orderValue){ //찾는 번호가 아닐 경우
                //임시 저장공간이 비어있지 않으면서 가장 최근에 들어간 요소가 찾는 번호일 경우
                if(!tmpStack.isEmpty() && tmpStack.peek() == orderValue){
                    tmpStack.pop();
                    i--; //임시 저장소에 있었지 stack이라는 공간에 있었던 것은 아니므로 한번더 반복해야한다.
                    orderValue++;
                }else{ //찾는 번호가 아닐 경우 임시저장소에 넣는다
                    tmpStack.push(stack[i]);
                }
            }else{ //찾는 번호일 경우
                orderValue++; //찾을 다음 번호로 넘어간다.
            }
        }

        boolean result = true; //결과 유효성 검사

        //stack.length를 다 비우고, 임시저장소는 비어있지 않을 수 있다.
        for(int i = 0; i < tmpStack.size(); i++){
            int tValue = tmpStack.pop(); //임시저장소에 최근에 들어간 번호

            if(tValue == orderValue){ //찾으려는 번호 이어서 저장
                orderValue++;
            }else{ //찾으려는 번호가 아니면 나오는 순서가 맞을 수 없으므로
                result = false;
                break; //더이상 반복X
            }
        }

        return result ? "Nice" : "Sad";
    }
}
        

• 코드 설명은 주석으로 작성해 두었으니 따로 설명은 생략하겠다.

결과

느낀 점

• 오랜만에 알고리즘을 풀어서 그런지 꽤 많이 헤맸다😩