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://www.acmicpc.net/problem/1038

 

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를

www.acmicpc.net

프로세스

  1. 재귀(백트래킹)를 사용해서 9에서 오른쪽 or 0에서 왼쪽으로 감소/증가 하는 방향으로 감소하는 수를 모두 구한다.
  2. 오름차순으로 정렬한다.
  3. n > 1023이라면 -1을, 그렇지 않다면 n번째 수를 출력한다.

풀이

처음엔 앞에 있는 수로 다음 수를 구하는 것 같아서 DP를 떠올렸지만 경우의 수가 아닌 n번째 수를 구하는 방법을 생각해내지 못했다.

 

다음은 완전 탐색으로 풀 수 있는지 생각해본다. 수의 범위: 0 ~ 9876543210, 하지만 이 숫자를 전부 확인하면 시간 초과다. 

 

어떻게 해야할까

 

각 자릿수는 일정한 방향성을 갖는다. 왼쪽의 수가 7이라면 오른쪽에 올 수 있는 수는 6~0이다. 이 아이디어에 착안하면 재귀적으로 감소하는 수만 골라서 모두 구할 수 있다. 그리고 이것을 정렬하면 n번째 감소하는 수를 구할 수 있다.

 

재귀 함수의 구체적인 구현은 다음과 같다

 1. 이전 수의 마지막 자리 숫자보다 작은 수를 오른쪽에 추가해서 새로운 숫자를 구한다. -> 나머지 연산 사용

 2. 새로 구한 숫자로 재귀 함수를 호출한다

for (i in lastDigit - 1 downTo 0) {
	val newNumber = number * 10 + i  // 오른쪽에 감소하는 수 추가
	addDecreasingNumber(newNumber)
}

 3. 호출된 함수는 숫자를 감소하는 수에 추가한다

 4. 마지막 자리 수가 0이라면 재귀 함수를 종료한다.

 

재귀 함수 소스 코드

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

위 방식은 왼쪽에서 오른쪽으로 숫자를 추가하면서 감소하는 방향으로 수를 구하고 있다. 반대로, 오른쪽에서 증가하는 방향으로 왼쪽에 숫자를 추가하는 방식도 가능하다.

 

감소하는 수를 구할 수 있을지 없을지는 어떻게 판단할까?

9 8 7 6 5 4 3 2 1 0에서 9531을 도출하는 방법을 경우의 수 관점에서 생각해볼 수 있다.

9, 5, 3, 1을 선택, 8, 7, 6, 4, 2, 0은 선택하지 않는 것이다. 각 자릿수를 선택/선택하지 않는 모든 경우의 수는 2^10개이고, 모두 선택하지 않는 경우는 없기 때문에 2^10 - 1 = 1023 개가 나온다. 따라서, n > 1022라면 감소하는 수를 구할 수 없다.

코드 (Kotlin)

1. 감소하는 방향으로 백트래킹

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else if (targetIndex >= 1023){ // 감소하는 수의 개수는 1023개다
        println(-1)
    } else {
        for (i in 0..9) {
            addDecreasingNumber(i.toLong())
        }
        decreasingNumbers.sort()
        println(decreasingNumbers[targetIndex])
    }
}

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

2. 증가하는 방향 

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()
    
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else {
        addDecreasingNumber(0, 0, 0)
        decreasingNumbers.sort()

        if (targetIndex > decreasingNumbers.lastIndex) {
            println(-1)
        } else {
            println(decreasingNumbers[targetIndex])
        }
    }
}

fun addDecreasingNumber(startNumber: Int, beforeLength: Int, beforeNumber: Long) {
    if (beforeLength >= 10 || startNumber >= 10) {
        return
    }

    for (i in startNumber..9) {
        val newNumber = i * (10.0).pow(beforeLength).toLong() + beforeNumber
        decreasingNumbers.add(newNumber)
        addDecreasingNumber(i + 1, beforeLength + 1, newNumber)
    }
}

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
    }
}

 

https://www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

프로세스

  1. 완전 탐색을 떠올린다. 연산자 4개, 자리는 10개이므로 시간 복잡도(경우의 수)는 4^10 = 1,048,576이다.
  2. 재귀 함수를 사용한다.
    1. calculate(왼쪽 피연산자(operand), 오른쪽 피연산자를 가리킬 인덱스)로 구성한다.
    2. 마지막 인덱스까지 계산할 때마다 최대 값, 최소 값을 갱신한다.
    3. 각 연산자마다 operand와 현재 피연산자를 계산해서 재귀함수를 호출한다.

풀이

어렵지 않았지만 재귀 함수를 연습하기 좋았다.

 

가장 먼저 완전 탐색을 떠올릴 수 있는데, 연산자 들어갈 자리가 최대 10자리이고 연산자가 4개 뿐이다. 따라서 모든 자리에 연산자를 한 번씩 넣어서 모든 경우의 수를 확인할 경우 4^10 = 1,048,576개 라서 충분히 완전 탐색으로 해결할 수 있다.

재귀 함수

재귀 함수 구성은 배열 1 2 3 4 5 6이 있다고 가정했을 때, (1 2) (연산자) (3 4 5 6)와 같이 나눌 수 있다. 즉, 지금까지 계산한 왼쪽 피연산자와 배열의 나머지에서 그 다음에 계산할 숫자의 현재 인덱스를 인자로 갖게 한다.

fun calculate(operand1: Int, idx: Int)

그리고 인덱스가 마지막 인덱스를 넘으면 전부 계산한 것이기 때문에 최대 값, 최소 값과 비교하여 정답을 갱신한다.

if (idx >= numbers.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

종료 조건이 아니라면, 각 연산자마다 계산해서 다음 자리에 해당하는 연산자를 넣어보기 위해 재귀 함수를 호출한다.

 for (i in operators.indices) {
        if (operators[i] <= 0) continue

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max
import kotlin.math.min

lateinit var numbers: IntArray
lateinit var operators: IntArray // +, -, *, /
var maxValue = Int.MIN_VALUE
var minValue = Int.MAX_VALUE

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    numbers = with(StringTokenizer(readLine())) {
        IntArray(size) { this.nextToken().toInt() }
    }
    operators = with(StringTokenizer(readLine())) {
        IntArray(4) { this.nextToken().toInt() }
    }

    calculate(numbers[0], 1)

    println(maxValue)
    println(minValue)
}

fun calculate(operand1: Int, idx: Int) {
    if (idx >= numbers.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

    for (i in operators.indices) {
        if (operators[i] <= 0) continue

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }
}

 

+ Recent posts