![[프로그래머스] 보석 쇼핑](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FekAOz7%2Fbtq4o7WjwOQ%2F4TAkYT3tQNXlH3X8nWcpv1%2Fimg.gif)
programmers.co.kr/learn/courses/30/lessons/67258?language=swift
코딩테스트 연습 - 보석 쇼핑
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]
programmers.co.kr
레벨 3에 해당하는 문제.
처음에는 그냥 시도해서 실패 > 투 포인터 개념 학습 후 도전 > 정확성은 다 맞으나 효율성 0점 > 문제의 원인? 배열! > 배열을 딕셔너리로 바꿔서 체크해줌 > 통과
자 이제 문제를 봐보자.
주어진 배열 내에서 유니크한 모든 원소들을 포함하는 구간을 만든다고 했을 때 가장 짧은 구간을 구하면 된다. 구할 때에 동일하게 짧은 구간이 있다면 시작 지점이 더 빠른 것을 반환해주면 된다.
여기서 "투 포인터"라는 알고리즘으로 풀이하게 되는데 어떠한 방식인지 알아보자.
투 포인터
말 그대로 투 = 2개의, 포인터 = 인덱스 라고 봐도 무방하다.
시작, 끝 지점의 인덱스 값을 가지고 범위 내의 값을 조건과 비교해가며 원하는 값을 얻어낼 수 있는 방식이다.
예를 들어 아래의 배열 내에서 합을 5로 만드는 원소들의 집합을 구해야 하는 상황을 생각해보자.
| index | 1 | 2 | 3 | 4 | 5 |
| value | 1 | 2 | 2 | 1 | 5 |
항상 시작은 (0,0)에서 할 수 있도록 세팅해준다.
따라야 할 조건은 다음과 같다.
1. 5보다 작다면, e += 1
2. 5와 같다면 해당 범위 내 집합 저장 후, 다음 케이스 탐색을 위해 s += 1
3. 5보다 크다면 s += 1
자 한 번 눈으로 하나하나씩 봐보자.
STEP 1.
s = 0, e = 0로 범위 내 집합은 [1] 이다. (5보다 작다)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[1번] 케이스에 해당하기에 e에 1을 더해준다.
STEP 2.
s = 0, e= 1로 범위 내 집합은 [1,2]이다. (5보다 작다)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[1번] 케이스에 해당하기에 e에 1을 더해준다.
STEP 3.
s = 0, e= 2로 범위 내 집합은 [1,2,2]이다. (5와 같다.)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[2번] 케이스에 해당하기에 우선 결과값을 저장해주고 다음 케이스 탐색을 위해 s에 1을 더해준다.
| answer | [[0,1,2]] |
STEP 4.
s = 1, e= 2로 범위 내 집합은 [2,2]이다. (5보다 작다.)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[1번] 케이스에 해당하기에 e에 1을 더해준다.
STEP 5.
s = 1, e= 3로 범위 내 집합은 [2,2,1]이다. (5와 같다.)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[2번] 케이스에 해당하기에 우선 결과값을 저장해주고 다음 케이스 탐색을 위해 s에 1을 더해준다.
| answer | [[0,1,2],[1,2,3]] |
STEP 6.
s = 2, e= 3로 범위 내 집합은 [2,1]이다. (5보다 작다.)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[1번] 케이스에 해당하기에 e에 1을 더해준다.
STEP 7.
s = 2, e= 4로 범위 내 집합은 [2,1,5]이다. (5보다 크다.)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[3번] 케이스에 해당하기에 다음 케이스 탐색을 위해 s에 1을 더해준다.
STEP 7.
s = 3, e= 4로 범위 내 집합은 [1,5]이다. (5보다 크다.)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[3번] 케이스에 해당하기에 다음 케이스 탐색을 위해 s에 1을 더해준다.
STEP 8.
s = 4, e= 4로 범위 내 집합은 [5]이다. (5와 같다.)
| index | 0 | 1 | 2 | 3 | 4 |
| value | 1 | 2 | 2 | 1 | 5 |
[2번] 케이스에 해당하기에 우선 결과값을 저장해주고 다음 케이스 탐색을 위해 s에 1을 더해준다.
| answer | [[0,1,2],[1,2,3],[4]] |
STEP 9.
그 다음부터는 s와e가 배열의 index를 넘어서기에 break해준다.
대충 위와 같은 방식으로 해당 문제도 풀이될 수 있다.
과정을 gif로 구성해보았다. 위 예시와 유사하게 전개되니 천천히 보면서 이해해보면 될 것 같다.
바로 코드로 가보자!
import Foundation
func solution(_ gems:[String]) -> [Int] {
// 나중에 e에 먼저 1을 더해야하기에 여기서 미리 -1 해준 상태로 시작
var s = 0, e = -1
// 중복없는 배열의 크기
let size = Set(gems).count
// 최대 거리 = 배열의 길이
var minDist = gems.count
var answer = [0,0]
// 1일 경우 먼저 예외처리
if size == 1 { return [1,1] }
// 투 포인터 알고리즘
var dict = [String:Int]()
var cnt = 0
while s < gems.count && e < gems.count {
cnt = dict.count
// 조건(모든 원소 포함?)에 맞는다면 s ++
if (cnt == size) {
if abs(e - s) < minDist {
minDist = abs(e - s)
// 기존 s,e는 인덱스이기에 +1씩 해줘야한다.
answer[0] = s + 1
answer[1] = e + 1
}
// dict내 value 값이 0이 되면 key를 삭제해줘야 한다.
// 그래야 cnt를 제대로 구할 수 있다.
if let v = dict[gems[s]] {
if v - 1 == 0 {
dict.removeValue(forKey: gems[s])
} else {
dict[gems[s]] = v - 1
}
}
s += 1
// 조건에 맞지 않는다면 e ++
} else {
e += 1
// index에서 벗어나지 않도록 해준다.
if e < gems.count {
// 들어오는 값들 추가
if let v = dict[gems[e]] {
dict[gems[e]] = v + 1
} else {
dict[gems[e]] = 1
}
}
}
}
return answer
}
[ 프로세스 ]
1. 시작, 끝의 인덱스를 설정한다.
2. 중복 값을 제거한 배열의 길이를 구하고, 기존 배열의 길이를 최소 거리로 설정한다
3. 모든 원소들이 담겨있는지 확인하기 위한 dict, cnt를 생성한다.
4. s와 e가 배열의 index를 벗어나지 않을 때
4-1. cnt의 값을 업데이트 해준다.
4-2. cnt가 모든 원소를 갖고 있다면
4-2-a. 최소 거리일 경우 최소 거리 값을 업데이트 해주고, s+1, e+1을 저장한다.
4-2-b. dict에 값을 가지고 있을 경우 1을 빼주고, 1을 빼줬을 때 값이 0이 되면 Key를 삭제한다. (이제 포함하고 있지 않기에)
4-2-c. s += 1
4-3. 조건에 맞지 않을 경우,
4-3-a. e+= 1 (먼저 해주는 이유는, 추가한 경우를 확인해야하기 때문)
4-3-b. 배열의 길이를 초과하지 않는다면, 값을 추가 (1) 해주거나 있을 경우 1만큼 더해준다.
5. 결과 반환!
풀고나니 엄청 어려운 문제는 아니었던 것 같다.
다만 "투 포인터"라는 새로운 알고리즘을 몰랐더라면 효율성도 딸려있는 문제이기에 풀기 어려웠을 것 같다.
이번 문제도 마찬가지로 여러 시뮬레이션을 해보며 이해하니 조금 수월했다. 그리고 새로운 알고리즘으로 접근해야하는 문제는 조금 시도해보고 빠르게 새로운 알고리즘을 학습하는 방식이 조금 더 효과적일 것 같다.
끄읕