[프로그래머스] 보석 쇼핑

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

하나의 배열에서 조건을 만족하는 구간을 구해야 했으므로 투포인터로 접근하였습니다.

시작점을 기준으로 하여, 조건을 찾은 후에 시작점을 한칸만 이동하여 다음 구간을 찾게 되면 시간초과 문제가 발생할것으로 생각했습니다.

또한, 짧은 구간이 여러개일 경우 시작 진열대 번호가 작은 구간을 출력하여야 했으므로 배열의 오른쪽에서 왼쪽으로 탐색을 시도하였습니다.

 

우선, 오른쪽 포인터를 기준으로 하여 왼쪽 포인터를 이동 시키며 조건을 만족하는 구간을 구했습니다. 그리고 왼쪽 포인터를 기준으로 오른쪽 방향으로 진행하여 더 짧은 구간이 존재하는지 탐색하였습니다.

구간의 길이를 구했다면, 다음 탐색을 위해 오른쪽 포인터보다 한칸 앞에서 기준을 잡아 탐색하였습니다.

2) 알고리즘

• 투포인터

3) 풀이 코드

사용 언어 - Python

def solution(gems):
    answer = [0, 1e10]
    G = len(set(gems))          # 보석의 종류의 개수
    gems = [''] + gems          # 보석의 번호가 1번부터 시작하므로 인덱스 맞춤

    sign = False                        # 인덱스 범위를 벗어나면 종료
    l, r = len(gems), len(gems)-1       # 두개 포인터의 시작점
    while True:
        buy_gems = set()                # 현재 경우에 구매하는 보석의 종류

        while len(buy_gems) < G:        # 모든 종류 보석을 구매하지 않았다면
            l -= 1                      # 왼쪽 인덱스 감소
            if l <= 0:                  # 왼쪽 인덱스가 범위를 벗어나면 종료
                sign = True
                break
            buy_gems.add(gems[l])       # 왼쪽 인덱스의 보석 추가
        else:
            answer = answer if answer[1]-answer[0] < r-l else [l, r]        # 보석을 종류별로 구매했으면 가장 짧은 거리인지 구분
        
            r = l - 1                                                       # 왼쪽 인덱스를 기준으로하여 오른쪽으로 한번 더 탐색
            buy_gems.clear()                                                # 구매한 보석 종류 리셋

            while len(buy_gems) < G:                                        # 모든 종류 보석을 구매하지 않았으면, 오른쪽 인덱스 증가
                r += 1
                buy_gems.add(gems[r])
            answer = answer if answer[1]-answer[0] < r-l else [l, r]
        
        l = r           # 다음 탐색을 위해, 두개의 포인터는 오른쪽 포인터쪽으로 맞춤
        r = r - 1

        if sign:        # 종료
            break

    return answer

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

포인터의 인덱스 관리에 어려움을 느꼈습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다