[백준/JS] #18258 : 큐2 (head 인덱스를 이용한 효율적인 큐 구현)

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (하단 참고)

512 MB

122497

40533

32721

33.131%

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1 복사

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1 복사

1
2
2
0
1
2
-1
0
1
-1
0
3

 

 

---

 

첫 번째 풀이 (시간 초과)

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');
const commands = input.slice(1);
let queue = [];
let result = [];
commands.forEach((line) => {
    line = line.split(' ');
    if (line[0] === 'push') {
        queue.push(line[1]);
    } else if (line[0] === 'front') {
        result.push(queue[0] ?? -1);
    } else if (line[0] === 'back') {
        result.push(queue[queue.length - 1] ?? -1);
    } else if (line[0] === 'size') {
        result.push(queue.length);
    } else if (line[0] === 'empty') {
        result.push(queue.length ? 0 : 1);
    } else if (line[0] === 'pop') {
        result.push(queue.shift() ?? -1);
    }
})
console.log(result.join('\n'));

단순한데? 하면서 정말 단순하게 풀었는데, 시간 초과가 났다.

그 원인은 pop을 하는 경우에 queue.shift() 가 O(N)의 시간복잡도를 가지기 때문이었다.

shift는 pop과 반대로 배열의 첫 번째 요소를 제거+반환할 때 사용할 수 있는데, 맨 끝 요소를 제거하는 pop과 달리 첫 번째 요소를 제거하기 때문에 한 칸씩 인덱스가 밀리게 된다. 그래서 해당 분기문 내부를 다음과 같이 조금 수정해서 제출해 보았다.

 

두 번째 풀이 (메모리 초과)

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');
const commands = input.slice(1);
let queue = [];
let result = [];
commands.forEach((line) => {
    line = line.split(' ');
    if (line[0] === 'push') {
        queue.push(line[1]);
    } else if (line[0] === 'front') {
        result.push(queue[0] ?? -1);
    } else if (line[0] === 'back') {
        result.push(queue[queue.length - 1] ?? -1);
    } else if (line[0] === 'size') {
        result.push(queue.length);
    } else if (line[0] === 'empty') {
        result.push(queue.length ? 0 : 1);
    } else if (line[0] === 'pop') {
    	// 수정한 부분
        result.push(queue[0] ?? -1);
        queue = queue.slice(1);
    }
})
console.log(result.join('\n'));

shift()를 사용하는 대신 배열의 첫 번째 요소를 추출하고, slice()를 사용하여 그 다음 요소부터 끝까지 배열을 잘라내주었다. 

하지만 이번에는 메모리 초과가 났는데, slice()를 사용하면 새로운 배열을 복사해서 반환하기 때문이다.

고로 매번 pop을 할 때마다 배열 전체를 새로 생성하기 때문에 이전 배열이 메모리에 남게 되고, 이는 공간 복잡도를 높일 수 밖에 없다.

 

정답 풀이

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');
const commands = input.slice(1);
let queue = [];
let result = [];
let head = 0;
commands.forEach((line) => {
    line = line.split(' ');
    if (line[0] === 'push') {
        queue.push(line[1]);
    } else if (line[0] === 'front') {
        result.push(head < queue.length ? queue[head] : -1); // head가 배열 전체 길이보다 크거나 같을 수 없음
    } else if (line[0] === 'back') {
        result.push(head < queue.length ? queue[queue.length - 1] : -1);
    } else if (line[0] === 'size') {
        result.push(queue.length - head);
    } else if (line[0] === 'empty') {
        result.push(head >= queue.length ? 1 : 0);
    } else if (line[0] === 'pop') {
        result.push(head < queue.length ? queue[head++] : -1); // 첫 번째 요소 제거 후 head 인덱스 한 칸 이동
    }
})
console.log(result.join('\n'));

결국 head 인덱스를 생성하여 첫 번째 요소가 가리키는 위치를 하나씩 옮기는 방식을 택하였다.

이 방식으로 풀이하면 보다 효율적으로 큐를 구현할 수 있다.

 

 

백준 문제같은 경우

https://github.com/tony9402/baekjoon

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)

여기서 선별을 해서 풀어보려고 하는데, 해당 문제가 권장 추천 문제로 체크되어 있는 이유를 알 것 같았다.

해당 방식으로 앞으로 다른 대용량 큐 문제에서도 효과적으로 풀이할 수 있을 것 같다.