[Go] 백준 24511번 queuestack (queue)

문제

https://www.acmicpc.net/problem/24511

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 N이 주어진다. (1 <= N <= 1000000)

둘째 줄에 길이 N의 수열 A가 주어진다. i번 자료구조가 큐라면 Ai = 0, 스택이라면 Ai = 1이다.

셋째 줄에 길이 N의 수열 B가 주어진다. Bi는 i번 자료구조에 들어 있는 원소이다. (1 <= Bi <= 1000000000)

넷째 줄에 삽입할 수열의 길이 M이 주어진다. (1 <= M <= 100000)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M의 수열 C가 주어진다. (1 <= Ci <= 1000000000)

입력으로 주어지는 모든 수는 정수이다.

출력

수열 C의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

---

문제 풀이

문제 해석 및 계획

문제만 10번 읽었던 문제입니다. 문제를 이해하는 것이 가장 어려웠습니다. 

문제 해석은 이렇습니다.

번호 별 큐 혹은 스택에 원소는 1개입니다

예시에서 0 1 1 0 순서로 1 2 3 4가 들어있습니다.

초기상태

1번 (큐) 원소 : 1

2번 (스택) 원소 : 2

3번 (스택) 원소 : 3

4번 (큐) 원소 : 4

입력은 2 4 7이므로 2를 먼저 넣게 되면 

1번에 2 입력

1번은 1 2가 되고 선입 선출에 따라 1이 반환

2번에 반환된 1을 입력

2번은 2 1이 되고 선입 후출에 따라 1이 반환

3번에 반환된 1을 입력

3번은 3 1이 되고 선입 후출에 따라 1이 반환

4번에 반환된 1을 입력

4번은 4 1이 되고 선입 선출에 따라 4가 반환

따라서 

1번 (큐) 원소 : 2

2번 (스택) 원소 : 2

3번 (스택) 원소 : 3

4번 (큐) 원소 : 1

상황이 됩니다.

이러한 상황이 반복되는 문제입니다. 문제를 이해하고 나면 두 번째 줄의 입력에 따라 queue인 상황과 stack인 상황을 구분하고 stack의 경우 입력 후 출력이므로 0인 경우만 queue의 선입 선출로 요소가 바뀌게 하여 작업을 하여 시간을 줄이려고 하였습니다.

오답 노트

로직을 있는 그대로 작성을 하여 아래와 같은 답을 제출하였지만 시간초과로 실패하였습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var N int
	fmt.Fscan(reader, &N)

	checkQS := make([]int,N)
	for i:=0 ; i<N ; i++ {
		fmt.Fscan(reader, &checkQS[i])
	}

	elems := make([]int,N)
	for i:=0 ; i<N ; i++{
		fmt.Fscan(reader, &elems[i])
	}

	var M int
	fmt.Fscan(reader, &M)
	rstList := make([]int,M)
	for i:=0 ; i<M ; i++{
		var input int
		fmt.Fscan(reader, &input)
		for j:=0 ; j<N ; j++{
			if checkQS[j] == 0 {
				elems[j], input = input, elems[j]
			}
		}
		rstList[i] = input
	}
	for _, v := range rstList {
		fmt.Fprintf(writer, "%d ", v)
	}
}

정답

시간을 더 단축시키기 위하여 고민을 한 결과는 아래의 코드입니다.

문제를 어렵게 적어두어 헷갈리지만 queuestack은 결국 queue의 구조를 가집니다. Ai가 1인 경우는 선입 후출에 의하여 요소가 변하지 않기에 생략하고 Ai가 0인 경우만 작동합니다. 따라서 입력에 의하여 queuestack에 요소를 넣으면 1번에 들어있던 요소는 다음 queue로 전달되고 모든 queue를 순환하여 마지막 queue의 값이 결과로 반환되는 queue의 원리입니다. 따라서 queue와 같은 작업을 하는 Deque를 생성하여 문제를 해결하였습니다.

package main

import (
	"bufio"
	"container/list"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var N int
	fmt.Fscan(reader, &N)

	checkQS := make([]int,N)
	for i:=0 ; i<N ; i++ {
		fmt.Fscan(reader, &checkQS[i])
	}

	newDeque := list.New()
	for i:=0 ; i<N ; i++{
		var input int
		fmt.Fscan(reader, &input)
		if checkQS[i] == 0 {
			newDeque.PushFront(input)
		}
	}
	var M int
	fmt.Fscan(reader, &M)

	for i:=0 ; i<M ; i++{
		var input int
		fmt.Fscan(reader, &input)
		newDeque.PushBack(input)
		fmt.Fprintf(writer,"%d ", newDeque.Front().Value)
		newDeque.Remove(newDeque.Front())
	}
}

---

느낀 점

문제를 해석하는 능력과 자료구조의 원리, 두 가지의 능력이 모두 필요한 문제였습니다. 답을 알고 나면 쉽게 느껴지는 문제지만 문제 해석과 자료구조의 원리 중 하나라도 부족하면 해결이 안 되는 문제라고 생각됩니다. 항상 시간을 단축시키는 것이 어렵기에 이러한 문제를 통하여 다양한 로직을 생각해 내는 연습이 필요하다고 생각하였습니다.