[Baekjoon] 10106_The Geneva Confection

문제(출처: https://www.acmicpc.net/problem/10106)

---

< The Geneva Confection >

 

문제 풀이 

 

Stack 두 개를 사용하여 lake와 branch에 적절히 이동시켜 순서대로 만들 수 있는지 구한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class _10106_ { // The Geneva Confection

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

		int t = Integer.parseInt(bf.readLine());

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			Stack<Integer> lake = new Stack<>();
			Stack<Integer> branch = new Stack<>();
			int cnt = 1;

			for (int j = 0; j < n; j++) {
				lake.add(Integer.parseInt(bf.readLine()));
			}

			boolean flag = false;
			while (!lake.isEmpty() || !branch.isEmpty()) {
				if (!branch.isEmpty() && branch.peek() == cnt) {
					branch.pop();
					cnt++;
				} else if (!lake.isEmpty() && lake.peek() == cnt) {
					lake.pop();
					cnt++;
				} else {
					if(lake.isEmpty()) {
						flag=true;
						break;
					}
					branch.add(lake.pop());
				}
			}
			
			if(flag) {
				bw.write("N\n");
			}else {
				bw.write("Y\n");
			}
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 개수
n : 기차 칸 수
lake, branch : Stack <Integer>
cnt : 현재 순서

 

테스트 케이스 수를 입력받아 테스트 케이스 수만큼 다음 과정을 반복한다.

 

1) 기차 칸 수를 입력받는다.

2) 기차 칸 수만큼 숫자를 입력받아 lake에 저장한다.

3) lake에 값이 있거나 branch에 값이 있을 때 다음 과정을 반복한다.

3-1) branch의 peek 값이 cnt와 일치한다면 pop, cnt+1

3-2) lake의 peek 값이 cnt와 일치한다면 pop, cnt+1

3-3) 둘 다 일치하지 않고 lake가 비어있다면 순서대로 완성할 수 없으므로 종료, lake가 비어있지 않다면 lake의 pop 한 값을 branch에 저장. 

4) flag가 true라면 N 출력, false라면 Y 출력

---

---