[JAVA] 백준 16단계 스택, 큐, 덱
2024. 12. 22. 10:38ㆍ카테고리 없음
28278 스택2
나의 답) 1000ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
switch(x) {
case 1:
int y = Integer.parseInt(st.nextToken());
stack.push(y);
break;
case 2:
if (stack.empty()) {
sb.append("-1").append("\n");
} else {
sb.append(stack.pop()).append("\n");
}
break;
case 3:
sb.append(stack.size()).append("\n");
break;
case 4:
if (stack.empty()) {
sb.append("1").append("\n");
} else {
sb.append("0").append("\n");
}
break;
case 5:
if (stack.empty()) {
sb.append("-1").append("\n");
} else {
sb.append(stack.peek()).append("\n");
}
break;
}
}
System.out.print(sb);
}
}
나의 답2) 876ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
switch(x) {
case 1:
int y = Integer.parseInt(st.nextToken());
stack.push(y);
break;
case 2:
sb.append(stack.empty() ? "-1" : stack.pop()).append("\n");
break;
case 3:
sb.append(stack.size()).append("\n");
break;
case 4:
sb.append(stack.empty() ? "1" : "0").append("\n");
break;
case 5:
sb.append(stack.empty() ? "-1" : stack.peek()).append("\n");
break;
}
}
System.out.print(sb);
}
}
다른 사람의 답) 424ms
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
int N = nextInt(); // 명령의 수
int[] stack = new int[N];
int top = -1;
while (N-- > 0) {
int command = nextInt();
switch (command) {
case 1: // Push
stack[++top] = nextInt();
break;
case 2: // Pop
sb.append(top >= 0 ? stack[top--] : -1).append('\n');
break;
case 3: // Size
sb.append(top + 1).append('\n');
break;
case 4: // Empty
sb.append(top >= 0 ? 0 : 1).append('\n');
break;
case 5: // Top
sb.append(top >= 0 ? stack[top] : -1).append('\n');
break;
}
}
System.out.print(sb);
}
// nextInt(): System.in.read()를 이용한 입력 처리
static int nextInt() throws IOException {
int number = 0;
boolean isNegative = false;
int character = System.in.read();
// 공백과 개행 문자를 건너뜀
while (character <= ' ') {
character = System.in.read();
}
// 음수 처리
if (character == '-') {
isNegative = true;
character = System.in.read();
}
// 숫자 파싱
while (character >= '0' && character <= '9') {
number = number * 10 + (character - '0');
character = System.in.read();
}
return isNegative ? -number : number;
}
}
10773 제로
나의 답1) 212ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<>();
int res = 0;
int k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
int temp = Integer.parseInt(br.readLine());
if (temp == 0) {
res -= stack.peek();
stack.pop();
}
else {
stack.push(temp);
res += temp;
}
}
System.out.print(res);
}
}
나의 답2) 200ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<>();
int k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
int temp = Integer.parseInt(br.readLine());
if (temp == 0) {
stack.pop();
}
else {
stack.push(temp);
}
}
int res = 0;
for (int s : stack) {
res += s;
}
System.out.print(res);
}
}
9012 괄호
나의 답1) 108ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
String str = br.readLine();
while (str.contains("()")) {
str = str.replace("()", "");
}
sb.append(str.isEmpty() ? "YES" : "NO").append("\n");
}
System.out.print(sb);
}
}
나의 답2) 108ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
String str = br.readLine();
if (isValidParenthesis(str)) {
sb.append("YES").append("\n");
} else {
sb.append("NO").append("\n");
}
}
System.out.print(sb);
}
static boolean isValidParenthesis(String str) {
Stack<Character> stack = new Stack<>();
for (char ch : str.toCharArray()) {
if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}4949 균형잡힌 세상
나의 답1) 216ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
while (true) {
String st = br.readLine();
if (st.equals(".")) break;
StringBuilder filter = new StringBuilder();
for (char s : st.toCharArray()) {
if (s == '(' || s == ')' || s == '[' || s == ']') {
filter.append(s);
}
}
while (filter.indexOf("()") != -1 || filter.indexOf("[]") != -1) {
filter = new StringBuilder(filter.toString()
.replace("()", "")
.replace("[]", ""));
}
if (filter.length() == 0) sb.append("yes").append("\n");
else sb.append("no").append("\n");
}
System.out.print(sb);
}
}
[아이디어]
// () [] => 균형잡힌 문자열 여부 확인
1. 무한 반복 => '.' 입력받기 전까지 반복
2. 모든 문자 제거 후 () [] 묶음 반복해서 제거
3. if) 공백이면 yes 출력
4. else) no 출력
[추가로 공부할 것]
1. toCharArryay()
: String 문자열을 char형 배열로 바꿔서 반환해주는 메서드
2. indexOf()
: 특정 문자열이 존재하면 해당 인덱스를 반환하고, 없으면 -1을 반환한다.
나의 답2) 176ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
while (true) {
String st = br.readLine();
if (st.equals(".")) break;
if (isBalanced(st)) sb.append("yes").append("\n");
else sb.append("no").append("\n");
}
System.out.print(sb);
}
static boolean isBalanced(String str) {
Stack<Character> stack = new Stack<>();
for (char ch : str.toCharArray()) {
if (ch == '(' || ch == '[') {
stack.push(ch);
} else if (ch == ')') {
if (stack.isEmpty() || stack.peek() != '(') {
return false;
}
stack.pop();
} else if (ch == ']') {
if (stack.isEmpty() || stack.peek() != '[') {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}
[아이디어 - 스택을 이용한 풀이]
1. 문자열을 왼쪽에서 오른쪽으로 순회하며 괄호를 처리한다.
2. '(' 또는 '['는 스택에 push한다.
3. ')' 또는 ']'를 만나면 스택에서 짝이 맞는 여는 괄호를 pop한다.
4. if) 스택이 비어있거나 || 닫는 괄호가 나오거나 || 짝이 맞지 않는 경우 => no
5. 문자열 순회가 끝난 후, if) 스택이 비어있으면 => yes else) => no
12789 도키도키 간식드라마
나의 답) 116ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
Stack<Integer> stack = new Stack<>();
int flag = 1;
int n = Integer.parseInt(br.readLine());
int arr[] = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < n; i++) {
// 현재 대기열에서 처리
if (flag == arr[i]) {
flag++;
} else { // 스택에서 처리 가능하면 처리
while (!stack.isEmpty() && stack.peek() == flag) {
stack.pop();
flag++;
}
stack.push(arr[i]); // 현재 대기열을 스택에 넣기
}
}
while (!stack.isEmpty()) { // 스택의 남은 요소 처리
if (stack.peek() != flag) {
System.out.print("Sad");
return;
}
stack.pop();
flag++;
}
System.out.print("Nice");
}
}
18258 큐2
처음 답) 시간 초과
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
ArrayList<Integer> list = new ArrayList<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String com = st.nextToken();
switch(com) {
case "push":
int num = Integer.parseInt(st.nextToken());
push(list, num);
case "pop":
sb.append(pop(list)).append("\n");
case "size":
sb.append(size(list)).append("\n");
case "empty":
sb.append(empty(list)).append("\n");
case "front":
sb.append(front(list)).append("\n");
case "back":
sb.append(back(list)).append("\n");
}
}
System.out.print(sb);
}
static void push(ArrayList<Integer> list, int num) {
list.add(num);
}
static int pop(ArrayList<Integer> list) {
if (list.isEmpty()) return -1;
else return list.remove(0);
}
static int size(ArrayList<Integer> list) {
return list.size();
}
static int empty(ArrayList<Integer> list) {
if (list.isEmpty()) return 1;
else return 0;
}
static int front(ArrayList<Integer> list) {
if (list.isEmpty()) return -1;
else return list.get(0);
}
static int back(ArrayList<Integer> list) {
if (list.isEmpty()) return -1;
else return list.get(list.size() - 1);
}
}
시간 초과가 난 이유)
ArrayList를 큐로 사용했기 때문이다.
ArrayList의 remove(0) 메서드를 사용할 때, 첫 번째 요소를 제거하면서 나머지 요소들을 모두 한 칸씩 이동시키는 작업이 수행된다.
이로 인해 O(n)의 시간이 소요되며, 입력 크기가 클 경우 성능 문제가 발생한다.
해결 방법)
큐 연산을 효율적으로 처리하기 위해 LinkedList 또는 ArrayDeque를 사용해야 한다.
이들은 큐의 특성에 맞게 설계되어 있어, 앞에서 요소를 제거하거나 뒤에 있는 요소를 추가하는 작업이 O(1) 시간 복잡도로 처리된다.
수정된 나의 답) 1228ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
LinkedList<Integer> queue = new LinkedList<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String com = st.nextToken();
switch(com) {
case "push":
int num = Integer.parseInt(st.nextToken());
queue.add(num);
break;
case "pop":
sb.append(queue.isEmpty() ? -1 : queue.poll()).append("\n");
break;
case "size":
sb.append(queue.size()).append("\n");
break;
case "empty":
sb.append(queue.isEmpty() ? 1 : 0).append("\n");
break;
case "front":
sb.append(queue.isEmpty() ? -1 : queue.peek()).append("\n");
break;
case "back":
sb.append(queue.isEmpty() ? -1 : queue.peekLast()).append("\n");
break;
}
}
System.out.print(sb);
}
}
주요 메서드)
- queue.poll(): 큐의 가장 앞 요소를 제거하고 반환
- queue.peek(): 큐의 가장 앞 요소를 반환 (제거x)
- queue.peekLast(): 큐의 마지막 요소를 반환
시간 복잡도 분석)
- push: O(1)
- pop: O(1)
- size: O(1)
- empty: O(1)
- front: O(1)
- back: O(1)
2164 카드2
나의 답1) 168ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> queue = new LinkedList<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
queue.add(i + 1);
}
while(queue.size() > 1) {
queue.remove();
queue.offer(queue.poll());
}
System.out.print(queue.peek());
}
}
+) 처음에 while문의 조건을 (queue.size() == 1)로 설정하여 반복문이 실행되지 않는 문제가 발생
나의 답2) 168ms(최적화)
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Deque<Integer> deque = new ArrayDeque<>();
int n = Integer.parseInt(br.readLine());
for (int i = 1; i <= n; i++) {
deque.add(i);
}
while(deque.size() > 1) {
deque.pollFirst();
deque.offerLast(deque.pollFirst());
}
System.out.print(deque.peekFirst());
}
}
큐의 remove와 offer 작업은 내부적으로 비용이 발생한다.
따라서 이를 Deque로 구현하면 pollFirst()와 offerLast()를 사용하여 더 효율적으로 처리할 수 있다.
1. LinkedList 대신 ArrayDeque 사용
- LinkedList는 더 많은 메모리를 사용하여, 삽입/삭제 작업에서 상대적으로 느리다.
- ArrayDeque는 더 적은 메모리를 사용하여 더 빠르다.
2. 함수 호출 간소화
: pollFirst()와 offerLast()로 큐 작업이 더 명확하고 효율적이다.
나의 답3) 104ms(가장 최적화)
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int highestPowerOfTwo = Integer.highestOneBit(n);
int res = (n == highestPowerOfTwo) ? n : (n - highestPowerOfTwo) * 2;
System.out.print(res);
}
}
수학적 규칙 활용
해당 문제에서 카드의 마지막 값은 2의 거듭 제곱과 관련된 규칙을 따른다.
1. N이 2의 거듭 제곱이면 마지막 남는 카드는 N이다.
2. 그렇지 않으면, N에서 가장 큰 2의 거듭 제곱을 뺴고 그 값을 두 배로 만든 값이 마지막 카드이다.
1. 수학적 규칙으로 반복 작업 제거
- Integer.highesOneBit(n)로 가장 큰 2의 거듭 제곱을 빠르게 계산
- 시간 복잡도는 O(1)
2. 메모리 사용 감소
: 큐 자료구조를 사용하지 않아 메모리 절약
11866 요세푸스 문제0
나의 답1) 136ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= n; i++) {
queue.add(i);
}
sb.append("<");
while (!queue.isEmpty()) {
for (int i = 0; i < k - 1; i++) {
queue.add(queue.poll());
}
sb.append(queue.poll());
if (!queue.isEmpty()) {
sb.append(", ");
}
}
sb.append(">");
System.out.print(sb);
}
}
=> 큐 사용
시간 복잡도:
- 각 요소 제거에 O(1) (큐의 연산)
- 총 O(N×K)로 동작
나의 답2) 112ms (연결 리스트 사용)
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
sb.append("<");
int idx = 0;
while(!list.isEmpty()) {
idx = (idx + k - 1) % list.size();
sb.append(list.remove(idx));
if (!list.isEmpty()) {
sb.append(", ");
}
}
sb.append(">");
System.out.print(sb.toString());
}
}
시간 복잡도:
- O(N^2): k번째 요소를 제거하기 위해 각 단계에서 리스트를 순회
28279 덱2
나의 답1) 1056ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Deque<Integer> deque = new ArrayDeque<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String c = st.nextToken();
int temp;
switch (c) {
case "1":
temp = Integer.parseInt(st.nextToken());
deque.addFirst(temp);
break;
case "2":
temp = Integer.parseInt(st.nextToken());
deque.addLast(temp);
break;
case "3":
sb.append(!deque.isEmpty() ? deque.pollFirst() : -1).append("\n");
break;
case "4":
sb.append(!deque.isEmpty() ? deque.pollLast() : -1).append("\n");
break;
case "5":
sb.append(deque.size()).append("\n");
break;
case "6":
sb.append(deque.isEmpty() ? 1 : 0).append("\n");
break;
case "7":
sb.append(!deque.isEmpty() ? deque.peekFirst() : -1).append("\n");
break;
case "8":
sb.append(!deque.isEmpty() ? deque.peekLast() : -1).append("\n");
break;
}
}
System.out.print(sb);
}
}
나의 답2) 880ms(답1 개선)
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Deque<Integer> deque = new ArrayDeque<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int com = Integer.parseInt(st.nextToken());
switch (com) {
case 1:
deque.addFirst(Integer.parseInt(st.nextToken()));
break;
case 2:
deque.addLast(Integer.parseInt(st.nextToken()));
break;
case 3:
sb.append(deque.isEmpty() ? -1 : deque.pollFirst()).append("\n");
break;
case 4:
sb.append(deque.isEmpty() ? -1 : deque.pollLast()).append("\n");
break;
case 5:
sb.append(deque.size()).append("\n");
break;
case 6:
sb.append(deque.isEmpty() ? 1 : 0).append("\n");
break;
case 7:
sb.append(deque.isEmpty() ? -1 : deque.peekFirst()).append("\n");
break;
case 8:
sb.append(deque.isEmpty() ? -1 : deque.peekLast()).append("\n");
break;
}
}
System.out.print(sb);
}
}
최적화 방안
1. String 대신 int로 명령 처리
- 명령어를 String으로 처리하면 비교 시 추가적인 비용이 발생한다.
- 명령어를 숫자로 변환하여 처리하면 성능 향상이 가능하다.
2. 조건문 간소화
- deque.isEmpty() 검사를 중복적으로 사용하지 않도록 구조를 간소화한다.
3. StringTokenizer 최소화
- 일부 명령어(예: "5", "6")는 추가 입력값이 필요하지 않으므로, 불필요하게 st.nextToken()을 호출하지 않도록 최적화한다.
2346 풍선 터뜨리기
나의 답1) 152ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
List<Integer> values = new ArrayList<>();
Deque<Integer> deque = new ArrayDeque<>();
// 풍선 번호와 값을 초기화
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
deque.add(i); // 풍선 번호 저장
values.add(Integer.parseInt(st.nextToken())); // 풍선 값 저장
}
while (!deque.isEmpty()) {
// 현재 풍선 번호
int current = deque.pollFirst();
sb.append(current).append(" ");
if (deque.isEmpty()) break;
// 이동 값(현재 풍선의 값)
int move = values.get(current - 1);
if (move > 0) {
// 오른쪽으로 이동
for (int i = 1; i < move; i++) {
deque.addLast(deque.pollFirst());
}
} else {
// 왼쪽으로 이동
for (int i = 0; i < Math.abs(move); i++) {
deque.addFirst(deque.pollLast());
}
}
}
System.out.print(sb.toString().trim());
}
}
나의 답2) 152ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
Deque<int[]> deque = new ArrayDeque<>();
// 풍선 번호와 값을 초기화
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
int value = Integer.parseInt(st.nextToken());
deque.add(new int[]{i, value}); // 번호와 값을 함께 저장
}
while (!deque.isEmpty()) {
// 현재 풍선 번호와 이동 값 가져오기
int[] current = deque.pollFirst();
sb.append(current[0]).append(" ");
if (deque.isEmpty()) break;
int move = current[1];
if (move > 0) {
// 오른쪽으로 이동(move - 1번)
for (int i = 1; i < move; i++) {
deque.addLast(deque.pollFirst());
}
} else {
// 왼쪽으로 이동
for (int i = 0; i < Math.abs(move); i++) {
deque.addFirst(deque.pollLast());
}
}
}
System.out.print(sb.toString().trim());
}
}
24511 queuestack
나의 답1) 시간 초과
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int[] type = new int[n]; // 자료구조 타입 (0: 큐, 1: 스택)
int[] currentValues = new int[n]; // 각 자료구조의 현재 값
// 자료구조 타입 입력
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
type[i] = Integer.parseInt(st.nextToken());
}
// 초기 값 입력
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
currentValues[i] = Integer.parseInt(st.nextToken());
}
int m = Integer.parseInt(br.readLine()); // 삽입할 값의 개수
st = new StringTokenizer(br.readLine());
// 입력 값 C 처리
for (int i = 0; i < m; i++) {
int value = Integer.parseInt(st.nextToken()); // 현재 삽입 값
int processedValue = value;
// 자료구조를 순차적으로 처리
for (int j = 0; j < n; j++) {
int temp = currentValues[j]; // 현재 값 저장
currentValues[j] = processedValue; // 새로운 값 삽입
if (type[j] == 0) { // 큐 (FIFO)
processedValue = temp; // 기존 값 전달
} else { // 스택 (LIFO)
processedValue = currentValues[j]; // 방금 삽입된 값 전달
}
}
// 최종 값 기록
sb.append(processedValue).append(" ");
}
System.out.print(sb.toString().trim());
}
}
시간 초과의 원인)
for 루프 안에서 O(M x N)의 작업이 이루어지기 때문이다.
다른 사람의 답) 536ms
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[] typeArr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
typeArr[i] = Integer.parseInt(st.nextToken());
}
Deque<Integer> deque = new ArrayDeque<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(st.nextToken());
if (typeArr[i] == 0) {
deque.addLast(num);
}
}
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
br.close();
while (M-- > 0) {
int moveValue = Integer.parseInt(st.nextToken());
deque.addFirst(moveValue);
sb.append(deque.pollLast()).append(" ");
}
System.out.println(sb);
}
}