📝 PROBLEM
https://school.programmers.co.kr/learn/courses/30/lessons/67258
🤔 THINKING
[요구사항]
배열 gems에서 모든 보석 종류를 하나 이상 포함하는 최소 구간을 찾는 문제이다.
최소 구간이 여러 개라면, 시작 번호가 작은 구간을 반환해야 한다.
💡 IDEA
["어떻게 모든 종류의 보석을 포함하는지 확인할까?"]
1. 중복 제거된 보석의 종류 개수를 파악해야 한다.
가장 먼저 떠올릴 수 있는 것은 "set"을 활용하는 것이다.
set(gems)를 사용해 보석 종류를 구하고, len(set(gems))으로 종류의 개수를 파악.
2. 현재 구간에서 보석 종류를 실시간으로 추적한다.
딕셔너리를 사용해 현재 구간에서 보석의 개수를 관리.
["최소 구간을 어떻게 찾을까?"]
1. 투 포인터(Two Pointers) 활용
- 시작 포인터 s와 끝 포인터 e를 사용해 구간을 조정한다.
- e를 증가시켜 구간을 확장하고, s를 증가시켜 구간을 줄임.
2. 조건 충족을 확인
- 현재 구간이 모든 보석 종류를 포함하는지 확인한다.
- len(gem_count) == len(gems_set)이면 모든 종류 포함.
3. 현재 구간 길이 (e - s + 1)이 기존 최소 길이보다 짧으면 정답을 갱신한다.
🎯 CODE
from collections import defaultdict
def solution(gems):
# 모든 보석의 종류를 파악
gems_set = set(gems)
total_types = len(gems_set) # 보석 종류의 개수
# 슬라이딩 윈도우를 위한 변수 초기화
gem_count = defaultdict(int)
s, e = 0, 0 # 투 포인터
answer = [0, len(gems) - 1] # 최소 구간 (시작, 끝)
gem_count[gems[0]] = 1 # 첫 보석 추가
while e < len(gems):
# 모든 종류의 보석을 포함하는지 확인
if len(gem_count) == total_types:
# 현재 구간 길이가 더 짧으면 정답 갱신
if (e - s) < (answer[1] - answer[0]):
answer = [s, e]
# 구간을 줄이기 위해 시작 포인터 이동
gem_count[gems[s]] -= 1
if gem_count[gems[s]] == 0: # 보석 개수가 0이 되면 제거
del gem_count[gems[s]]
s += 1
else:
# 끝 포인터를 이동해 구간 확장
e += 1
if e < len(gems):
gem_count[gems[e]] += 1
# 정답은 1-based index로 반환
return [answer[0] + 1, answer[1] + 1]
✒️ 총평
사실 코딩테스트에 관련된 포스팅은 하지 않고 깃허브에 코드를 올리고 주석으로 달아두거나,
readme 파일에 관련된 문법 정도만 차곡차곡 정리하는 편이다.
최근 2,3달 전에 본 회사 2차 코딩테스트에서 너무나 비슷한 문제가 나왔다.
해당 코테에는 3문제가 나왔고, 분명 1, 2번은 제출 후 모든 케이스까지 통과할 것 같는 확신이 있었다.
그리고 이 문제와 매우 흡사한 3번 문제에서 효율성을 강조하는 문장이 있었고,
나는 '문자열 슬라이싱 반복 / 매번 set을 반복하여 확인하는 로직 / 이중 for 문'을 사용했고,
해당 로직이 cost가 매우 많이 드는 구조인 것을 알고 있음에도 뚜렷한 해결방식을 떠올리지 못하고, 그대로 제출했던 경험이 있다.
물론 여타 효율성 테스트 문제와 같이, 문제 자체는 어렵지 않아 테스트 케이스에서는 모두 통과했지만
제출 후 효율성 테스트에서 많이 감점이 되었는지 떨어지게 되었다.
당시에도 어렴풋이는 "투 포인터"를 쓰면 될 것 같다 정도만 생각했었던 것 같다.
그래서 아마 투포인터를 구현하다가 시간 내에 구현하지 못하고 이전 방식대로 제출했었다.
그러나 몇 달 후 프로그래머스에서 매우 흡사한 문제를 발견했고, 투포인터만 적용해도 효율성 테스트가 통과하지 않는다는 것을 알게되었다...
같은 실수를 반복하지 않기 위해... 이런 문제나 꼭 기억하고 싶은 문제는 가끔 포스팅해서 두고두고 봐야겠다.
