문제이해
문제가 너무 길어서.. 간식 별로 안먹고싶어짐 ..
이 문제는 승환이 앞에 서 있는 학생들의 수를 입력받고, 그 다음 줄에는 학생들의 번호표를 입력받습니다.
이후, 번호순으로 간식을 받을 수 있는데 해당 순서에 해당하지 않으면, 추가 대기줄에 순서대로 들어간 이후, 나올땐 가장 최근에 들어간 사람부터 나옵니다.
현재 줄 서있는 곳에서 들어온 순서대로 값이 나가는것을 볼 수 있습니다.
즉, first in first out하여 비교 이후, 기준에 따라 중간 대기열에 넣을지 간식을 받을지 선택합니다.
중간 대기열은 다음과 같이 last in first out 하는것을 볼 수 있습니다.
입력
입력으로 승환이 앞에 서 있는 학생들의 수를 입력받은 이후, 학생들의 번호표를 순서대로 입력받습니다.
출력
승환이가 간식을 받을 수 있으면 Nice, 받을 수 없으면 Sad를 출력합니다.
문제접근
현재 대기열은 first in first out 하고 있으므로 Queue 자료구조를 사용해주었고, 중간 대기열은 last in first out하고 있으므로, Stack 자료구조를 사용해주었습니다.
입력값 파싱 및 저장
- 값의 입력을 위해 BufferedReader를 이용하였습니다.
- 입력받은 값을 Split() 메소드를 이용해 공백 기준으로 나누어 문자열 배열에 저장해주었습니다.
- 반복문을 이용해 정수형으로 변환해준 이후, queue에 저장해주었습니다.
solutions()
-
번호표의 비교를 위해 idx를 초깃값 1로 설정해주었습니다.
-
숫자가 처리되는 과정을 크게 보면, 현재 대기열을 처리한 이후, 중간 대기열에 남은 사람들에 대해 처리해주고 있는걸 확인할 수 있습니다.
-
편의를 위해 현재 대기열은 큐, 중간대기열은 스택이라고 설명하겠습니다.
위의 조건을 생각하여 두개의 while문을 작성해주었습니다.
while (!q.isEmpty()){
}
while (!s.isEmpty()){
}
- 현재 대기줄(큐)이 비어있지 않을 때
-
큐 처음 값이 idx와 같으면 큐에서 pop합니다.
큐의 다음 값을 위해 idx를 1 증가시켜줍니다. -
큐가 비어있지 않을때, 스택도 비어있지 않는 경우에 대해 처리해줍니다.
큐의 값이 idx와 불일치하는 경우, stack의 값을 확인해줘야 합니다.
-
stack의 값이 idx와 일치하는 경우, stack에서 pop해줍니다.
-
만약, 스택의 값이 idx가 아니고, 큐의 값도 idx이 아닌 경우, 큐의 값을 스택으로 옮겨주어야 합니다.
위의 과정을 고려하여 작성하면 코드는 아래와 같습니다.
while (!q.isEmpty()) { // 대기열이 비어있지 않을 때
if (q.peek() == idx) { // 대기번호와 큐의 값이 같은 경우
q.poll(); // 큐에서 값을 꺼냄
idx++;
} else if (!stack.isEmpty() && stack.peek() == idx) {
stack.pop();
idx++;
} else {
stack.push(q.poll());
}
}과정을 반복하다보면, queue는 비게 될 것 입니다.
- 현재 대기줄(큐)을 모두 처리 한 이후, 중간 대기줄(스택)에 남아있는 사람들에 대한 처리
stack이 비어있지 않은 경우에 대해 생각해봅시다.
-
스택의 last in 값과 idx를 비교한 이후, 그 값이 같다면 pop해야 할 것이고, 그렇지 않다면 간식을 받을 수 없습니다.
코드는 아래와 같습니다.while (!stack.isEmpty()) { if (stack.peek() == idx) { stack.pop(); idx++; } else { return "Sad"; }code
솔루션 코드는 아래와 같이 작성해주었습니다.
private static String solution(Queue<Integer> q) { Stack<Integer> stack = new Stack<>(); int idx = 1; // 현재 처리해야 할 인덱스 while (!q.isEmpty()) { if (q.peek() == idx) { q.poll(); idx++; } else if (!stack.isEmpty() && stack.peek() == idx) { stack.pop(); idx++; } else { stack.push(q.poll()); } } while (!stack.isEmpty()) { if (stack.peek() == idx) { stack.pop(); idx++; } else { return "Sad"; } } return "Nice"; }
code
전체 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue<Integer> q = new LinkedList<>();
String[] str = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
q.add(Integer.parseInt(str[j]));
}
System.out.println(solution(q));
}
private static String solution(Queue<Integer> q) {
Stack<Integer> stack = new Stack<>();
int idx = 1;
// 큐에 대한 처리
while (!q.isEmpty()) {
if (q.peek() == idx) {
q.poll();
idx++;
} else if (!stack.isEmpty() && stack.peek() == idx) // 둘다 비어있지 않을 경우 {
stack.pop();
idx++;
} else {
stack.push(q.poll());
}
}
// 스택에 대한 처리
while (!stack.isEmpty()) {
if (stack.peek() == idx) {
stack.pop();
idx++;
} else {
return "Sad";
}
}
return "Nice";
}
}
