[프로그래머스] 보석쇼핑
2020 카카오 인턴십 문제풀이 with Python3
문제링크
문제설명
- 이름이 다른 여러 종류의 보석들이 번호 순으로 놓여있는 진열대에 보관되어 있다.
- 진열대의 번호는 1번부터 시작하며 어떤 보석이 담겨있는지는
gems매개변수로 주어진다.
진열대 번호 : 1 2 3 4 5 6 7 8
보석의 종류 : D R R D D E S D- “진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간”을 찾아서 리턴한다.
위 예시에서 “모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간”은 D, R, E, S 보석을 모두 포함하는 3번 부터 7번 진열대임으로 [3, 7] 이 답이 된다.
문제풀이
배열의 처음부터 끝까지 순차적으로 탐색하는 탐색문제이다.
gems 배열의 크기는 최대 100000 이기 때문에 O(n^2)이상인 탐색 알고리즘으로는 시간 초과가 발생하여 문제를 풀 수 없다. 효율성 테스트가 존재하는 문제이기 때문에 알고리즘을 최적화하지 않는다면 더더욱 통과하기가 힘들것이다.
그러므로 O(n) 으로 탐색할 수 있는 투 포인터 알고리즘을 사용해야 한다.
- 먼저 배열 인덱스를 저장하는
start변수와end변수를 선언한다.
2. 배열의 start 와 end 구간이 “모든 종류의 보석을 포함하는 구간”이 될 때 까지 end 인덱스를 증가시킨다.
※ “배열의 start 와 end 구간” 이 “모든 종류의 보석을 포함하는 구간" 인지 여부를 판단하는 문제는 효율성을 위해 딕셔너리 자료구조를 사용한다.
진열대 번호 : 1 2 3 4 5 6 7 8
인덱스 번호 : 0 1 2 3 4 5 6 7
보석의 종류 : D R R D D E S Dstart = 0 end = 0 구간안에있는 보석 : []
start = 0 end = 1 구간안에있는 보석 : [D]
start = 0 end = 2 구간안에있는 보석 : [D, R]
start = 0 end = 3 구간안에있는 보석 : [D, R, R]
start = 0 end = 4 구간안에있는 보석 : [D, R, R, D]
start = 0 end = 5 구간안에있는 보석 : [D, R, R, D, D]
start = 0 end = 6 구간안에있는 보석 : [D, R, R, D, D, E]
start = 0 end = 7 구간안에있는 보석 : [D, R, R, D, D, E, S]
3. “구간 중 가장 짧은 구간” 을 구해야 하기 때문에 start 인덱스를 하나씩 증가시켜보며 구간의 길이를 줄여본다. 줄어든 구간이 “모든 종류의 보석을 적어도 1개 이상 포함” 한다는 조건을 만족시키면 현재start , end 를 저장하고, 조건이 만족되지 않을 때까지 구간의 길이를 줄인다.
진열대 번호 : 1 2 3 4 5 6 7 8
인덱스 번호 : 0 1 2 3 4 5 6 7
보석의 종류 : D R R D D E S Dstart = 0 end = 0 구간안에있는 보석 : []
start = 0 end = 1 구간안에있는 보석 : [D]
start = 0 end = 2 구간안에있는 보석 : [D, R]
start = 0 end = 3 구간안에있는 보석 : [D, R, R]
start = 0 end = 4 구간안에있는 보석 : [D, R, R, D]
start = 0 end = 5 구간안에있는 보석 : [D, R, R, D, D]
start = 0 end = 6 구간안에있는 보석 : [D, R, R, D, D, E]
start = 0 end = 7 구간안에있는 보석 : [D, R, R, D, D, E, S] 조건만족: O
start = 1 end = 7 구간안에있는 보석 : [D, R, R, D, D, E, S] 조건만족: O
start = 2 end = 7 구간안에있는 보석 : [R, R, D, D, E, S] 조건만족: O
start = 3 end = 7 구간안에있는 보석 : [R, D, D, E, S] 조건만족: O
start = 4 end = 7 구간안에있는 보석 : [D, D, E, S] 조건만족: X
4. 현재 구간이 조건을 만족시키지 않는다면 다시 end 인덱스를 증가시키면서 구간을 탐색한다.
5. 위 과정을 반복한다.
6. 구간을 전부 탐색했다면 탐색을 종료하고 조건을 만족하는 구간들 중에 길이가 가장 짧은 구간의 start , end 를 리턴한다.
