문제 url:
queuestack
문제:
🤔 문제 알아보기
문제를 이해하는 데, 조금 어려웠다. 10분동안 빡세게 몇번 읽으니 그나마 눈에 들어와 부랴부랴 코드 작성을 했는데, 코드 조차도 쉽지 않았던 것 같다.
문제를 주어진 tc를 이용해 같이 한번 살펴보자,
먼저 Queue 자료구조부터 살펴보자,
Queue는 FIFO 구조를 가진 자료구조로, 먼저온 것이 먼저 나오기 때문에
기존에 입력되어 있던, 1과 4가 나오는 것을 확인할 수 있다.
stack 자료구조를 살펴보면,
stack은 LIFO 구조를 가진 자료구조로, 나중에 들어온 것이 먼저 나가기 때문에
stack에 저장된 값은 기존값과 동일하다.
여기서 핵심이 바로, stack은 어떠한 상황이어도 기존값이 변경되지 않는다는 것인데!
즉, 우리는 stack을 굳이 확인할 필요없이 건너뛰면 된다는 얘기이다.
이 얘기는 나중에 밑에서 자세히 하고,
아무튼 2를 삽입했을 때 마지막 배열의 모습은 2, 2, 3, 1 리턴은 4 인것을 알 수 있다.
이제 이것을 2, 4, 7을 넣으면 4, 1, 2의 값을 확인할 수 있는데,
이걸 보니 무언가 떠오르지 않은가??
그렇다. 빨간원에 속한 4와 1 은 초기 배열에 존재했던 기존값이다. 이것이 순서대로 리턴되는 것을 볼 수 있는다.
또한 2,4,7은 입력해주는 입력값인데, 우리가 tc의 답을 보면 4, 1, 2인 것을 알 수 있다. 그러면, 여기서 2는 무엇인가?
바로 기존의 1 자리를 뺏었던 입력값 2인 것이다.
그리고, 가장 중요한 조건을 잘 봐야한다. 현재 시간제한, 메모리 제한이 있다.
시간제한이 1초에 N과 M은 100,000단위이다. 즉 O(n^2)이상은 사용할 수 없는 구조라는 것을 파악하고 들어가야 한다.
그러면 이제 문제를 풀 수 있다.
🐱👤 실제 코드
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
// Deque를 배열형태로 만들어, Deque안에 여러 자료구조가 존재할 수 있도록 함
Deque[] queuestack = new ArrayDeque[N];
// option_arr은 o과 1값을 받아 0은 큐, 1은 스택을 나타내기 위한 배열
int[] option_arr = new int[N];
// 자료구조 모습(0과 1)를 배열에 담는 로직
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
option_arr[i] = Integer.parseInt(st.nextToken());
}
//queuetack 배열안에 덱을 선언하여, 하나의 자료구조로써 사용하도록 함
//그런 다음, 입력값을 각 배열마다 삽입 (문제 조건에서 하나의 요소를 가진다고 했음)
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
queuestack[i] = new ArrayDeque();
queuestack[i].offer(Integer.parseInt(st.nextToken()));
}
//출력을 위한 result 덱 선언
//여기서, 기존에 설명했던, 자료구조가 큐일 경우 해당 값만 뽑아서 추가.
//해당 값은 추후, 마지막에 return값으로 나오기 때문(마지막에서 나오는 부분이라)
//offer로 오른쪽에서 진입,
Deque<Integer> result = new ArrayDeque<>();
for(int i = 0; i < N; i++) {
if(option_arr[i] == 0) {
result.offer((Integer) queuestack[i].poll());
}
}
int M = Integer.parseInt(br.readLine());
//삽입값 m을 result 덱에 넣는데, 단 해당 값은 삽입되는 값으로 왼쪽에서부터 넣는 값이니
//오른쪽에서 넣는 offer가 아닌 offerFirst를 사용
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
int value = Integer.parseInt(st.nextToken());
result.offerFirst(value);
// 조건에 맞게 출력,
// pollLast를 한 이유는 처음 큐에서 넣은 것이, stack구조로 나와야 하기 때문
sbd.append(result.pollLast() + " ");
}
System.out.println(sbd);
}
}
코드가 다소 난해하다. 나중에 코드 리팩토링 세션에서 정리된 모습으로 볼 수 있지만 주석을 읽어보면 조금은 이해가 될 것이다.
이를 그림으로 조금 더 표현해보겠다.
이렇게 나타낸 다음 조건에 맞게 출력,
이렇게 하면, 시간복잡도는 O(N + M)를 가질 수 있다.
🤢 코드 리팩토링
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
StringTokenizer st;
Deque<Integer> deque = new ArrayDeque<>();
int N = Integer.parseInt(br.readLine());
int[] option_arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
option_arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
int queue_value = Integer.parseInt(st.nextToken());
if(option_arr[i] == 0) {
deque.offer(queue_value);
}
}
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
int M_value = Integer.parseInt(st.nextToken());
deque.offerFirst(M_value);
sbd.append(deque.pollLast()).append(" ");
}
System.out.println(sbd);
}
}
이전 코드와 로직은 동일하지만, 조금 더 가독성이 좋게 만들어졌다.
또한, 덱안에 배열을 넣지 않고, 바로 풀면서 복잡성 역시 좋아졌다.
리팩토링한 결과, 메모리와 시간 부분에서 좋아진 모습을 볼 수 있다.
🤢 회고
먼저, 좋은점과 나쁜점이 있다.
좋은점은 나름 문제 이해도가 조금씩 상승하는 느낌을 받고 있다는 점과 본인이 이해한 바를 어느정도 코드화 시키는 능력이 상승했다는 점이다.
하지만 나쁜점은, 아직도 문제 조건에 맞춰서 메모리나 시간제한에 대한 대비가 많이 부족하다. 필자도 사실 O(N^2) 이상의 시간복잡도로 계산하면 안된다는 것을 알지만,
이를 줄이는 방법을 강구하지 못해 결국 타 블로그를 참조하여 이해하며 코드를 짯다
사실 해당 문제는 정확히 이해하지 못한 상태에 가까워서 조금 아쉽기도 하다.
근래 알고리즘 푸는 시간도 많이 들고, 외부적으로 시간도 부족한데 취업 생각까지 하니 막막함이 들긴 하지만, 기초가 튼튼하면 나중에 무너지지 않는다고 생각하며
계속 풀어보고자 한다.
해당 코드는 시간 초과가 난 코드이다. 보통 시간 초과가 난다면 아래와 같은 로직일 가능성이 높다고 생각한다.
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
Deque[] queuestack = new ArrayDeque[N];
int[] option_arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
option_arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
queuestack[i] = new ArrayDeque();
queuestack[i].offer(Integer.parseInt(st.nextToken()));
}
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
int value = Integer.parseInt(st.nextToken());
for(int j = 0; j < N; j++) {
if(option_arr[j] == 0) {
queuestack[j].offer(value);
value = (int) queuestack[j].poll();
}
else {
queuestack[j].offer(value);
value = (int) queuestack[j].pollLast();
}
}
sbd.append(value).append(" ");
}
System.out.println(sbd);
}
}
💜 참고자료
