https://www.acmicpc.net/problem/24511
문제
입력
출력
수열 C의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.
풀이과정
문제를 꼼꼼히 읽어보며 이해를 하고나서 처음 들었던 생각은 카테고리의 이전 문제들과 크게 다를 바 없다고 생각했다. 왜냐하면 그저 queuestack의 작동이 어려운게 아닐뿐더러 그대로 따라가면 결과는 제대로 나오기 때문이다.
과연 그렇게 똑같이 쉽게 문제를 내었을까? 생각하자 아니나 다를까 시간제한이 1초였다. queuestack의 작동대로 따라간다면 시간 효율성은 O(N * M)이다. N의 최대 범위는 100,000이며 M의 최대 범위 또한 100,000이다. 무조건 시간제한에 걸리거나 메모리 초과에 걸릴터였다.
다른 수를 생각해야한다.
예제를 만들고 살펴보자.
예제 입력은 다음과 같다.
자료구조: 0 1 1 0
수열: 1 2 3 4
queuestack에 삽입할 원소 수열C: 2 4 7
자료구조와 해당 자료구조에 들어있는 숫자는 다음과 같다.
수열 C를 하나씩 삽입해보며 어떤 결과가 있는지 보자. 먼저 2를 삽입해보자.
무언가 패턴이 보인다. 이번엔 4를 삽입해보자.
잘보면 첫 번째 자료구조인 큐에서 pop한 원소가 마지막 자료구조까지 이어지는 것을 볼 수 있다. 마지막으로 7을 삽입해보자.
결론은, 스택 자료구조에 원소를 삽입하고 pop했을 때 이전 자료구조에서 pop한 원소랑 똑같다. 그러므로 스택 자료구조는 사실상 있으나마나라는 뜻이다. 그리고 다시 이미지를 보면 마지막에 pop되어져 나간 원소는 큐에 삽입되어있는 원소와 완전히 똑같다. 즉, 중간에 스택 자료구조가 포함되어 있어도 스택은 결과에 아무 영향을 주지 않으므로 마지막 pop 되어져 나간 원소는 큐에 들어있는 원소로 이루어져야한다는 뜻이다.
결과는 4, 1, 2이다. 이미지에서도 마지막 큐부터 첫 번째 큐까지 4, 1로 이루어져있고, 4, 1 순으로 pop 됐다. (2는 순열C가 삽입된 숫자이다.)
이를 이용하면 효율성을 O(N + M)만큼 줄일 수 있다.
다음은 풀이에 사용하기 위해 구현한 덱과 노드이다.
static class Custom{
Node firstNode;
Node lastNode;
Custom(){
firstNode = null;
lastNode = null;
}
public void add(int value){
Node node = new Node(value);
if( firstNode == null ){
firstNode = node;
lastNode = node;
}else{
node.nextNode = firstNode;
firstNode.previousNode = node;
firstNode = node;
}
}
public void addBack(int value){
Node node = new Node(value);
if( firstNode == null ){
firstNode = node;
lastNode = node;
}else{
node.previousNode = lastNode;
lastNode.nextNode = node;
lastNode = node;
}
}
public int pop(){
Node node = lastNode;
if( lastNode.previousNode != null ){
lastNode = lastNode.previousNode;
}else{
lastNode = null;
firstNode = null;
}
return node.value;
}
}
static class Node{
int value;
Node nextNode;
Node previousNode;
Node(int value){
this.value = value;
nextNode = null;
previousNode = null;
}
}
}다음은 제출한 풀이 코드이다.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 자료구조 개수 N
int N = Integer.parseInt(br.readLine());
// 0과 1로 이루어진 자료구조 선택 입력
StringTokenizer queueOrStacks = new StringTokenizer(br.readLine(), " ");
// i번 자료구조에 넣을 값
StringTokenizer values = new StringTokenizer(br.readLine(), " ");
// 덱
Custom dequeue = new Custom();
while( N-- > 0 ){
int queueOrStack = Integer.parseInt(queueOrStacks.nextToken());
int value = Integer.parseInt(values.nextToken());
// 만약 큐 자료구조라면
// 덱 뒤에 원소를 넣는다.
if(queueOrStack == 0)
dequeue.addBack(value);
}
// 삽입할 순열 길이
int M = Integer.parseInt(br.readLine());
// 순열 C
StringTokenizer cValues = new StringTokenizer(br.readLine(), " ");
// 삽입할 순열 길이만큼 반복
while( M-- > 0 ){
int value = Integer.parseInt(cValues.nextToken());
// 덱 앞에 원소를 넣는다.
dequeue.add(value);
// 덱 마지막 원소를 pop하고 출력한다.
sb.append(dequeue.pop()).append(" ");
}
System.out.println(sb.toString());
}