Algorithm - 백준 도키도키 간식드리미(자료구조, 스택)

 

 

 

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

 

 

오늘도 여러 문제를 풀었다.

위의 문제는 스택과 같은 자료구조를 이용해서 해결하는 문제였다.

나는 Queue와 Stack을 이용하여 문제를 해결하려고 마음먹었다.

최근에 자료구조 문제들을 많이 풀어서 쉬울줄 알았지만, 위의 문제가 생각보다 쉽게 해결되지 않았다.

 

import java.util.*;

public class Main {
  public static void main(String[] args) {
  
   ...
   
    while (!queue.isEmpty()) {
      // 맨 앞의 사람의 번호
      int currentNumber = queue.poll();

      // 맨 앞사람의 번호가 가장 빠른 번호일 경우
      if (currentNumber == min) {
        min++;
      }

      // 기존줄의 맨 앞사람의 번호가 가장 빠른 번호가 아니며, 대기줄에 사람이 없는 경우
      else if(stack.isEmpty()){
        stack.push(currentNumber);
      }

      // 기존줄의 맨 앞사람의 번호가 가장 빠른 번호가 아니며, 대기줄에 사람이 있는 경우
      else {
        while (!stack.isEmpty()) {
          // 대기줄의 가장 앞에있는 사람이 가장 빠른 순번일 경우
          if (stack.peek() == min) {
            min++;
            stack.pop();
          }

          // 기존의 줄과 대기줄의 가장 앞에있는 사람이 가장 빠른 순번이 아닐 경우
          else {
            stack.push(currentNumber);
            break;
          }
        }
      }
    }

    //처음 줄에 사람이 없을 경우, 대기줄 사람 체크
    ...

 

 

몇시간 정도 헤매고 난 후, 도저히 감이 잡히지 않아 다른 사람들의 풀이를 확인했다.

대부분 Queue 대신 Array를 사용하였다.

코드를 한줄씩 비교하다 보니 문제점을 알 수 있었다.

 

        int currentNumber = queue.poll();
        ...
        while (!stack.isEmpty()) {
          // 대기줄의 가장 앞에있는 사람이 가장 빠른 순번일 경우
          if (stack.peek() == min) {
            min++;
            stack.pop();
          }

 

기존의 코드 31 ~ 36번째줄에서 문제가 발생했다.

Stack(대기줄)의 가장 앞사람이 가장 빠른 순번을 가지게 될 경우, 

Queue를 사용하여 꺼낸 현재의 값, 즉 기존 줄에서 가장 앞에있던 사람이 사라지게 되는것이었다.

 

 

 if(!stack.isEmpty() && stack.peek() == getFoodOrder) {
                    stack.pop();
                    i--;
                    min++;

 

Array를 사용하여 문제를 해결한 사람들의 경우 Stack에 가장 빠른 순번의 사람이 있을 때, 

for문의 i의 값을 하나씩 빼주어 기존 줄에 가장 앞의 사람을 한번 더 조회할 수 있도록 코드를 작성되어있었다.

 

나는 Queue로 구현하고 싶었기에, 

값을 꺼낼 때 poll이 아닌 peek을 써서 값을 확인한 후, 조건에 따라 poll을 사용하여 값을 빼는 형식으로 구현했다. 

import java.util.*;

public class Main{

  public static void main(String [] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int student[] = new int [N];
    Queue<Integer> queue = new LinkedList<>();
    for(int i=0;i<N;i++) {
//      student[i] = sc.nextInt();
      queue.add(sc.nextInt());
    }
    int min = 1;
    Stack<Integer>stack = new Stack<>();
    while (!queue.isEmpty()){
      int currentNumber = queue.peek();
      if(currentNumber != min){
        if(!stack.isEmpty() && stack.peek() == min){
          stack.pop();
          min++;
        }
        else {
          stack.push(queue.poll());
        }
      }
      else {
        queue.poll();
        min++;
      }
    }
    boolean answer = true;

    for(int i = 0; i < stack.size(); i++) {
      int stu = stack.pop();
      if(stu == min) {
        min++;
      }else {
        answer = false;
        break;
      }
    }
    String result = answer ? "Nice" : "Sad";
    System.out.println(result);

  }
}

 

아직 자료구조에 대해 많이 서툰것 같다.

더 많은 문제를 풀어 익숙해질 수 있도록 해야겠다.