[백준] 12789 _ 도키도키 간식드리미 (Java)

정답코드와 결론은 맨 아래에-!!

이 문제는 스택의 기본 원리는 이용한 문제이다.

문제 이해

[ 스택 이해 ]
스택 이해는 아래의 링크를 타고 다른 스택 문제 해결과정을 통해 이해하길 바란다.
https://velog.io/@nyezxxj/Java-%EB%B0%B1%EC%A4%80-28278-%EC%8A%A4%ED%83%9D-2

이 문제의 내용은 다음과 같다.
간식을 받으려 번호표를 받고 대기하는 사람들이 있다.
뒤죽박죽 섞여있는 사람들은 번호표 순서대로 줄 세우기 위해 스택 2개를 통해 줄을 바로 세운다.

순서대로 받을 수 있다면 "Nice"를, 순서대로 받을 수 없다면 "Sad"를 출력하면 된다.

---

주의 사항
[ 현재 줄 서있는 곳 ]은 스택 1, [ 한 명씩만 설 수 있는 공간 ]을 스택2 라고 할 때,
스택 2 -> 스택 1 의 이동은 불가능하다.

---

스택 여러개를 응용한 문제로, 아래의 단계별로 이해하면 도움이 될 것이다.

• 스택( line ) : [ 현재 줄 서있는 곳 ]에 해당하는 스택
• 스택( stack ) : [ 한 명씩만 설 수 있는 공간 ]에 해당하는 스택
• 스택( check ) : 마지막으로 순서가 맞는지 확인하기 위한 스택
• 배열( array ) : 처음에 입력받는 배열을 순서대로 입력받기 위해 사용되는 공간
• 문자열( str ) : 최종 출력할 문자열을 가지고 있는 공간

---

---

예제 입력을 바탕으로 설명하자면

1. 몇 개의 숫자가 입력될지를 먼저 입력받음 ( n )
2. n개의 숫자를 배열에 입력받음 ( 0 ~ 4 )
3. for문으로 배열을 4부터 반대로 스택(line)에 push한다.
4. for문으로 1부터 n까지 돌리면서 숫자(순서)를 고정.
   4-1. 안에 while문을 돌리며 입력받은 숫자와 고정된 숫자가 일치하는지 비교
   4-2. for문의 고정된 숫자(순서)와 while문의 비교하는 숫자가 동일하다면 check 스택에 넣기 + line 스택에서 pop하기
   4-3. while문 안의 비교하는 숫자는 line 스택의 숫자와 stack의 숫자로 나뉜다. (자세한 내용은 아래 코드와 함께 설명하겠음)
5. 예외 처리 -> str의 값을 "Sad"로 변경 (기본 값을 "Nice"로 설정)
6. 모든 과정이 끝났다면, 마지막으로 check 스택에 있는 값이 순서대로 push 되었는지 확인

코드 이해

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

  static Stack<Integer> line = new Stack<>();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    int n = Integer.parseInt(br.readLine());
    int[] array = new int[n];
    st = new StringTokenizer(br.readLine());

    // 배열에 받고 스택에 순서대로 넣는 과정
    for (int i = 0; i < n; i++) {
      array[i] = Integer.parseInt(st.nextToken());
    }

    for (int i = n - 1; i >= 0; i--) {
      line.push(array[i]);
    }

    System.out.println(solve(n));
  }

  public static String solve(int n) {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> check = new Stack<>();
    String str = "Nice";

    for (int i = 1; i <= n; i++) {
      int x = 0, y = 0;

      while (true) {
        if (!line.empty()) x = line.peek();
        if (!stack.empty()) y = stack.peek();

        if (i == y) {
          check.push(stack.pop());
          break;
        }

        if (i == x) {
          check.push(line.pop());
          break;
        }

        if (i < x) stack.push(line.pop());

        if ((line.empty() && !stack.empty()) && (i != y)) {
          str = "Sad";
          return str;
        }
      }
    }

    int x = check.pop();
    int y;
    for (int i = 1; i < n; i++) {
      y = check.pop();

      if (y > x) {
        str = "Sad";
        break;
      }
      x = y;
    }

    return str;
  }
}

코드를 크게 main 부분과 핵심 해결메소드(solve)로 나누었다.

공통(static) 부분

• line 스택 선언 : main 메소드와 solve 메소드에서 모두 사용

main 부분

