https://www.acmicpc.net/problem/3015
3015번: 오아시스 재결합
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람
www.acmicpc.net
결론부터 먼저 말하면 이 문제는 스택 활용이 필요하다. 어차피 검색을 했다면, 풀이가 필요했을 테니 스포일러가 아니리라 생각한다.
스택 활용 문제는 항상 쉽지 않다. 하지만 시간 복잡도를 O(N)으로 낮춰주는 대단히 강력한 방법이다.
O(N^2)이 보통 최악이라면, 그것을 O(NlogN)으로만 낮추어도 효율이 좋은 건데 O(N)은 사실상 최선의 방법이다.
적어도 모든 데이터를 한번씩은 봐야 하니깐.
문제의 예시를 보자.
2 4 1 2 2 5 1
위처럼 주어져 있다.
이 문제를 우리가 손으로 푼다면 보통 앞에서부터 한 숫자씩 따서 가능한 경우를 탐색해보게 된다.
왼쪽에서부터 한 숫자씩 선택해서 오른쪽 범위를 쭉 살펴보자.
탐색 시 매우 중요한 점은 A, B 사이에 A 또는 B 보다 큰 수가 없어야 한다는 것이다. <- 이 부분을 놓쳐서 애먹었다...
1. 가장 첫번째 숫자 2는 아래의 1가지 경우가 있다.
(2,4)
2. 두번째 숫자 4는 4가지.
(4,1) (4,2) (4,2) (4,5)
3. 세번째 숫자 1은 단 1가지
(1,2)
4. 네번째 숫자 2는 2가지
(2,2) (2,5)
5. 다섯번째 숫자 2는 1가지
(2,5)
6. 여섯번째 숫자 5는 1가지
(5,1)
다 합치면 10가지가 된다. 하지만 이렇게 본 방법은 O(N^2)이 된다. 각 숫자를 집어서 전 범위를 하나씩 다 보았기 때문이다. (오른쪽만 봤어도, 이런 식의 방식은 엔제곱으로 이해된다)
이를 개선하기 위해서는 당연히 탐색 범위를 줄여야 한다.
이전의 수보다 큰 수가 나왔을 때, 그 큰 수 다음 범위의 수들은 모두 배제할 수 있다는 사실에 착안하여야 한다.
즉, 2, 5, 3, 1라는 배열이 있다면, 첫번째 숫자 2는 5까지만 볼 수 있고, 그 후의 3과 1의 존재는 알 수 없다.
다시 말하면, 5가 나오는 순간 그 이전의 숫자들은 모두 버려도 되는 것이다.
스택으로 문제를 풀 때, 어려운 이유가 우리가 보통 간단하게 생각하는 방식의 순서를 이리저리 헤집어야 하기 때문이라고 생각한다.
스택은 뜻 그대로 값을 쌓는 자료구조이다. FILO (first in last out)이어서 가장 먼저 들어간 케이스 또는 값이 가장 마지막에 처리된다. 이는 레이지(lazy) 개념을 갖고 있다고도 이해할 수 있다. 먼저 할 수 있었던 연산을 미뤄두고 나중에 하는 것이다.
하지만 그를 통해, 각 수의 케이스 확인시 범위를 비약적으로 단축할 수 있는 것이다.
가장 먼저 두개의 수 2,4를 보자.
2 이후에 바로 4라는 수가 나오면서 2의 입장에서는 4이후의 숫자를 아무것도 볼 수 없게 되어 버렸다.
그래서 (2,4)의 케이스를 일단 카운트하고 2를 버리면 된다. 2는 뒤의 1 2 2 5 1과 비교할 필요조차 없는 것이다.
만약 3, 2, 1, 4 라는 배열이 주어졌다면?
3은 2를 볼 수 있고, 가장 마지막에 나오는 4도 볼 수 있다. 즉, 3은 마지막 4를 볼 때까지 버릴 수 없다.
3은 전체 범위를 모두 확인해야 하는 것이다. 왜 3은 전 범위를 봐야 할까. 4가 나올 때까지 자신보다 큰 수가 없었기 때문이다.
좀 더 자세히 살펴보면,
3과 2는 서로 볼 수 있어서 (3,2)를 카운트 할 수 있었지만 해당 처리를 일단 미뤄두고(lazy) 스택에 담는다. 그 다음 2와 1도 서로 볼 수 있지만 미뤄두고 다시 스택에 담는다. 1이 2보다 작기 때문에 2가 1을 넘어서 다른 사람을 더 볼 수 있는 가능성이 있기 때문이다.
이제 1보다 큰 수 4가 들어왔다. 이제 4가 왔기 때문에 1은 4를 넘어선 뒤의 사람들을 아무도 볼 수 없다. 즉 1은 이제 버려도 되는 것이다. 버리기 전에 그동안 계속 미뤄온 연산이 필요하다. (1,4)를 먼저 카운트 해준다. 그리고 1의 왼쪽인 2와 볼 수 있으므로 (2,1)을 카운트한다.
여기서 1은 자신의 왼쪽 범위를 전부 볼 필요가 없다. 이 스택은 모노톤이며 내림차순으로 자동 정렬되기 때문에, 자신의 바로 왼쪽 사람만 볼 수 있다. 그래서 (2,1)만 카운트하면 끝인 것이다.
1이 버려지고 나면 스택의 위에는 2가 보인다. 물론 2와 4는 서로 볼 수 있다 (2,4)를 카운트하고 마찬가지로 (3,2)가 카운트된다. 이런 식으로 큰 수가 들어오면 내림차순 정렬이 유지될 때까지 스택에서 뽑아 카운트 해주면 된다.
이 방법의 큰 강점은 탐색범위가 급격히 줄어듦에 있다. 3은 자신보다 작은 2, 1이 연달아 나오니 스택에 계속 담아서 4가 올 때까지의 탐색범위가 자동 조정된 것이다. 중간의 2는 1이 스택에서 빠질 때 (2,1)이 카운트되었고, 자신이 빠질 때 (2,4)와 (3,2)가 카운트되었다. 자연스럽게 자신이 볼 수 있는 범위만큼만 본 것이다.
이제 다 된 것 같지만, 한가지 더 생각해야 한다. 바로 같은 값이 포함된 경우이다.
4 2 2 1 1 을 예시로 보자.
두번째 2와 세번째 2 모두 첫번째 위치한 4를 볼 수 있다.
마찬가지로 세번째 2는 네번째 1과 다섯번째 1을 볼 수 있다.
하지만, 두번째 2는 네번째 1과 다섯번째 1을 볼 수 없다.
여기가 조심해야하는 부분이라고 생각한다. 문제의 조건에 의해 불가능 한 것은 알지만, 같은 수를 중첩시켜서 연산하는 식으로 로직을 짜다보면 실수할 수 있는 부분이다.
필자의 경우, 스택에 담을 때 숫자만 담지 않고, 숫자와 그 숫자가 몇개 중첩인지를 묶어서 담았다.
카운트해줄 때는 어차피 왼쪽의 1개만 볼 수 있으니 중첩만큼 카운트해주면 된다.
이제 다시 문제의 예시로 돌아오자.
2 4 1 2 2 5 1
내림차순 자동 정렬되는 모노톤 스택을 구성하고, 큰 수가 나왔을 때만 그 동안의 케이스들을 카운트하는 식으로 처리하면
- 2 들어옴
스택 [(2,1)]
카운트: 0
- 4 들어옴
2를 뽑아서 (2,4) 카운트 되고, 4가 쌓임
스택: [(4,1)]
카운트: 1
- 1 들어옴
4보다 작으므로 적립
스택: [(4,1),(1,1)]
카운트: 1
- 2 들어옴
스택의 가장 상단 1보다 크므로 처리 필요. 1을 pop
(1,2) 카운트 (4,1) 카운트
그 다음 4보다 작으므로 적립
스택:[(4,1), (2,1)]
카운트: 3
- 2 들어옴
스택의 상단 2와 같다. 여기서 중첩을 해준다. 앞서서 버린 1은 볼 수 없기에 문제 없다.
스택: [(4,1), (2,2)]
카운트: 3
- 5 들어옴
스택의 상단 2보다 크다. 2를 버린다.
(2,5) (2,5) 카운트된다. 실제로는 중첩값 2를 읽어서 카운트에 누적시키게 된다.
(4,2) (4,2) 카운트된다. 여기도 중첩값 2를 읽어서 카운트에 누적시키게 된다.
이때 (2,2)도 카운트된다. 같은 키를 가진 사람들은 서로서로 볼 수 있다.
2가 버려지고 남은 4도 5보다 작다. 이제 4도 버린다
(4,5)가 카운트된다.
스택: [(5,1)]
카운트: 9
- 1 들어옴
5보다 작으니 적립한다.
스택: [(5,1), (1,1)]
카운트: 9
모든 숫자를 순회했는데 스택에 값들이 남았다 (스택의 길이가 2이다. 1보다 크다)
1부터 순차적으로 버리면서 중첩값을 카운트에 더해준다.
(5,1)이 카우트 되었다
스택: [(5,1)]
카운트: 10
이제 여기서 끝인 것 같지만
만약 스택에 남은게 [(5,3)] 이었다면
5 5 5 의 상태이니 3개가 더 카운트될 수 있음에 유의해야 한다.
스택으로 문제를 풀 때, 어려운 이유가 우리가 보통 간단하게 생각하는 방식의 순서를 이리저리 헤집어야 하기 때문이라고 생각한다.
위에서 말한 내용을 반복하였다. 순서가 어떻게 달라졌는지 확인해보자.
가장 위에서 처음에 살펴본 손으로 대충 찾는 방식은
(2,4)
(4,1) (4,2) (4,2) (4,5)
(1,2)
(2,2) (2,5)
(2,5)
(5,1)
의 순서로 쌍을 찾았다.
하지만 스택 풀이에서는
(2,4)
(1,2) (4,1)
(2,5) (2,5)
(4,2) (4,2)
(2,2)
(4,5)
(5,1)
의 순서로 쌍을 찾았다.
당연히 손으로 찾을 때와 같은 케이스들이지만 순서가 상당히 다르다. 앞에서부터 하나씩 골라서 전범위를 살피지 않고, 이전에 수보다 클 때만 케이스가 카운트되기 때문이다. 그리고 그를 통해 탐색범위도 줄어드는 효과를 보게 되는 것이다.
<알고리즘>
스택
<코드>
const fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')
const calc = a => parseInt(a * (a + 1) / 2, 10)
input = input.map(e => parseInt(e, 10))
const n = input[0]
let c = 0
const st = []
for (let i = 0; i < n; ++i) {
const v = input[i + 1]
let top = st.length > 0 ? st[st.length - 1][0] : 2 ** 31
// 3 cases
// 1. same
if (top === v) {
st[st.length - 1][1]++
continue
}
// 2. smaller than st.top or st.length===0
if (top > v) {
st.push([v, 1])
continue
}
// 3. greather than st.top
while (top < v) {
const hold = st.pop()
c += hold[1]
c += calc(hold[1] - 1)
if (st.length === 0) break
c += hold[1]
top = st[st.length - 1][0]
}
if (st.length > 0 && st[st.length - 1][0] === v) st[st.length - 1][1]++
else st.push([v, 1])
}
while (st.length > 1) {
const hold = st.pop()
c += hold[1]
c += calc(hold[1] - 1)
}
c += calc(st[0][1] - 1)
console.log(c)
