[KAKAO] 보석쇼핑 (2020 KAKAO 인턴십)

어느 순간 level3문제를 풀다가 문득 너무 어렵다고 느껴져 백준 온라인으로 넘어갔다. 거기서 특정 알고리즘 bfs, dfs, 투포인터, greedy, dijkstra, 등 쉬운 몇 문제들을 풀었다. 아직 알고리즘 부분에서 부족한 것들이 많게 느껴져서 기초를 잡고자 함이었다.

 

다시 돌아와서 확실히 문제들을 풀어보니 문제를 읽다가 어떤 알고리즘으로 풀어야겠다! 라고 생각이 점점 나기 시작했다.

이번문제의 알고리즘은 투포인터 알고리즘으로 풀 수 있었다.

중간에 계속 틀려서 잠시 dp로 풀수도 있을까 생각 했지만 내 로직이 틀렸던 것 같아 계속 수정해서 해봤더니 맞았다.

 

투포인터

투포인터 알고리즘 정리할겸 간단하게 요약해봐야겠다.

긴 배열에서 연속된길이를 구할 때 특정조건을 만족시키면서 배열을 O(N)번만 탐색 가능하게 할 수 있는 알고리즘이다.

l, r 의 값을조절해주면서 만약 특정 조건을 만족시킨다면 l 값을 증가시키거나 r값을 증가시키면서 정답을 찾아나간다.

이번문제는 효율성 면에서도 고려해 봤을때 이 알고리즘이 가장 적합하다고 생각했다.

(배열의 길이가 10만이 되어버리므로 N^2으로 했다가는 시간초과가 날 것이다.)

 

 

 

programmers.co.kr/learn/courses/30/lessons/67258?language=python3

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

먼저 문제를 봤을 때 찾고자하는 연속된 길이안에 어느 보석이 몇개 들어있는지 알아야한다.

투포인터를 생각해도 중요했던 것은 각 조건들을 어떻게 넣어줄까? 에서 고민을 좀 했던것 같다.

 

1. set() 을 통해 중복없이 보석들을 딕셔너리에 저장해준다. 

 

2. 투포인터 알고리즘으로 가능한 연속된 배열의 정보를 answer에 맞춰 담는다.

( 탈출 조건이 중요하다. r이 맨끝으로 도달 하고,  인덱스 l~r까지의 수들의 개수가 현재 보석들의 종류보다 작으면 탈출한다.)
check 딕셔너리에 해당 배열이 나타나면 넣어주되 cnt로 현재 보석 몇 종류가 담겨져 있는지 따로 변수를 둔다.

- check[ 보석 ] = 0 인경우에서 check[ 보석 ] = 1 인 경우로 된다면 보석의 종류가 늘어난것이되고 아니면 감소한것이 된다.

 

3. answer을 길이가 짧은 순으로 정렬하여 첫번째 리스트를 반환한다.

 

def solution(gems):
    answer = []
    dia = set(gems)
    check = {j: 0 for j in dia}

    l, r = 0, 0
    check[gems[l]] += 1
    cnt = 1

    while l <= r:
        if r == len(gems)-1 and r-l+1 < len(dia):
            break
        if cnt == len(dia):
            answer.append([l+1, r+1])
            check[gems[l]] -= 1
            if check[gems[l]] == 0:
                cnt -= 1
            l += 1
        else:
            if r != len(gems) - 1:
                r += 1
                if check[gems[r]] == 0:
                    cnt += 1
                check[gems[r]] += 1
            else:
                check[gems[l]] -= 1
                if check[gems[l]] == 0:
                    cnt -= 1
                l += 1

    answer = sorted(answer, key=lambda x: (x[1]-x[0], x[0], x[1]))
    return answer[0]