[Baekjoon] 14540_Railway Station

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

---

< Railway Station >

 

문제 풀이 

 

Stack 2개를 활용하여 문제를 해결한다.

1) A 방향에서 들어오는 기차

2) 역 내부

 

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;
import java.util.StringTokenizer;

public class _14540_ { // Railway Station

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

		int n = 0;
	
		while ((n = Integer.parseInt(bf.readLine())) != 0) {
			String str = "";

			while (!(str = bf.readLine()).equals("0")) {
				st = new StringTokenizer(str);

				int[] result = new int[n];
				int idx = 0;
				for (int i = 0; i < n; i++) {
					result[i] = Integer.parseInt(st.nextToken());
				}

				Stack<Integer> stack = new Stack<>();
				Stack<Integer> temp = new Stack<>();
				for (int i = n; i > 0; i--) {
					stack.add(i);
				}

				boolean flag = false;
				while (idx < n) {
					if (!stack.isEmpty() && stack.peek() == result[idx]) {
						stack.pop();
						idx++;
					} else if (!temp.isEmpty() && temp.peek() == result[idx]) {
						temp.pop();
						idx++;
					} else {
						if (!stack.isEmpty()) {
							temp.add(stack.pop());
						} else {
							flag = true;
							break;
						}
					}
				}
				if (flag) {
					bw.write("No\n");
				} else {
					bw.write("Yes\n");
				}
			}
			bw.write("\n");
		}
		bw.flush();
	}
}

변수)
n : 기차 객차 개수
str : 임의의 순열
result : str을 배열로 저장
idx : result를 가리키는 index
stack : A방향에서 들어오는 객차 순서
temp : 역 내부에 있는 객차 순서
flag : 순열 만들 수 있는지 여부

 

기차 객차 개수가 0이 아닐 때까지 입력받아 다음 과정을 반복한다.

 

1) 0이 아닐 때까지 임의의 순열 입력받아 다음 과정을 반복한다.

1-1) 입력받은 임의의 순열을 배열 result에 저장한다.

1-2) Stack에 A방향에서 들어오는 객차 순서를 저장한다.

1-3) A방향에서 들어오는 객차를 살펴보며 result [idx]와 일치하면 pop 한다.

1-4) A방향에서 들어오는 객차와 일치하지 않고 역 내부에 있는 객차를 살펴보며 result [idx]와 일치하면 pop 한다.

1-5) 둘 다 일치하지 않고 A방향에서 들어오는 객차가 남아있다면 그 객차를 역 내부에 저장한다.

1-6) 둘 다 일치하지 않고 A방향에서 들어오는 객차가 남아있지 않다면 순열을 만들 수 없으므로 종료한다.

2) flag 여부에 따라 정답을 출력한다. 

---

---