23.03.17 파이썬 코딩 퀴즈#200 보석 쇼핑 (프로그래머스 스쿨)

이번 문제는 보석 쇼핑 문제이다.

전달받은 gems 배열을 탐색하여 모든 종류의 보석을 1개 이상씩 구매 할 수 있는 구간을 찾고, [시작번호, 끝번호] 를 반환하면 된다.

딱히 특별한 제한조건은 없으나, 배열의 크기가 1이상 100,000 이하이다.

처음 작성한 코드이다.

코드가 길긴 하지만 굉장히 단순하게 구현했다. 먼저 보석의 종류를 확인하고 보석 종류별로 gems 에서 index를 확인해 gem_idx 에 2차원 배열로 저장한다.

그리고 permutations()를 이용해 생성된 조합을 통해 조건을 만족하는 조합만 선택하여, [min(), max(), max()-min()] 으로 저장해 주었다. 

그리고 마지막으로 max()-min()값 기준으로 오름차순 정렬하여, [buy[0][0], buy[0][1]] 을 반환해 주었다.

코드 자체에 오류는 없었으나 절반 이상이 시간제한에 걸렸다. 어느정도 예상은 했지만, 내 생각을 코드로 작성해 보고 싶었다.

이제 시간을 줄일 수 있는 방법을 찾아봐야 한다.

1. 슬라이싱을 하지 않고 범위내의 보석의 종류와 갯수를 확인 가능한 방법을 찾아야 한다.

2. 배열의 처음부터 끝까지 완전탐색이 필요하다.

몇시간을 고민한 끝에 완성한 코드.

먼저 answer의 완성 조건은 gem_list{}의 모든 요소의 값이 1 이상인 경우이다.

반대로 얘기하면 탐색을 진행할때, 처음에는 모든 보석이 담기는 마지막 지점까지 갔다가, 다시 while문을 통해 start 값을 증가시켜 주는데, 이때에는 보석이 2개 이상 담긴 배열까지만 진행하게 된다.

위 그림처럼 ["A","B","B","B","B","B","B","C","B","A"] 이라는 배열을 전달받아서 탐색하낟고 가정해보자.

[0,8] 까지 탐색을 하게 되면 A,B,C 3종류의 보석을 모두 구매할 수 있다.

하지만 이때 start 값을 1`로 늘리게 되면 A가 하나밖에 존재하지 않기 때문에 while문을 그대로 빠져나오고 A가 2개가 되는 시점이 마지막까지 탐색을 진행한다. 이때 len(gems) 는 11이고 end 는 10이 된다.

최종적으로 end 값을 1 증가 시킨 다음 if문을 타고 들어가서 start 값이 증가되기 시작한다.

제거한 이후에 start 값이 증가되기 때문에, 계산되는 좌표는 왼쪽의 좌표이다.

그리고 마지막으로 반환되는 값은 start 값이 1 증가된 [8,10]이 된다.

 

최종적으로 주의해야 할 점은 구간의 길이이다. 이는 answer[2] 값을 사용하였다.

따라서 최종적으로 반환해야 할 값은 answer[:2] 가 된다.