프로그래머스 보석 쇼핑 파이썬 문제풀이

문제 설명

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

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

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

진열대 번호12345678

보석 이름

DIA

RUBY

RUBY

DIA

DIA

EMERALD

SAPPHIRE

DIA

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

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

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

[제한사항]

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

---

입출력 예

gemsresult

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]	[3, 7]
["AA", "AB", "AC", "AA", "AC"]	[1, 3]
["XYZ", "XYZ", "XYZ"]	[1, 1]
["ZZZ", "YYY", "NNNN", "YYY", "BBB"]	[1, 5]

입출력 예에 대한 설명

입출력 예 #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일 테스트케이스가 추가되었습니다.

 

 

문제풀이1. 

처음에는 투포인터를 사용해서 Left를 첫 영역에, 그리고 Right를 마지막 영역에 설정하면서 푸는 풀이로 접근을 했다. 보석을 다 가지는 위치를 찾고, 그 때 구간의 길이와 Left, Right를 Return했고, 이 값을 우선순위큐에 넣어서 구간의 길이가 가장 작은 값을 가지는 식으로 접근했다. 

이 때, 대부분의 문제는 해결이 되었는데 효율성 문제에서 발목이 잡혔다. 처음에는 Left를 KMP 알고리즘에서 건너뛰는 것처럼 접근을 했는데, 당연하게도 반례가 굉장히 많았다. 

예를 들어, B,A,A,A,C,D라는 항목이 있다고 했을 때, 이 때 구간의 총 길이는 6이고 보석의 갯수는 4개가 된다. 그런데 이 정보를 바탕으로 그 다음 살펴볼 구간을 효율적으로 구할 수 있는 방법이 없었다. 예를 들어, 총 6개 중에 4개만 만족하니 2개를 건너 뛴다고 가정하면, 당연하게도 더 이상의 값을 구할 수가 없다. 위의 경우에는 그렇게 해도 답이 나오지만, 뒷쪽에 수열이 더 많이 있을 경우에는 필연적으로 반례가 나타날 수 밖에 없는 구조였다.  

이런 이유 때문에 Left를 1칸씩 계속 올리고, 올렸을 때 Left, Right로 Two Pointer로 접근을 했다. 이 때, 효율성 테스트 3,6,9,12번에서 통과가 안되었다. 지금 생각해보면, 시간 복잡도가 O(N * N) 정도가 될 것 같다. 왜냐하면 Left가 0부터 N까지 한번 쓸고 가기 때문에 N이 기본인데, 그 N번의 경우에 대해서 최악의 경우 전체를 다 살펴봐야 할 가능성이 있기 때문이다. 

그 후에는 Start, End 방식으로 접근했다. START는 0, END는 -1로 설정을 해둔 후, 점진적으로 살펴본다. 아래와 같은 로직으로 접근했다.

1.  현재 가지고 있는 보석의 개수가 보석 종류보다 작으면 Right를 한 칸 올린다.
2.  현재 가지고 있는 보석의 개수가 보석 종류와 같으면 Left를 한 칸 올린다.
3.  Right를 끝까지 살펴봤다면, Left를 끝까지 올리며 살펴본다.

도식화 하면 아래와 같이 볼 수 있다. 

Index	0	1	2	3	4	5	6	7	개수	가진거
시도	D	R	R	D	D	E	S	D
1	LR								1	D
2	L	R							2	DR
3	L		R						2	DR
4	L			R					2	DR
5	L				R				2	DR
6	L					R			3	DRE
7	L						R		4	DRES
8		L					R		4	DRES
9			L				R		4	DRES
10				L			R		3	DESD

 

그렇다면 위의 경우를 할 때, 보석의 수는 어떻게 세는 것이 맞을까? 처음에는 Dictionary에 Count가 0으로 되어있는 행의 갯수를 세면서 현재 보석 종류 수를 세었는데, 이 경우 당연한 얘기지만 보석의 종류가 많아지면 시간초과가 필연적으로 따라올 수 밖에 없다. 

이 문제를 해결 하기위해, 1,2번 과정에서 보석 종류 갯수를 확인하는 것을 보완했다. 예를 들어 Right를 위로 올리는 행위는 새로운 보석이 들어오는 일이기 때문에 올렸을 때, 들어올 보석의 갯수가 현재 0개인지  확인하는 식으로 해결했다.

Left는 가지고 있던 보석을 빼는 일이기 때문에, 현재 Left에 있는 보석의 갯수가 1개인지 확인을 했다. 1개면 이번 보석이 빠지면 0개가 되고, 그러면 보석 종류가 1개 줄어든다. 

def find_len(gems) :
    my_set = set()
    for i in gems :
        my_set.add(i)
    return my_set

def init_dict(d,my_set) :
    for i in my_set :
        d[i]
    return d

def solution(gems):
    d = defaultdict(int)
    my_set = find_len(gems)
    init_dict(d,my_set)
    left,right,gnum = 0,-1, 0
    answer_skew = 9876543210
    while left < len(gems) and right < len(gems) :
        if gnum == len(my_set) :
            if answer_skew > right - left +1  :
                answer_skew = right - left + 1
                answer_left = left
                answer_right = right
        if right < len(gems) -1  :
            if gnum < len(my_set) :
                right += 1
                if d[gems[right]] == 0 :
                    gnum +=1
                d[gems[right]] +=1

            else :
                if d[gems[left]] == 1 :
                    gnum -=1
                d[gems[left]] -=1
                left +=1
        else :
            if d[gems[left]] == 1:
                gnum -= 1
            d[gems[left]] -=1
            left +=1
    return [answer_left +1 , answer_right +1 ]