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
}
}
피드백
투 포인터는 정렬된 배열있고 특정 기준이 있을 때, 기준에 가장 부합하는 최적의 두 수를 빠르게 찾을 때 사용할 수 있다. 이분 탐색과 조건이 아주 유사하다.
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을 사용하는 것 같아서 이번 기회에 정리하고 넘어간다.
우선순위가 더 큰 문서가 있는지 연결 리스트의 모든 문서를 확인한다. (total O(N^2))
있다 -> 문서를 큐에 다시 넣는다.
없다 -> 문서를 출력(삭제)하고 removeCount++
출력 문서 == location 문서 -> removeCount 반환
2. 우선순위 큐, 출력 확인용 배열 사용: O(NlogN)
우선순위 큐(PQ)에 문서를 모두 넣는다. (total O(NlogN))
큐에서 문서를 꺼낸다.
PQ에서 우선순위가 더 높은 문서가 있는지 확인한다. (total O(N))
우선순위 큐 제일 위에 있는 문서를 확인한다.
이미 출력한 문서라면(isPrinted 확인) PQ에서 제거하고 다시 확인한다.
더 높은 문서가 있다 -> 큐에 다시 넣는다
없다 -> 문서 출력, removeCount++, isPrinted에 체크
출력한 문서 == location 문서 -> removeCount 반환
풀이
1. 연결 리스트 사용
가장 쉬운 방법은 큐에서 문서를 꺼낼 때마다 우선 순위가 더 높은 문서가 있는지 모두 확인하는 것이다. 끝에 어떤 문서서가 있을지 알 수 없어서 매번 연결 리스트를 끝까지 탐색(O(N))해야 하므로 총 O(N^2)이 걸린다. 하지만 문서가 최대 100개이므로 O(N^2)으로 해결할 수 있다.
2. 우선순위 큐와 출력 확인용 배열 사용
우선순위 큐와 출력 확인용 배열을 사용하면 O(nlogn)으로 좀 더 빠르게 해결할 수 있다.
O(N^2)이 걸렸던 이유는 매번 다른 문서를 전부 확인해야 했기 때문이다. 따라서 다른 문서의 우선 순위를 더 빠르게 확인할 수 있다면 시간 복잡도를 줄일 수 있다.
우선순위 큐
문서를 우선순위 큐(PQ)에 따로 넣어놓으면, PQ의 맨 위에 있는 문서를 통해 순위가 더 높은 문서가 있는지 바로 확인이 가능하다.
val doc = queue.poll()
// 우선 순위가 더 높은 문서가 있는지 확인
if (doc.priority >= pq.peek().priority) {
removeCount++
isPrinted[doc.id] = true
}
하지만 문제는 문서를 출력할 때 PQ에서 해당 문서를 삭제하기가 번거롭다는 것이다. 왜냐면 맨 위에 있는 문서가 우선 순위가 같은 다른 문서일 수도 있기 때문이다. PQ에서 일일이 삭제를 할 수도 있는데, 그러면 총 O(nlogn)의 시간이 걸린다.
출력 확인 배열
좀 더 빠른 방법은 출력됐음을 확인하는 배열을 사용하는 것이다. 출력할 때 PQ에서 삭제하는 것이 아니라 배열에 체크를 하고, 다음 문서를 확인할 때 PQ의 맨 위에 있는 것이 이미 출력된 문서라면 제거하고 다음 문서를 가져온다. 이렇게 하면 PQ에서 문서를 제거하는 데 총 O(N)이 걸린다.
// 출력된 문서 제거
while (isPrinted[pq.peek().id]) {
pq.poll()
}
코드 (우선순위 큐)
import java.util.*
data class Document(val id: Int, val priority: Int)
class Solution {
fun solution(priorities: IntArray, location: Int): Int {
var removeCount = 0
val queue: Queue<Document> = LinkedList()
val pq = PriorityQueue(compareByDescending<Document>{it.priority})
val documents = Array<Document>(priorities.size) { i ->
Document(i, priorities[i])
}
val isPrinted = BooleanArray(documents.size)
for (doc in documents) {
queue.add(doc)
pq.add(doc)
}
while(queue.isNotEmpty()) {
// 출력된 문서 제거
while (isPrinted[pq.peek().id]) {
pq.poll()
}
val doc = queue.poll()
// 우선 순위가 더 높은 문서가 있는지 확인
if (doc.priority >= pq.peek().priority) {
removeCount++
isPrinted[doc.id] = true // 출력 체크
if (doc.id == location) break
} else {
queue.add(doc)
}
}
return removeCount
}
}