[level 3] [카카오 인턴] 보석 쇼핑 - 67258

문제 링크

성능 요약

메모리: 17.1 MB, 시간: 53.68 ms

구분

코딩테스트 연습 > 2020 카카오 인턴십

채점결과

정확성: 33.3
효율성: 66.7
합계: 100.0 / 100.0

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.

어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.

어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.

진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

[제한사항]

• gems 배열의 크기는 1 이상 100,000 이하입니다.
  • gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
  • gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
  • gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

---

입출력 예

입출력 예에 대한 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

3종류의 보석(AA, AB, AC)을 모두 포함하는 가장 짧은 구간은 [1, 3], [2, 4]가 있습니다.

시작 진열대 번호가 더 작은 [1, 3]을 return 해주어야 합니다.

입출력 예 #3

1종류의 보석(XYZ)을 포함하는 가장 짧은 구간은 [1, 1], [2, 2], [3, 3]이 있습니다.

시작 진열대 번호가 가장 작은 [1, 1]을 return 해주어야 합니다.

입출력 예 #4

4종류의 보석(ZZZ, YYY, NNNN, BBB)을 모두 포함하는 구간은 [1, 5]가 유일합니다.

그러므로 [1, 5]를 return 해주어야 합니다.

※ 공지 - 2020년 7월 21일 테스트케이스가 추가되었습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

---

문제 풀이

문제 분석

이 문제는 보석이 진열된 순서대로 주어졌을 때, 모든 종류의 보석을 최소 1개 이상 포함하는 가장 짧은 구간을 찾는 것을 목표로 합니다. 만약 가장 짧은 구간이 여러 개라면, 시작 진열대 번호가 가장 작은 구간을 반환해야 합니다. 입력은 보석 이름 문자열들이 담긴 배열 gems이며, 출력은 찾은 구간의 시작 진열대 번호와 끝 진열대 번호(1부터 시작하는 인덱스)를 담은 배열입니다.

접근 방법

이 문제는 "모든 종류를 포함하는 가장 짧은 연속된 구간"을 찾는 전형적인 슬라이딩 윈도우(Sliding Window) 문제로 해결할 수 있습니다. 슬라이딩 윈도우는 두 개의 포인터(시작 left, 끝 right)를 사용하여 배열의 특정 구간을 탐색하는 기법입니다.

1. 모든 보석 종류 파악: 먼저 진열대에 존재하는 전체 보석 종류가 몇 가지인지 알아야 합니다. 이는 set 자료구조를 이용해 gems 배열의 유니크한 원소들을 추출하여 알 수 있습니다.
2. 윈도우 확장: right 포인터를 오른쪽으로 이동시키면서 현재 윈도우(gems[left:right+1])에 보석을 하나씩 추가합니다. 각 보석의 개수는 해시 맵(Python의 dict)을 사용하여 관리합니다.
3. 조건 확인 및 윈도우 축소: 현재 윈도우가 모든 종류의 보석을 포함하게 되면, 이제 이 윈도우를 최대한 줄여서 가장 짧은 구간을 만들어야 합니다. left 포인터를 오른쪽으로 이동시키면서 윈도우에서 보석을 제거하고, 해시 맵에서 해당 보석의 개수를 줄입니다. 이 과정에서 어떤 보석의 개수가 0이 되면 그 보석은 윈도우에서 사라진 것이므로 해시 맵에서 해당 종류를 제거합니다. 이 과정을 통해 윈도우가 더 이상 모든 종류의 보석을 포함하지 않을 때까지 left를 이동시킵니다.
4. 최단 구간 갱신: 윈도우 축소 과정에서 모든 종류의 보석을 포함하는 유효한 윈도우가 발견될 때마다 현재까지 발견된 최단 구간과 길이를 비교하여 갱신합니다. 시작 진열대 번호가 가장 작은 경우를 위해 left 포인터를 먼저 옮기는 방식은 자연스럽게 이 조건을 만족합니다.

구현 설명

1. 초기 설정 및 모든 보석 종류 파악

• gem = set(gems): gems 배열에서 모든 고유한 보석 종류를 추출하여 set에 저장합니다.
• l = len(gem): set의 크기를 l에 저장하여, 이 값이 우리가 윈도우에 포함해야 할 최소 고유 보석 종류의 개수가 됩니다.
• count = {}: 현재 슬라이딩 윈도우 내의 보석 종류별 개수를 저장할 딕셔너리를 초기화합니다.
• left = 0: 슬라이딩 윈도우의 시작 인덱스(0-based)를 0으로 초기화합니다.
• d = len(gems): 전체 보석 배열의 길이를 저장합니다.
• answer = [0, d - 1]: 최종 결과를 저장할 배열로, 초기에는 가장 긴 구간 [0, d-1]을 임시로 설정합니다. (나중에 더 짧은 구간이 발견되면 업데이트됩니다.)

2. 슬라이딩 윈도우 확장 (right 포인터 이동)

