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

 

 

https://www.acmicpc.net/problem/12789

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

 

 

---

 

package dataStructure;

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

public class Ex12789 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n= Integer.parseInt(br.readLine()); 
		Stack<Integer> stack= new Stack<>();
		
		String s= br.readLine(); 
		StringTokenizer st= new StringTokenizer(s);
		int cnt=1;
		
		for(int i=0;i<n;i++) {
			int num= Integer.parseInt(st.nextToken());
			if(num==cnt) {
				cnt++;
				while(!stack.isEmpty()&&cnt==stack.peek()) {
					stack.pop();
					cnt++;
				}
			}else {
				stack.add(num);
			}
		}
		
		
		if(cnt==n+1) {
			System.out.println("Nice");
		}else {
			System.out.println("Sad");
		}
	}

}

 

 

- 현재 줄서있는 곳에서 차례대로 한명씩 데려와서 번호 체크

- cnt 라는 변수를 둠으로써, 번호를 체크(1로 초기화)

- stack: 한명씩만 설수있는 공간

 

1. cnt와 현재 줄서있는 곳에서 데려온 사람 번호가 다르면, stack에 추가

2. 같으면, 간식받는 곳으로 보냄 -> cnt ++

-> stack에 다음수(cnt)가 있는 지 점검(while을 사용해 반복)

stack.peek() (스택의 맨 위의 수)가 cnt와 같으면, 간식받는 곳으로 보냄, stack.pop()실행(스택에서 꺼내기), cnt++

3. 스택 peek에 cnt가 같지않으면 다시 현재 줄서있는 곳에서 데려옴

4. 위를 반복한다.

5. 다 돌고난 뒤, cnt값이  n+1(갯수+1, 마지막에 한번 더 더했기 때문)과 같으면 승환이가 간식을 받음