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

12789번: 도키도키 간식드리미 (acmicpc.net)

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

 

 

풀이 과정 

 

처음에는 스택으로만 접근하다가 안풀려서 구글링 해보니 스택과 큐를 이용해서 풀이한 것을 확인함,,,

 

- 입장 순서를 지킬 수 있는지 판단하는 문제 

- Input 큐 :현재 줄 서 있는 곳 (입력 값 저장)

- wait 스택 :임시 대기 공간

- order : 간식을 받을 순서 

 

- input 배열에서 현재 order값이 나올 때까지 stack 배열로 push

- 현재 order 값이 나오면 pop

- stack 배열을 pop 했을 때 order과 같은 숫자가 나온다면 위 과정 반복

- order과 다른 숫자가 나온다면 "sad"출력 

- wait 스택이 비어 있다면, 모든 학생들이 입장 순서를 지켰음을 의미함으로 "Nice" 출력

 

 

Queue 컬렉션 프레임 워크 

 

[Java] 자바 Queue 클래스 사용법 & 예제 총정리 (tistory.com)

[Java] 자바 Queue 클래스 사용법 & 예제 총정리

 

- 먼저 들어간 자료가 먼저 나오는 FIFO(First In Frist out) 구조 

- 한쪽은 프런트(front)로 정하여 삭제 연산만 수행

- 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행 

 

import java.util.LinkedList; 
import java.util.Queue;

Queue<Integer>queue = new LinkedList<>();
Queue<String>queue = new LinkedList<>();

queue.add(1); //값 추가 
queue.offer(3); //값 추가 
queue.poll(); //queue에 첫 번째 값을 반환하고 제거, 비어 있다면 null
queue.remove(); //queue에 첫 번째 값 제거 
queue.clear(); //queue 초기화 

queue.peek(); //queue의 첫 번째값 참조

 

- 자바에서 큐는 LinkedList를 활용해서 생성해야 함 

- queue에 값을 추가하고 싶다면 add(value) 또는 offer(value) 메서드를 활용 

- 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴

- queue에서 값을 제거하고 싶다면 poll()이나 remove 메서드를 사용 

- poll() 메서드는 큐가 비어 있으면 null을 반환 

- pop을 하면 가장 앞쪽에 있는 원소의 값이 제거 됨 

- queue의 모든 요소를 제거하려면 clear() 메서드를 사용

 

 

정답 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
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));
        
        Queue<Integer>Input = new LinkedList<>();
        Stack<Integer>Wait = new Stack<>();
        
        int num = Integer.parseInt(br.readLine());
        int order = 1; 
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<num; i++)
        {
            Input.offer(Integer.parseInt(st.nextToken()));
        }
        
        while(!Input.isEmpty())
        {
            if(Input.peek() == order)
            {
                Input.poll();
                order++;
            }
            else if(!Wait.isEmpty() && Wait.peek() == order)
            {
                Wait.pop();
                order++;
            }
            else
            {
                Wait.push(Input.poll());
            }
        }
        
        while(!Wait.isEmpty() && Wait.peek() == order) {
            Wait.pop();
            order++;
        }
        
       
        if(Wait.isEmpty())
        {
            bw.write("Nice");
        }
        else
        {
            bw.write("Sad");
        }
        
        bw.flush();
        bw.close();
    }
}