엄청난 문제였다.
문제 이해를 하는데 있어서 꽤 오랜 시간이 걸렸고, 내가 작성한 코드가 시간 초과가 나서 애를 많이 먹었다.
결국, 나의 생각이 짧았던 것이었다.
문제풀이 들어가보겠새우..
우선 이 문제는 딱 보고 나서는 해석하기가 매우 힘들다.
간단히 정리를 해보겠다.
우선 첫째줄에 기본적으로 덱에 넣어햐 하는 수의 갯수N이 주어진다.
두번째줄에는 0이냐, 1이냐에 따라서 큐를 만들거나 스택을 만든다.
예를 문제에 주어진 것을 들자면,
1,2,3,4가 주어졌는데 0,1,1,0, 즉, 큐,스택,스택,큐 이다.
1은 큐에 저장
2는 스택
3도 스택
4는 큐
이렇게 저장을 하고
M개 만큼 주어진 수를 한개한개씩 순차적으로 (큐,스택,스택,큐)에 넣겠다는 뜻이다.
한개를 입력했을때 마지막에 뿅!하고 튀어나오는 수를 모아서 출력해달라!~~ 이런 문제이다.
장황한 것에 비하면 아주 간단한 문제이다. 이제 정답 코드를 보여주겠다.
정답 코드
package que;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Q6finalFinal {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer stQorS = new StringTokenizer(br.readLine());
Deque<Integer> QorS = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
QorS.offer(Integer.parseInt(stQorS.nextToken()));
}
StringTokenizer stInput = new StringTokenizer(br.readLine());
Deque<Integer> InputVal = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
int a = Integer.valueOf(stInput.nextToken());
if (QorS.pop() == 0) {
InputVal.offer(a);
}
}
int M = Integer.parseInt(br.readLine());
StringTokenizer CValue = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
InputVal.offerFirst(Integer.valueOf(CValue.nextToken()));
sb.append(InputVal.pollLast()).append(" ");
}
System.out.println(sb);
}
}
차근차근 설명을 해보겠다.
예제1번 코드를 예시로 설명하겠다.
우선 N을 입력받아준다.
그 다음, 큐냐 스택이냐를 판별해줄 수 있는 것을 QorS 라는 덱에 넣어준다.
QorS에는 <0,1,1,0>이 들어있다.
그 다음 숫자를 넣어줄 덱 InputVal을 만들어 준다.
이제 숫자를 넣어줄 차례인데, 이제 키포인트이다.
예시를 잘 따라내려가다보면, 결국엔 스택을 pop하면, 넣어준 값이 그대로 나오기때문에 스택은 이 문제연산에 아무런 영향도 주지 않는다는 것을 알 수 있다.
결국에 중요한 것은 큐를 pop 해줄때인데, 원래 큐에 들어있던 값이 밀려나면서 후순위에 있던 큐에 대입되게 된다.
결국 최종적으로는 맨 마지막 큐에 들어있던 값이 pop되면서 우리가 원하는 값이 나오게 되는것이다.
따라서 QorS의 값이 0(즉, 큐인경우)일 때만 InputVal을 대입해준 뒤,
CValue를 넣어주면 된다.
단, CValue를 넣으면
원래 들어있던 값이 pop되어서 뒤에 있는 큐에 대입되고,
그러면 또 원래 그 자리에 있던 값이 pop되어서 뒤에 있는 큐에 대입되고,
그러면 또 원래 그 자리에 있던 값이 pop되어서.........
계속계속 반복됨!!!
한개한개씩 밀려나면서
맨 마지막에 있던 값 한개가 뾱 하고
튀어나오는 것이라고 설명했으므로,
CValue를 무작정 offer해주는 것이 아니라,
offerFirst를 해줘야할 것이다.
그리고 StringBuilder에 대입해야하는것은 pollLast일 것이다.
이렇게 해서 시간초과가 나지 않고 풀어보았다!
이 밑에 두가지 코드는 내가 시간초과가 나면서 머리를 끙끙댔던 코드이다.
기록용(1)
package que;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Q6 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer stQorS = new StringTokenizer(br.readLine());
int[] arrQorS = new int[N];
for (int i = 0; i < N; i++) {
arrQorS[i] = Integer.parseInt(stQorS.nextToken());
}
StringTokenizer stInput = new StringTokenizer(br.readLine());
Deque<Integer> que = new ArrayDeque<>();
Deque<Integer> stk = new ArrayDeque<>();
int M = Integer.parseInt(br.readLine());
StringTokenizer CValue = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int inputVal = Integer.parseInt(stInput.nextToken());
if (arrQorS[i] == 0) {
que.offer(inputVal);
} else {
stk.offer(inputVal);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
int X = Integer.parseInt(CValue.nextToken());
for (int j = 0; j < N; j++) {
if (arrQorS[j] == 0) {
que.offer(X);
X = que.poll();
} else {
stk.offer(X);
X = stk.pollLast();
}
}
sb.append(X).append(" ");
}
System.out.println(sb);
}
}
큐와 스택이라는 이름의 덱을 두개를 만들었다.
QorS가 0이라면
큐에다가 X를 대입해주고 X에다가는 맨 앞에 값을 poll해준다. 다음차례의 연산을 시행해줘야하니..
만약 QorS가 1이라면
스택이므로 아무영향을 안끼치므로 그냥 X에다가 마지막에 있는 값을 pollLast해주면 아무영향이없다.
------------------------
라고 생각했지만 시간초과,,,, 당연하다., 범위가 100,000짜리 두개이니까...
결국에는 스택을 아예 머리에서 빼고 생각하면 되는 문제이지 않았나.
머리가 안 좋은 덕에 시간초과로 더 끙끙댔던 하루였다.
그럼에도 잘 배워갑니다
기록용(2)
package que;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Q6final {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer stQorS = new StringTokenizer(br.readLine());
Deque<Integer> QorS = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
QorS.offer(Integer.parseInt(stQorS.nextToken()));
}
StringTokenizer stInput = new StringTokenizer(br.readLine());
Deque<Integer> InputVal = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
InputVal.offer(Integer.valueOf(stInput.nextToken()));
}
int M = Integer.parseInt(br.readLine());
StringTokenizer CValue = new StringTokenizer(br.readLine());
int cnt = 0, X = 0;
StringBuilder sb = new StringBuilder();
int[] arr = new int[M];
int arrcnt = 0;
while (true) {
if (cnt == 0) {
X = Integer.parseInt(CValue.nextToken());
} else if (cnt == N) {
arr[arrcnt] = X;
if (arrcnt == M - 1) {
break;
}
arrcnt++;
X = Integer.parseInt(CValue.nextToken());
cnt = 0;
}
if (QorS.peek() == 0) {
InputVal.offer(X);
X = InputVal.poll();
cnt++;
} else {
InputVal.offer(InputVal.poll());
cnt++;
}
QorS.offer(QorS.poll());
}
for (int i : arr) {
sb.append(i).append(" ");
}
System.out.println(sb);
}
}
이건 그냥 혹시라도 포문을 두번 써서 그런가,,,,>?하고 while문으로 바꿔봤지만 다를거 있겠니???????
하하ㅏ하
앞으로도 머리 더 굴려보새우~
곧 실버1 찍새우~
더 발전된 새우로 돌아오겠새우~
'백준' 카테고리의 다른 글
| [백준]1260: DFS와 BFS (1) | 2025.07.17 |
|---|---|
| [백준]24060: 병합 정렬(재귀) (0) | 2025.03.06 |
| [백준]2346: 풍선 터뜨리기 , 덱 개념 (1) | 2025.01.20 |
| [백준]11866: 요세푸스 문제, 큐 정리 (0) | 2025.01.20 |
| [백준]4949: 균형잡힌 세상, 스택 문제풀이 (1) | 2025.01.19 |