프로그래머스 보석쇼핑 문제

접근 방식(알고리즘 분류)

• 투포인터

내 풀이

1차 풀이

def solution(gems):
    answer = []
    idx = []
    _len = len(set(gems))
    for i in range(len(gems)):
        temp = set(gems[i:])
        if len(temp) == _len:
            idx.append(i)

    for k in idx:
        for i in range(len(gems)-1, k-1, -1):
            if len(set(gems[k:i+1])) == _len:
                end = i
        answer.append([k+1,end+1])
    return answer[0]

solution(["AA", "AB", "AC", "AA", "AC"])

1차 풀이 설명

• 우선적으로 [첫번째: 마지막] , [두번째:마지막] ... 이런식으로 검사해서 조건에 만족하는 경우를 저장한다.
• 조건을 만족하는 경우에 한해서 2중 반복문으로 조건에 만족하는 경우를 선별했다.

2차 풀이

def solution(gems):

    temp = gems[:]
    L = len(gems)
    dic = {gems[0]:1}
    size = len(set(temp))
    start, end = 0, 0
    result = [0, L-1]
    while start < L and end < L:
        if len(dic) == size:
            if result[1] - result[0] > end - start:
                result = [start, end]
            if dic[gems[start]] == 1:
                del dic[gems[start]]
            else:
                dic[gems[start]] -= 1
            start += 1
        else:
            end += 1
            if end == L:
                break
            if gems[end] in dic.keys():
                dic[gems[end]] += 1
            else:
                dic[gems[end]] = 1

    return([result[0]+1, result[1]+1])
solution(["AA", "AB", "AC", "AA", "AC"])

2차 풀이 설명

• 우선 반복문에 필요한 값들을 만들어두고, 투포인터를 이용해서 조건에 맞는지 검사한다.
• 해당 문제에서 투포인터 이용 --> 먼저 조건에 맞는 end값을 구해주고, 가장 적절한 start를 찾는 방식
• 기본적인 조건 즉, len(dic) == size 가 맞지 않으면 end를 키워가며 검사를 한다.
• 조건에 맞으면, 가장 적절한 start값을 찾아준다.

느낀점

• 문제를 풀때, 알고리즘이 하나도 안들어가고 단순히 조건 검사로 풀리는 문제는 의심을 해보고, 최대한 알고리즘을 적용시켜야 한다는 생각을 가지고 문제에 접근해야겠다.