보석 쇼핑[2020 카카오 인턴십]

 

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

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

 

 

1. 첫번째 시도

 

무지막지하게 틀려버렸다. 예제는 맞아서 기뻤지만 그 기쁨도 한 순간, 제출 해보니 무지막지 했다.

시간초과가 엄청 발생했고 메모리는 1기가를 잡아먹더라(처음 봤다 이런 메모리는....)

 

접근 방법 :

* 고유값만 가져와서 비교하면 될것으로 판단, set 자료구조를 사용하였다.

* 입력받은 보석들의 고유값들의 길이 만큼  구간을 띄워주고 인덱싱 해주고 이 모든 것을 set로 만들어 버린다

* 다시 배열을 순회하면서 set의 길이가 같은 친구들을 answer 배열에 넣어준다

* answer 배열을 기준에 맞게 정렬해주고 답을 출력한다.

 

  def solution(gems):
      result = [[{}] * len(gems) for _ in range(len(gems))]
      l = set(gems)
       answer = []
        for i in range(len(gems)):
             for j in range(i, len(gems)):
                 result[j][i] = set(gems[i:j + 1])

         for i in range(len(result)):
             for j in range(len(result[0])):
                 if len(result[j][i]) == len(l):
                     answer.append([i, j])

         answer.sort(key=lambda x: (x[1] - x[0], x[0]))
         first, second = answer[0]
         return [first+1, second+1]

 

2. 정답 코드

 

* 배열의 최대 길이가 100000 인데 이걸 n^2 으로 접근해버리면 10000000000가 된다..... n^2은 안된다.

* python의 딕셔너리와 start, end에 대한 정보만 가지고 값을 접근할 수 있지 않을까 싶었다.

* 값을 순회해야할때 규칙적인 룰이 있다면 배열, 불규칙적이다 하면 dict를 사용하라고 배웠다.

 

정답 코드 먼저 첨부하고 설명을 해보자

def solution(gems) :  
  answer = []
  gem_set = set(gems)
  gem_dict = {}
  GEM_LENGTH = len(gems)
  start = 0
  end = 0
  while start <= GEM_LENGTH and end <= GEM_LENGTH :
    if len(gem_dict) < len(gem_set) :
      if end >= GEM_LENGTH:
        break
      if gem_dict.get(gems[end]) :
        gem_dict[gems[end]] += 1
      else :  
        gem_dict[gems[end]] = 1
      end += 1
    else :
      answer.append([start, end - 1])
      gem_dict[gems[start]] -= 1
      if gem_dict.get(gems[start]) == 0 :
        del gem_dict[gems[start]]
      start += 1
    
  answer.sort(key= lambda x : (x[1] - x[0], x[0]))
  first, second = answer[0]
  return [first+1, second+1]

 

* start, end의 증가, 감소 쪽에 집중을  해보자

 

-> start 증가 조건

어피치의 모든 보석을 없애지 않는 조건 하에서 모든 보석의 개수가 2개 이상이여야 줄일 수 있다.

-> end 증가 조건

어피치는 모든 보석을 사고 싶어한다 -> dict에 모든 보석이 포함될때까지 증가 시켜야 한다.

-> 종료 조건 

start, end가 배열의 인덱스보다 커지면 종료 시킨다.