1. 입력받는 BufferedReader, 숫자 배열을 구분해서 입력받기 위해 StringTokenizer 선언
2. 숫자 변수 n, 순서대로 숫자를 스택에 넣어주기 위한 배열 array 선언
3. StringTokenizer로 숫자배열 입력받기
4. n만큼 돌리면서 배열 한 자리씩 값 넣기
5. for문 조건을 4에서 0까지 거꾸로 돌리면서 line 스택에 넣기
6. solve 메소드 실행
7. 반환값을 출력

solve 메소드

1. 숫자의 개수를 사용하기 때문에 변수 n을 매개변수로 받음
2. 비교한 숫자를 넣어둘 스택 2개, stack check 선언
3. 반환할 문자열 선언 : 기본 값 "Nice", 예외 발생 시 "Sad"로 변경
4. for문을 1부터 n까지 돌리면서 순서값과 입력받은 line의 숫자를 비교해 순서대로 정렬
5. while문에서 line과 stack의 값을 하나씩 가져와서 비교
   5-1. line과 stack의 수를 하나씩 가져와 i와 비교하여 각 스택에 넣음
   5-2. 만약 line이 비어있으면서(&&) stack이 비어있지 않고(&&) i가 y(stack의 숫자)와 같지 않다면 반환값을 "Sad"로 바꾸기 + 바로 종료
6. 모든 과정이 잘 종료되었다면, check 값을 미리 하나 꺼내고 n-1번 돌면서 숫자가 앞 숫자보다 큰지(순서가 맞는지)를 비교
   6-1. 비교하다 순서가 안맞을 경우 반환값을 바로 "Sad"로 변경 후 반복문 탈출
7. 반환값을 main으로 반환

입력 예시

5
5 4 1 3 2

n = 5
array = 2 3 1 4 5
line = 5 4 1 3 2

---

main에서 line을 순서대로 넣는 것 까지 끝내고 solve 메소드 실행

• stack, check 스택은 비어있는 상태
• x : line의 값 하나 복사
• y : stack의 값 하나 복사

---

1-1. i = 1
1-2. line에 값이 있다면 ? x = 5
1-3. stack에 값이 있다면 ? y= 0
1-4. i인 1보다 5가 더 큼 = stack에 5 push

2-1. i = 1
2-2. line에 값이 있다면? x = 4
2-3. stack에 값이 있다면? y = 5
2-4. i인 1보다 5가 더 큼 -> 4도 더 큼 = stack에 4 push

3-1. i = 1
3-2. line 값 x = 1
3-3. stack 값 y = 4
3-4. i인 1과 y는 다름 / x는 같음 = line.pop() + break;

4-1. i = 2
4-2. line 값 x = 3
4-3. stack 값 y = 4
4-4. i인 2보다 y가 더 큼 -> x도 더 큼 = stak에 3 push

5-1. i = 2
5-2. line 값 x = 2
5-3. stack 값 y = 3
5-4. i인 2와 y는 다름 / x는 같음 = line.pop() + break;

6-1. i = 3
6-2. line 값 x = 없음
6-3. stack 값 y = 3
6-4. i인 3과 y가 같음 = stack.pop + break;

의 과정으로 4와 5까지 모두 끝난 후 "Nice"를 반환한다.

예외처리

[ 1 ]
만약 예제처럼 딱 맞는 값이 아니라 ex) 45312 가 들어왔다면
stack : 4 5
check : 1 2 3
의 상태에서 stack의 5가 무한반복을 자아낸다.
-> 이 경우의 예외처리로 만약 line은 모두 빼내고 && stack은 아직 남아있는 상태에서 비교하려는 순서(i)와 스택의 값(y)가 같지 않다면 "Sad"를 반환하도록 했다.

[ 2 ]
모두 잘 끝났다면 check를 한번 더 점검한다.
check : 1 2 3 4 5 순으로 들어가있을 경우 5부터 숫자가 빠지기 때문에(선입후출) for문을 통해 뒤에서부터 꺼내 비교해주어야 한다.
for문을 돌리기 전 값 하나를 미리 빼준 후 x에 넣어준다.
그리고 for문에서 y에 값을 하나 넣은 후 x > y가 성립하는지 확인한다.
만약 성립되지 않는다면 "Sad"를 반환하도록 한다.
+) 성립했다면 다음 단계에서 x = y로 대입하고 y는 다시 앞의 값을 꺼내서 비교하도록 한다.

한줄평

최적화보다는 문제를 푸는데에 집중해서 생각보다 코드가 길었다.

단계별로 코드를 바로 풀어내기 어렵다면 필기를 통해 단계를 정리한 후 코드로 구현해 보는 것을 추천한다.