import kotlin.math.abs
class Solution {
fun threeSumClosest(nums: IntArray, target: Int): Int {
var answerDiffer = Int.MAX_VALUE // 절대값(target - target에 가장 가까운 합)
var answerSum = 0 // target에 가장 가까운 합
nums.sort() // 투 포인터로 해결하기 위해 정렬
for (i in 0 until nums.size - 2) {
var start = i + 1
var end = nums.lastIndex
while (start < end) {
val tempSum = nums[i] + nums[start] + nums[end]
val tempDiffer = abs(target - tempSum)
// target과 차이가 더 작은 합을 발견하면 정답을 갱신
if (tempDiffer < answerDiffer) {
answerDiffer = tempDiffer
answerSum = tempSum
}
if (tempSum > target) {
end--
} else if (tempSum < target) {
start++
} else {
return tempSum // 정답은 꼭 하나라고 했으므로 리턴
}
}
}
return answerSum
}
}
피드백
투 포인터는 정렬된 배열있고 특정 기준이 있을 때, 기준에 가장 부합하는 최적의 두 수를 빠르게 찾을 때 사용할 수 있다. 이분 탐색과 조건이 아주 유사하다.
모든 보석을 포함하는 구간(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
}
}
orders의 원소마다 즉, 각 주문마다 course에서 주어진 코스 요리의 단품 메뉴 개수별 모든 조합을 구한다. 문자열을 (오름차순으로 정렬해놨기 때문에 앞에서부터 조합을 구성하면 자연스럽게 오름차순이 된다.)
각 조합을 문자열로 변환해서 Map에 count한다.
길이 별로 count 값이 가장 큰 조합을 모두 리스트에 추가한다.
리스트를 오름차순 정렬해서 반환한다.
풀이
카카오 2021 공채에 2번으로 나왔던 문제로 프로그래머스에서 난이도가 2로 되어 있지만, 코테 정답률은 25%로 많은 사람들이 어려워 했다. 삼성 A형 처럼 약간의 단계를 거치며 풀어야 하기 때문에, 조합 구하는 방법과 Map 조작에 익숙하지 않다면 풀다가 멘탈이 터질 수 있다.
풀이를 요약해보면 어렵진 않다. 각 주문마다 course 원소에 해당하는 길이마다 조합을 구해서 빈도 수를 count한다. 그리고 제일 많이 count된 조합을 모두 구한다.
근데 막상 풀려고 하면 부담이 된다. "아니 조합을 길이 별로 구해야 돼?" 조합에 자신이 없는 상태에서 만나면 이렇게 무식하게 푸는 게 맞는 건지 의구심이 들 수도 있다. 그런데 그렇게 푸는 거 맞다(ㅡ_ㅡ)
그리고 길이 별로 조합을 따로 저장한다. 단품 개수별로 가장 많이 나온 조합을 찾아야 하기 때문이다. 길이가 최대 10이므로 배열로 길이를 구분하고, 그 안에 Map을 저장할 수 있다.
마지막으로 길이별 Map을 value(빈도 수) 내림차순으로 정렬해서 첫 번째 원소의 빈도 수와 같은 key(조합)를 모두 리스트에 저장한다. 그리고 리스트를 정렬하면 정답을 구할... 수도 있고 틀릴 수도 있다. (1) 빈도 수가 2 이상인 조합만 구해야 하고, (2) 각 조합도 오름차순으로 정렬되어야 하기 때문이다.
따라서, 다 구하고 나서 각 조합(원소)을 정렬하거나, 처음에 order의 각 값을 오름차순으로 정렬을 해놓고 조합을 구할 때 왼쪽에서부터 순서대로 선택을 해서 자연스럽게 오름차순으로 만들 수도 있다.
정리
(1) 각 주문을 오름차순으로 정렬한다.
private val mOrders = mutableListOf<CharArray>()
//...
for (order in orders) {
mOrders.add(order.toCharArray().sortedArray())
}
(2) 개수 별로 조합의 빈도 수를 count할 배열과 Map을 준비한다.
// 조합을 저장할 배열 - combs[단품 개수][Map<조합, 빈도 수>]
private val combs: Array<MutableMap<String, Int>> = Array(11){ HashMap() }
(3) 주문마다 단품 메뉴 개수(길이) 별로 조합을 구한다.
for (order in mOrders) {
for (combSize in course) {
findComb(0, CharArray(combSize), order, 0) // 주문마다 필요한 길이 별 조합을 구한다
}
}
//...
// combCount: 지금까지 선택한 메뉴의 개수, currentComb: 선택한 메뉴 저장하는 배열
// order: 주문(선택할 메뉴 후보들), startIdx: 선택 가능한 메뉴 범위의 시작 - startIdx ~ order.lastIndex
private fun findComb(combCount: Int, currentComb: CharArray, order: CharArray, startIdx: Int) {
if (combCount >= currentComb.size) { // 다 뽑았으면,
// 조합을 문자열로 변환
val combination = StringBuilder().append(currentComb).toString()
if (combs[currentComb.size].contains(combination).not()) {
combs[currentComb.size][combination] = 0
}
combs[currentComb.size][combination] = combs[currentComb.size][combination]!! + 1
return
}
// 남아있는 메뉴 개수 < 앞으로 더 뽑아야할 메뉴 개수
if (order.size - startIdx < currentComb.size - combCount) return
// order[startIdx ~ order.lastIndex]에서 하나를 선택한다
for (i in startIdx until order.size) {
currentComb[combCount] = order[i]
findComb(combCount + 1, currentComb, order, i + 1)
}
}
(4) 길이 별로 가장 많이 나온 조합을 저장한다.
for (size in course) {
if (combs[size].isEmpty()) continue // 해당 길이의 조합이 없을 수도 있다
// map을 리스트로 바꾸면 Pair<key, value> 형태가 된다
// value 기준 내림차순으로 정렬
val combList = combs[size].toList().sortedByDescending { it.second }
val maxCount = combList[0].second
if (maxCount <= 1) continue // 2개 이상 나온 조합이어야 함
// 가장 긴 조합들을 저장한다
for (order in combList) {
if (maxCount > order.second) break
answer.add(order.first)
}
}
전체 코드
import java.util.*
class Solution {
// 조합을 저장할 배열 - combs[단품 개수][Map<조합, 빈도 수>]
private val combs: Array<MutableMap<String, Int>> = Array(11){ HashMap() }
private val mOrders = mutableListOf<CharArray>() // 주문 마다 오름차순의 CharArray로 바꿔서 저장한다
fun solution(orders: Array<String>, course: IntArray): Array<String> {
val answer = mutableListOf<String>()
for (order in orders) {
mOrders.add(order.toCharArray().sortedArray())
}
for (order in mOrders) {
for (combSize in course) {
findComb(0, CharArray(combSize), order, 0) // 주문마다 필요한 길이 별 조합을 구한다
}
}
for (size in course) {
if (combs[size].isEmpty()) continue // 해당 길이의 조합이 없을 수도 있다
// map을 리스트로 바꾸면 Pair<key, value> 형태가 된다
// value 기준 내림차순으로 정렬
val combList = combs[size].toList().sortedByDescending { it.second }
val maxCount = combList[0].second
if (maxCount <= 1) continue // 2개 이상 나온 조합이어야 함
// 가장 긴 조합들을 저장한다
for (order in combList) {
if (maxCount > order.second) break
answer.add(order.first)
}
}
return answer.sorted().toTypedArray()
}
// combCount: 지금까지 선택한 메뉴의 개수, currentComb: 선택한 메뉴 저장하는 배열
// order: 주문(선택할 메뉴 후보들), startIdx: 선택 가능한 메뉴 범위 - startIdx ~ order.lastIndex
private fun findComb(combCount: Int, currentComb: CharArray, order: CharArray, startIdx: Int) {
if (combCount >= currentComb.size) { // 다 뽑았으면,
// 조합을 문자열로 변환
val combination = StringBuilder().append(currentComb).toString()
if (combs[currentComb.size].contains(combination).not()) {
combs[currentComb.size][combination] = 0
}
combs[currentComb.size][combination] = combs[currentComb.size][combination]!! + 1
return
}
// 남아있는 메뉴 개수 < 앞으로 더 뽑아야할 메뉴 개수
if (order.size - startIdx < currentComb.size - combCount) return
for (i in startIdx until order.size) {
currentComb[combCount] = order[i]
findComb(combCount + 1, currentComb, order, i + 1)
}
}
}
회고
알고리즘이나 아이디어가 어려운 문제는 아니었는데, 조합이나 Map을 다루는 것이 능숙하지 않아서 어렵게 느꼈던 것 같다. 조합 구하는 거 자신 있다고 생각했었는데 착각이었다..ㅋㅋ. 복잡한 문자열 관련 문제들 중 대부분이 조합과 Map을 사용하는 것 같아서 이번 기회에 정리하고 넘어간다.
if (심사된 인원 >= 입국 인원) --> end = mid - 1 (최소 값을 구하기 위해)
else --> start = mid + 1 (제한 시간이 짧아서 전부 검사할 수 없기 때문)
이분 탐색이 끝나면 start를 반환한다.
풀이
처음엔 우선순위 큐를 이용하는 방법을 시도했다. pq에서 뺄 때마다 지금까지 걸린 시간 += 검사 시간, 검사한 인원이 n보다 클 때까지 진행하는 방식이었다. 그런데 최악의 경우 시간 복잡도가 10억(명) * log(십만)이라 그런지 시간 초과가 났다.
이 문제는 대놓고 이분 탐색 카테고리에 있던 문제였어서 이분 탐색에 초점을 맞추고 접근해봤다.
뭘 기준으로 이분 탐색을 할 수 있을까..
경험상 직관적이지 않던 이분 탐색 문제들은 모두 정답이 될 것을 기준으로 두고 있었다. 그래서 걸리는 시간을 기준으로 생각해봤다. 시간을 정해놓고, 시간 안에 모든 인원을 심사할 수 있는지 확인하는 것이다.
제한 시간 안에 모두 심사할 수 있는지는 심사관마다 걸리는 시간을 제한 시간으로 나누면 구할 수 있다. 시간 복잡도는 O(심사관 수)이다.
/**
* 제한 시간 안에 모두 검사할 수 있는지 확인한다
* @param) time: 제한 시간
*/
fun isPossibleInTime(time: Long, officers: IntArray, numOfPeople: Int): Boolean {
var checkCount: Long = 0
for (checkTime in officers) {
checkCount += time / checkTime // 해당 심사관이 시간 안에 검사할 수 있는 인원 수
}
return if (checkCount >= numOfPeople) true else false
}
이분 탐색의 범위
최소 시간: 심사관 수 >= 입국자 수, 각 심사관이 검사하는데 걸리는 시간 1분 -> 1분
최대 시간: 심사관 1명, 심사 시간 10억 분, 입국자 10억 명 -> 10억 * 10억 분
const val MAX_SIZE: Long = 1_000_000_000
...
var start: Long = 1
var end: Long = MAX_SIZE * MAX_SIZE
탐색 범위 좁히기
걸리는 시간의 최소 값을 구하는 것이므로
시간 안에 모두 심사 가능 -> 더 짧은 시간에 대해 확인해보기 위해 end = mid - 1
불가능 -> 현재 시간이 너무 짧다는 의미이므로 start = mid + 1로 범위를 좁혀나간다.
그리고 이분 탐색이 종료됐을 때 start 값이 구하고자 하는 답이 된다.
코드
/* 걸린 시간을 기준으로 이분 탐색 */
import java.util.*
const val MAX_SIZE: Long = 1_000_000_000
class Solution {
fun solution(n: Int, times: IntArray): Long {
var start: Long = 1 // 심사관 >= 입국자, 검사 시간: 1분
var end: Long = MAX_SIZE * MAX_SIZE // 심사관: 1명, 검사 시간: 10억 분, 입국자: 10억 명
while(start <= end) {
val mid = (start + end) / 2
if (isPossibleInTime(mid, times, n)) {
end = mid - 1
} else {
start = mid + 1
}
}
return start
}
/**
* 제한 시간 안에 모두 검사할 수 있는지 확인한다
* @param) time: 제한 시간
*/
fun isPossibleInTime(time: Long, officers: IntArray, numOfPeople: Int): Boolean {
var checkCount: Long = 0
for (checkTime in officers) {
checkCount += time / checkTime // 해당 심사관이 시간 안에 검사할 수 있는 인원 수
}
return if (checkCount >= numOfPeople) true else false
}
}