프로그래머스 - 보석 쇼핑

nhwang·2022년 5월 4일
0

PS_해시

목록 보기
1/1
def solution(gems):
    answer = [0,0]
    checkcnt = {}
    for g in gems:
        if g in checkcnt:
            continue
        else:
            checkcnt[g] = 1
    ll = len(checkcnt)
    d = {}
    mmin = 200000
    for i in range(len(gems)):
        if gems[i] in d:
            del d[gems[i]]
            d[gems[i]] = i+1
        else:
            d[gems[i]] = i+1
        if ll == len(d):
            for key in d:
                tempst=d[key]
                break
            temp = i+1 - tempst
            if temp < mmin:
                answer[0] = tempst
                answer[1] = i+1
                mmin = temp
    return answer

보석 최대 갯수 중복없이 체크 일반적으로 하면 n^2이라 풀 수 없음
처음에 DP를 생각함. 선이 계속 중복으로 그어지기 때문.
정석풀이는 투포인터라고들 하는데 불현듯 해시가 떠올랐다.

연결된 것을 따지는 거기 때문에 배열보다는 리스트 계열과 유사한 성질을 가질것으로 판단
중복없이 보석수와 동일해질 때 처음과 마지막에만 관심이 있음 (중간은 관심이 없음)
해시는 스택처럼 뒤에 쌓이는 성질을 이용하기로 함. 13414


O(N) 풀이 가능

1) index를 순회하며 맨 뒤의 index만 보관하면 최소범위로 저장될 것이라 판단.
2) 삭제 후 삽입을 하게되면 보석의 순서도 지켜질 것.
3) A B B에서 A:1, B:3 담고 있으면 중간의 2에 위치한 B도 포함하지 않을 것 처럼 생각되었으나,
A B최소 범위는 이미 index가 2일 때 순회하면서 따졌을 것이므로 1번 규칙을 충족한다.

구현방법
1. 먼저 해시로 보석의 갯수를 센다.
2. gems를 순회하면서 보석을 담는다. 이때 중복없이 처음과 마지막만 알면 되기 때문에 이미 담겨있으면 지워버리고 인덱스를 담는다
3. 보석의 수를 충족하는 경우 인덱스를 담고 있으므로 end - start로 갯수를 비교해 가장 적은 값을 가지고 있으면서 전체 순회
*범위가 같은 경우는 저장하지 않는다. 앞에서부터 저장하기 때문

유사 문제 - 백준 13414 수강신청

profile
42Seoul

0개의 댓글