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)

  1. 보석 종류의 개수를 센다 (HashSet 사용)
  2. 구간 길이를 기준으로 이분 탐색을 한다. 
    1. 모든 보석을 포함하는 구간(mid)을 찾았다 -> 정답을 비교,갱신하고 최소 값을 찾기 위해 end = mid - 1
    2. 모든 보석을 포함하는 구간이 없다 -> 길이를 늘려서 (이분 탐색 구간을 오른쪽으로 이동) 확인하기 위해 start = mid + 1
  3. 보석 포함 구간을 찾는 과정은 투 포인터(슬라이딩 윈도우) 알고리즘과 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
    }
}

https://programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

프로세스

  1. orders의 각 문자열을 오름차순으로 정렬해서 저장한다.
  2. orders의 원소마다 즉, 각 주문마다 course에서 주어진 코스 요리의 단품 메뉴 개수별 모든 조합을 구한다. 문자열을 (오름차순으로 정렬해놨기 때문에 앞에서부터 조합을 구성하면 자연스럽게 오름차순이 된다.)
  3. 각 조합을 문자열로 변환해서 Map에 count한다.
  4. 길이 별로 count 값이 가장 큰 조합을 모두 리스트에 추가한다.
  5. 리스트를 오름차순 정렬해서 반환한다. 

풀이

카카오 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을 사용하는 것 같아서 이번 기회에 정리하고 넘어간다.

https://programmers.co.kr/learn/courses/30/lessons/43238

 

코딩테스트 연습 - 입국심사

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한

programmers.co.kr

프로세스

  1. 걸리는 시간(제한 시간)을 기준으로 이분 탐색을 한다.
  2. 제한 시간 안에 총 몇 명을 심사할 수 있는지 확인한다.
    1. if (심사된 인원 >= 입국 인원) --> end = mid - 1 (최소 값을 구하기 위해)
    2. else --> start = mid + 1 (제한 시간이 짧아서 전부 검사할 수 없기 때문)
  3. 이분 탐색이 끝나면 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
    }
}

 

https://programmers.co.kr/learn/courses/30/lessons/42587

 

코딩테스트 연습 - 프린터

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린

programmers.co.kr

프로세스

1. 단순 연결 리스트 사용: O(N^2)

  1. 큐(연결 리스트)에서 문서를 꺼낸다. (total O(N))
  2. 우선순위가 더 큰 문서가 있는지 연결 리스트의 모든 문서를 확인한다. (total O(N^2))
    1. 있다 -> 문서를 큐에 다시 넣는다.
    2. 없다 -> 문서를 출력(삭제)하고 removeCount++
  3. 출력 문서 == location 문서 -> removeCount 반환

2. 우선순위 큐, 출력 확인용 배열 사용: O(NlogN)

  1. 우선순위 큐(PQ)에 문서를 모두 넣는다. (total O(NlogN))
  2. 큐에서 문서를 꺼낸다.
  3. PQ에서 우선순위가 더 높은 문서가 있는지 확인한다. (total O(N))
    1. 우선순위 큐 제일 위에 있는 문서를 확인한다.
    2. 이미 출력한 문서라면(isPrinted 확인) PQ에서 제거하고 다시 확인한다.
    3. 더 높은 문서가 있다 -> 큐에 다시 넣는다
    4. 없다 -> 문서 출력, removeCount++, isPrinted에 체크
  4. 출력한 문서 == 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
    }
}

 

+ Recent posts