문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/67258
난이도 : Level 3
프로그래머스 - 보석 쇼핑
문제 요약
진열대에 여러 종류의 보석이 순서대로 놓여 있다.
이때 모든 종류의 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아야 한다.
조건은 다음과 같다.
- 진열대 번호는 1번부터 시작한다.
- 모든 보석 종류를 하나 이상 포함해야 한다.
- 가장 짧은 구간을 return 한다.
- 가장 짧은 구간이 여러 개라면 시작 번호가 가장 작은 구간을 return 한다.
처음 접근: 완전탐색
처음에는 단순하게 생각했다.
각 시작점에서 출발해서, 모든 보석 종류가 나올 때까지 오른쪽으로 탐색하면 되지 않을까?
즉, i = 0부터 시작해서 모든 보석이 모일 때까지 오른쪽으로 이동하고,
그다음 i = 1에서 다시 같은 과정을 반복하는 방식이다.
초기 코드는 아래와 같았다.
JavaScript
function solution(gems) {
const set = new Set(gems)
// { 'DIA', 'RUBY', 'EMERALD', 'SAPPHIRE' }
const gemTypeCount = set.size
// 4
const list = []
for (let i = 0; i < gems.length - gemTypeCount; i++){
const temp_set = new Set(gems)
let start = i
let count = 0
let index = i
while (temp_set.size !== 0 && index < gems.length){
count += 1
temp_set.delete(gems[index])
index++
}
if (temp_set.size === 0){
let end = start + count - 1
let length = end - start
list.push([[start+1,end+1],length])
}
}
// list = [ [[1,7],6], [[2,~],~ ], [[3,~], ~ ] ... ]
// minLength 찾고 그 시점 start,end 저장하기
let minLength = Infinity
for (const [[start, end], length] of list) {
minLength = Math.min(minLength,length)
}
const cand = []
for (const [[start, end], length] of list) {
if (length == minLength){
cand.push(([start,end]))
}
}
cand.sort((a,b) => a[0] - b[0])
return cand[0]
}Python
def solution(gems):
gem_set = set(gems)
# {'DIA', 'RUBY', 'EMERALD', 'SAPPHIRE'}
gem_type_count = len(gem_set)
# 4
result_list = []
for i in range(len(gems) - gem_type_count):
temp_set = set(gems)
start = i
count = 0
index = i
while len(temp_set) != 0 and index < len(gems):
count += 1
temp_set.discard(gems[index])
index += 1
if len(temp_set) == 0:
end = start + count - 1
length = end - start
result_list.append([[start + 1, end + 1], length])
# result_list = [ [[1,7],6], [[2,~],~ ], [[3,~], ~ ] ... ]
# minLength 찾고 그 시점 start,end 저장하기
min_length = float("inf")
for (start_end, length) in result_list:
min_length = min(min_length, length)
cand = []
for (start_end, length) in result_list:
if length == min_length:
cand.append(start_end)
cand.sort(key=lambda x: x[0])
return cand[0]정확성 테스트 일부는 통과했다.
하지만 효율성 테스트는 전부 시간 초과가 났다.
왜 시간 초과가 났을까?
처음에는 gems의 길이가 최대 100,000이니까, 완전탐색도 어느 정도 가능하지 않을까 생각했다.
하지만 이 생각에는 문제가 있었다.
현재 코드는 각 시작점마다 다시 오른쪽으로 탐색한다.
예를 들어 배열 길이가 100,000이라면 최악의 경우 다음과 같이 탐색할 수 있다.
i = 0일 때 0부터 끝까지 탐색
i = 1일 때 1부터 끝까지 탐색
i = 2일 때 2부터 끝까지 탐색
...
i = 99999일 때 끝까지 탐색즉 전체 탐색 횟수는 대략 다음과 같다.
100000 + 99999 + 99998 + ... + 1이는 결국 O(n²)이다.
n = 100,000이면 최악의 경우 수십억 번에 가까운 연산이 발생할 수 있다.
게다가 초기 코드에서는 반복문 안에서 매번 새로운 Set을 만들고 있었다.
const temp_set = new Set(gems)이 코드도 gems 전체를 순회해야 하므로 O(n)이다.
이것을 바깥 반복문마다 실행하면 이 역시 O(n²)에 가까운 비용이 된다.
즉, 시간 초과의 핵심 원인은 다음과 같다.
- 각 시작점마다 오른쪽을 다시 탐색한다.
- 매번
new Set(gems)를 만든다. - 전체적으로
O(n²)구조가 된다.
그럼 어떤 방향으로 가야 할까?
이 문제는 연속 구간을 다루는 문제다.
그리고 조건은 다음과 같다.
모든 보석 종류를 포함하는 가장 짧은 연속 구간을 찾아라.
이런 문제에서는 보통 투 포인터 또는 슬라이딩 윈도우를 생각할 수 있다.
완전탐색은 매 시작점마다 오른쪽을 다시 탐색한다.
반면 투 포인터는 현재 구간을 유지하면서 left, right를 한 방향으로만 이동시킨다.
투 포인터 아이디어
투 포인터의 핵심은 다음과 같다.
right를 늘리면서 보석을 현재 구간에 추가한다.
모든 보석 종류가 모이면 left를 당기면서 구간을 줄인다.
줄이다가 모든 보석 종류를 만족하지 못하면 다시 right를 늘린다.즉, 흐름은 다음과 같다.
right를 오른쪽으로 이동하면서 보석을 담는다.- 현재 구간이 모든 보석 종류를 포함하면 정답 후보가 된다.
- 그 상태에서
left를 오른쪽으로 이동시키며 구간을 줄인다. - 줄이다가 어떤 보석이 빠져서 모든 종류를 포함하지 못하면 멈춘다.
- 다시
right를 이동한다.
이 방식에서는 left와 right가 각각 배열을 한 방향으로만 이동한다.
따라서 시간복잡도는 O(n)이 된다.
최종 코드
JavaScript
function solution(gems) {
const gemTypeCount = new Set(gems).size
const map = new Map()
let left = 0
let answer = [1, gems.length]
let minLength = Infinity
for (let right = 0; right < gems.length; right++) {
const rightGem = gems[right]
map.set(rightGem, (map.get(rightGem) || 0) + 1)
while (map.size === gemTypeCount) {
const currentLength = right - left
if (currentLength < minLength) {
minLength = currentLength
answer = [left + 1, right + 1]
}
const leftGem = gems[left]
map.set(leftGem, map.get(leftGem) - 1)
if (map.get(leftGem) === 0) {
map.delete(leftGem)
}
left++
}
}
return answer
}Python
def solution(gems):
gem_type_count = len(set(gems))
gem_count = {}
left = 0
answer = [1, len(gems)]
min_length = float("inf")
for right in range(len(gems)):
right_gem = gems[right]
if right_gem in gem_count:
gem_count[right_gem] += 1
else:
gem_count[right_gem] = 1
while len(gem_count) == gem_type_count:
current_length = right - left
if current_length < min_length:
min_length = current_length
answer = [left + 1, right + 1]
left_gem = gems[left]
gem_count[left_gem] -= 1
if gem_count[left_gem] == 0:
del gem_count[left_gem]
left += 1
return answer투 포인터는 왜 모든 경우를 놓치지 않을까?
투 포인터 풀이를 처음 보면 조금 찝찝할 수 있다.
left와 right가 둘 다 한 방향으로만 이동하는데, 정말 모든 경우를 놓치지 않는 걸까?
나도 처음에는 이 부분이 잘 안 믿겼다.
완전탐색은 모든 시작점과 끝점을 직접 확인한다.
반면 투 포인터는 right를 늘리고, 조건을 만족하면 left를 당기는 방식으로 진행한다.
그래서 이런 의문이 들 수 있다.
중간에 확인하지 않고 지나쳐버린 구간 중에 정답이 있으면 어떡하지?
이 문제에서 투 포인터가 가능한 이유
보석 쇼핑 문제의 조건은 다음과 같다.
현재 구간 안에 모든 보석 종류가 하나 이상 들어있는가?
이 조건은 방향성이 있다.
right를 오른쪽으로 이동하면 구간에 보석이 추가된다.
right 이동 → 보석 추가 → 조건을 만족할 가능성이 커짐반대로 left를 오른쪽으로 이동하면 구간에서 보석이 제거된다.
left 이동 → 보석 제거 → 조건을 잃을 가능성이 있음즉, 이 문제는 다음과 같은 성질을 가진다.
right를 늘리면 조건을 만족하기 쉬워진다.
left를 늘리면 조건을 만족하기 어려워진다.이 성질 때문에 투 포인터를 사용할 수 있다.
right가 하는 일
right는 현재 구간을 확장하는 역할을 한다.
아직 모든 보석 종류가 모이지 않았다면, 구간을 더 넓혀야 한다.
따라서 right를 오른쪽으로 이동시킨다.
보석 종류가 부족하다 → right 이동right가 이동하면서 새로운 보석이 구간에 들어오고, 언젠가 모든 보석 종류가 모이면 현재 구간은 정답 후보가 된다.
left가 하는 일
모든 보석 종류가 모였다고 해서 바로 그 구간이 정답은 아니다.
더 짧은 구간이 있을 수 있다.
그래서 그 순간부터는 left를 오른쪽으로 이동시키며 구간을 줄여본다.
모든 보석 종류가 있다 → left 이동이때 중요한 점은, left를 이동하기 전의 구간은 모두 정답 후보로 확인한다는 것이다.
예를 들어 현재 구간이 모든 보석을 포함하고 있다면,
[left ... right]이 구간은 일단 정답 후보가 된다.
그다음 left를 한 칸 이동해도 모든 보석이 남아 있다면,
[left + 1 ... right]이 구간도 정답 후보가 된다.
이 과정을 반복하다가, 어떤 보석의 개수가 0이 되어 모든 보석을 포함하지 못하는 순간 멈춘다.
즉, 특정 right에 대해 가능한 유효 구간들은 while문 안에서 left를 이동시키며 확인하게 된다.
한 번 지나간 left를 다시 볼 필요가 없는 이유
투 포인터에서 가장 중요한 부분은 left를 다시 왼쪽으로 되돌리지 않는다는 점이다.
처음에는 이 부분이 가장 의심스러웠다.
하지만 한 번 버린 left는 다시 볼 필요가 없다.
예를 들어 [0, 3] 구간을 이미 확인했다고 하자.
이후 right가 더 오른쪽으로 이동하면 [0, 4], [0, 5] 같은 구간이 생길 수 있다.
하지만 이 구간들은 [0, 3]보다 더 길다.
[0, 3] 길이 4
[0, 4] 길이 5
[0, 5] 길이 6우리는 가장 짧은 구간을 찾고 있다.
따라서 이미 확인한 left를 그대로 둔 채 right만 더 늘린 구간은 정답이 될 가능성이 낮다.
만약 [0, 3]이 이미 조건을 만족했다면, [0, 4]는 더 긴 구간일 뿐이다.
그래서 다시 left = 0으로 돌아갈 필요가 없다.
예시로 보기
예를 들어 보석 배열이 다음과 같다고 해보자.
["A", "B", "A", "C", "B"]전체 보석 종류는 A, B, C이다.
처음에는 right를 이동시키며 보석을 모은다.
[A, B, A, C]
L R이 시점에서 모든 보석 종류가 모였다.
현재 구간 [0, 3]은 정답 후보가 된다.
이제 left를 오른쪽으로 이동시키며 더 짧은 구간을 찾아본다.
맨 왼쪽 A를 제거해도 아직 구간 안에 A가 하나 더 남아 있다.
[B, A, C]
L R이 구간 [1, 3]도 모든 보석을 포함한다.
따라서 정답 후보가 된다.
이제 다시 left를 이동해 B를 제거하면,
[A, C]
L RB가 사라지므로 더 이상 모든 보석을 포함하지 못한다.
이 순간 while문을 멈추고, 다시 right를 이동시킨다.
다음으로 right가 마지막 B까지 이동하면,
[A, C, B]
L R다시 모든 보석이 모인다.
그러면 또 left를 이동시키며 구간을 줄여본다.
이런 식으로 right는 부족한 보석을 채우는 역할을 하고,
left는 조건을 만족하는 동안 구간을 줄이는 역할을 한다.
투 포인터가 모든 경우를 보는 방식
투 포인터는 완전탐색처럼 모든 구간을 하나하나 확인하지 않는다.
대신 정답이 될 수 없는 구간을 건너뛴다.
예를 들어 이미 [0, 3]을 확인했다면, 이후의 [0, 4], [0, 5]는 더 긴 구간이다.
가장 짧은 구간을 찾는 문제에서는 굳이 다시 확인할 필요가 없다.
즉, 투 포인터는 모든 경우를 무식하게 다 보는 방식이 아니라,
정답 후보가 될 수 있는 구간만 효율적으로 확인하는 방식이다.
정리
투 포인터를 믿을 수 있는 이유는 이 문제의 조건에 방향성이 있기 때문이다.
right를 늘리면 조건을 만족하기 쉬워진다.
left를 늘리면 조건을 만족하기 어려워진다.그래서 다음 흐름이 가능하다.
보석 종류가 부족하면 right를 늘린다.
모든 보석 종류가 모이면 left를 줄인다.
줄이다가 조건이 깨지면 다시 right를 늘린다.한 번 지나간 left를 다시 볼 필요가 없는 이유는,
앞으로 right가 더 커질수록 같은 left에서 시작하는 구간은 더 길어지기만 하기 때문이다.
결국 투 포인터는 모든 구간을 직접 확인하지 않지만,
정답이 될 가능성이 있는 구간은 놓치지 않는다.
