https://programmers.co.kr/learn/courses/30/lessons/67258
코딩테스트 연습 - 보석 쇼핑
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]
programmers.co.kr
과정
1. 이분 탐색 * 투 포인터 알고리즘: O(logn) * O(n) = O(nlogn)
- 보석 종류의 개수를 센다 (HashSet 사용)
- 구간 길이를 기준으로 이분 탐색을 한다.
- 모든 보석을 포함하는 구간(mid)을 찾았다 -> 정답을 비교,갱신하고 최소 값을 찾기 위해 end = mid - 1
- 모든 보석을 포함하는 구간이 없다 -> 길이를 늘려서 (이분 탐색 구간을 오른쪽으로 이동) 확인하기 위해 start = mid + 1
- 보석 포함 구간을 찾는 과정은 투 포인터(슬라이딩 윈도우) 알고리즘과 Map을 활용한다. (Map 활용법은 아래를 참고해주세요)
2. 슬라이딩 윈도우만 적용하는 알고리즘: O(n)
1. 보석 종류를 센다.
2. 투 포인터로 모든 보석을 포함하는 가장 짧은 구간을 찾는다.
2-1) 모든 보석을 포함시킬 때까지 end 포인터를 증가시키며 보석을 담는다. (map의 value 증가)
2-2) 모든 보석을 포함하면,
2-2-1) 이전에 구했던 구간 길이와 비교해서 정답을 갱신한다.
2-2-2) start 포인터를 증가시키면서 보석을 버린다.
2-2-3) 여전히 모든 보석을 포함하고 있으면, 2-2) 의 로직을 반복한다.
💡 Map을 활용해서 구간 내 보석 종류의 개수 관리하는 방법
val countMap = HashMap<String, Int>() // 범위 내 보석 개수 저장, key: 보석, value: 개수
var countInRange = 0 // 범위 내 보석 종류의 개수
// 보석이 새로 추가된 경우 (0 -> 1)
if (countMap[addedGem]!! == 1) {
countInRange++
}
// 포함됐던 보석이 범위 이동으로 제거된 경우 (1 -> 0)
if (countMap[removedGem]!! == 0) {
countInRange--
}전체 코드1 (이분 탐색 + 투 포인터)
import java.util.*
class Solution {
val gemSet = HashSet<String>() // 모든 보석
fun solution(gems: Array<String>): IntArray {
for (gem in gems) {
gemSet.add(gem)
}
var answer = IntArray(2)
var start = gemSet.size
var end = gems.size
// 이분 탐색
while (start <= end) {
val mid = (start + end) / 2
val range = findRange(gems, mid)
// 해당 길이로는 모든 보석을 포함시킬 수 없다 -> 길이를 늘린다
if (range == null) {
start = mid + 1
} else { // 포함시킬 수 있다 -> 정답을 갱신하고, 최소 길이를 탐색한다
answer[0] = range.first
answer[1] = range.second
end = mid - 1
}
}
return answer
}
// 투 포인터(or 슬라이딩 윈도우)
fun findRange(gems: Array<String>, rangeLength: Int): Pair<Int, Int>? {
val countMap = HashMap<String, Int>() // 범위 내 보석 count
var countInRange = 0 // 범위 내 보석 종류의 개수
var start = 0
var end = 0
// [start, end)로 투 포인터 탐색
// end가 가리키는 보석을 추가하고, end를 증가시키는 구조
while (end < gems.size) {
val addedGem = gems[end++]
countMap[addedGem] = countMap.getOrDefault(addedGem, 0) + 1
// 보석이 새로 추가된 경우 (0 -> 1)
if (countMap[addedGem]!! == 1) {
countInRange++
}
// rangeLength가 될 때까지는 범위를 늘리기만 한다
if (end - start < rangeLength) continue
// 모든 보석을 포함하는 구간을 찾았으면 바로 반환
// why? 가장 왼쪽 범위를 원하고 있기 때문이다
if (countInRange == gemSet.size) {
return Pair(start + 1, end) // 진열대 번호: 1 ~ gems.size
}
val removedGem = gems[start++]
countMap[removedGem] = countMap[removedGem]!! - 1
// 포함하던 보석이 범위 이동으로 제거된 경우
if (countMap[removedGem]!! == 0) {
countInRange--
}
}
return null
}
}전체 코드2 (슬라이딩 윈도우 or 투 포인터)
import java.util.*
class Solution {
fun solution(gems: Array<String>): IntArray {
var answer = IntArray(2)
val gemSet = HashSet<String>()
var countMap = HashMap<String, Int>() // 범위 내 보석 개수 저장, key: 보석, value: 개수
var countInRange = 0 // 범위 내 보석 종류 수
var minLength = gems.size + 1 // 모든 보석 포함하는 최소 구간 길이
for (gem in gems) {
gemSet.add(gem)
}
var start = 0
var end = 0
// [start, end) 형태로 구간 탐색
// end가 가리키는 곳까지 범위를 늘리고, end를 증가시키는 구조
// 전체 보석을 포함할 때까지 end를 증가시키고,
// 보석 하나가 전부 제거될 때까지 start를 증가시키면서 정답을 비교, 갱신한다
while (end < gems.size) {
val addedGem = gems[end++]
countMap[addedGem] = countMap.getOrDefault(addedGem, 0) + 1
if (countMap[addedGem]!! == 1) {
countInRange++
}
// start를 오른쪽으로 한 칸 옮겼는데도 여전히 모든 보석을 포함하는 경우가 존재한다.
// ex) 범위 내에 start 보석을 2개 이상 갖고 있는 경우
// 따라서, 보석 하나가 0이 될 때까지 start를 증가시키면서 정답 갱신 조건을 확인한다
while (countInRange == gemSet.size) {
if (minLength > end - start) {
minLength = end - start
answer[0] = start + 1
answer[1] = end
}
val removedGem = gems[start++]
countMap[removedGem] = countMap[removedGem]!! - 1
if (countMap[removedGem]!! == 0) {
countInRange--
}
}
}
return answer
}
}'Problem Solving > 프로그래머스' 카테고리의 다른 글
| 프로그래머스: 메뉴 리뉴얼 (Kotlin) (0) | 2022.04.11 |
|---|---|
| 프로그래머스: 입국 심사 (Kotlin) (0) | 2022.04.04 |
| 프로그래머스: 프린터 (Kotlin) (0) | 2022.03.31 |
| (Java) 프로그래머스 - 아이템 줍기 (0) | 2022.03.12 |
| [프로그래머스] 순위 (Kotlin) - 플로이드 와샬 사용하지 않고 풀기 (0) | 2022.02.14 |