• for right in range(d): right 포인터를 0부터 gems 배열의 끝까지 순회하며 윈도우를 확장합니다.
• count[gems[right]] = count.get(gems[right], 0) + 1: gems[right]에 해당하는 보석을 윈도우에 추가하고, count 딕셔너리에서 해당 보석의 개수를 1 증가시킵니다. 만약 처음 등장하는 보석이면 기본값 0에 1을 더해 1이 됩니다.

3. 윈도우 축소 및 최단 구간 갱신 (left 포인터 이동)

• while len(count) == l: 현재 윈도우([left, right])가 모든 l 종류의 보석을 포함하고 있는 동안 이 while 루프를 실행합니다. 즉, 유효한 윈도우를 찾았으므로 이제 left를 이동시켜 윈도우 길이를 줄일 수 있는지 확인합니다.
  • if right - left < answer[1] - answer[0]: 현재 윈도우의 길이가 이전에 찾은 최단 윈도우(answer)의 길이보다 짧다면, answer를 현재 윈도우의 [left, right]로 갱신합니다. 이 조건은 "가장 짧은 구간"을 찾는 데 사용됩니다.
  • count[gems[left]] -= 1: left 포인터가 가리키는 보석을 윈도우에서 제외하기 위해 해당 보석의 개수를 1 감소시킵니다.
  • if count[gems[left]] == 0: del count[gems[left]]: 만약 gems[left] 보석의 개수가 0이 되었다면, 이 종류의 보석은 더 이상 현재 윈도우에 없으므로 count 딕셔너리에서 해당 항목을 완전히 제거합니다. 이렇게 하면 len(count) 값이 실제 윈도우에 있는 고유 보석 종류의 개수를 정확히 반영하게 됩니다.
  • left += 1: left 포인터를 오른쪽으로 한 칸 이동시켜 윈도우를 축소합니다.
• 이 while 루프는 left를 계속 이동시키면서 윈도우의 길이를 최소화하고, len(count)가 l보다 작아져 모든 보석 종류를 포함하지 않게 되면 종료됩니다. 이후 right 포인터가 다시 이동하여 윈도우를 확장하게 됩니다.

4. 결과 반환

• return [answer[0] + 1, answer[1] + 1]: 모든 탐색이 끝난 후 answer에 저장된 최단 구간의 0-based 인덱스에 1을 더하여 1-based 인덱스로 변환한 뒤 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(N)

  • set(gems)를 통해 모든 고유 보석 종류를 파악하는 데 O(N) 시간이 걸립니다. (여기서 N은 gems 배열의 길이입니다.)
  • right 포인터는 배열의 처음부터 끝까지 한 번만 순회합니다 (N번).
  • left 포인터도 right 포인터와 마찬가지로 배열의 처음부터 끝까지 한 번만 이동합니다 (최대 N번).
  • count 딕셔너리의 get, +=, -=, del, len 등의 연산은 평균적으로 O(1)의 시간 복잡도를 가집니다.
  • 따라서 전체 시간 복잡도는 N에 비례하는 O(N)이 됩니다.

• 공간 복잡도: O(G)

  • gem set은 최대 G개의 고유 보석 종류를 저장합니다.
  • count 딕셔너리도 최대 G개의 고유 보석 종류를 저장합니다.
  • G는 전체 보석의 개수 N보다 작거나 같으므로, 최악의 경우 (모든 보석이 다를 경우) O(N)의 공간을 사용합니다. 일반적인 경우 G는 N보다 훨씬 작을 수 있으므로 O(G)로 표현하는 것이 더 정확합니다.

핵심 포인트

1. 슬라이딩 윈도우 (Two Pointers): left와 right 두 개의 포인터를 사용하여 효율적으로 연속된 부분 배열(윈도우)을 탐색합니다. right 포인터로 윈도우를 확장하고, 조건이 만족되면 left 포인터로 윈도우를 축소하여 최적의 길이를 찾습니다.
2. 해시 맵 (Dictionary): 윈도우 내에 어떤 종류의 보석이 얼마나 포함되어 있는지를 O(1)의 평균 시간으로 추적하기 위해 사용됩니다. 이를 통해 현재 윈도우가 모든 종류의 보석을 포함하는지 빠르게 판단할 수 있습니다.
3. 모든 종류 보석의 개수 사전 파악: set(gems)를 통해 전체 gems 배열에 있는 유일한 보석 종류의 개수를 미리 알아내어, 슬라이딩 윈도우가 이 조건을 만족하는지 여부를 판단하는 기준으로 삼습니다.

풀이 코드

def solution(gems):
    gem = set(gems)
    l = len(gem)
    count = {}
    left = 0
    d = len(gems)
    answer = [0, d - 1]

    for right in range(d):
        count[gems[right]] = count.get(gems[right], 0) + 1

        while len(count) == l:
            if right - left < answer[1] - answer[0]:
                answer = [left, right]

            count[gems[left]] -= 1
            if count[gems[left]] == 0:
                del count[gems[left]]
            left += 1

    return [answer[0] + 1, answer[1] + 1]