[Algorithm/Kotlin] 백준 10816번 숫자 카드 2: 시간 복잡도를 계산해 시간초과 해결하기

 

이 문제를 풀때, 처음에는 단순히 이중 반복문을 떠올려 문제를 해결했지만 입력 크기를 고려하지 못해 시간 초과 실패를 경험했습니다.
이 경험을 토대로, 단순히 문제를 푸는 것에 그치지 않고 시간 복잡도를 계산하고 효율적인 알고리즘을 설계하는 것이 얼마나 중요한지를 배웠습니다.

이후 시간 복잡도를 다시 계산하고, 효율적인 방법(groupingBy)을 도입해 문제를 해결할 수 있었습니다.

각각의 문제 풀이법과 시간 복잡도 계산 내용을 정리해 두고자 합니다.

---

문제 설명

숫자 카드는 정수 하나가 적혀 있는 카드입니다. 상근이는 숫자 카드 N개를 가지고 있으며, 정수 M개가 주어졌을 때, 이 수가 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성해야 합니다.

• 입력 조건
  1. 첫째 줄: 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)
  2. 둘째 줄: 숫자 카드에 적힌 정수들 (각 정수는 -10,000,000 ≤ 정수 ≤ 10,000,000)
  3. 셋째 줄: 구해야 할 정수의 개수 M (1 ≤ M ≤ 500,000)
  4. 넷째 줄: 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수들 (각 정수는 -10,000,000 ≤ 정수 ≤ 10,000,000)
• 출력 조건
  • 각 M개의 정수에 대해, 숫자 카드에 몇 개가 적힌 숫자 카드를 상근이가 가지고 있는지 공백으로 구분해 출력합니다.

---

문제 해결 아이디어

1. 이중 반복문 방식 (O(M × N))
   •    M개의 정수를 순회하며 각 수에 대해 N개의 숫자 카드와 비교하는 방식입니다.
2. 코틀린 내장 메서드 groupingBy를 사용한 방식 (O(N + M))
   •    숫자 카드 리스트 nList의 등장 횟수를 미리 계산하여 맵(Map) 형태로 저장합니다.
   •    구해야 할 리스트 mList의 각 숫자에 대해 맵에서 빠르게 등장 횟수를 조회합니다.
   •    연산 횟수를 크게 줄이고 시간 초과를 방지할 수 있습니다.

---

구현 코드

1. 이중 반복문 방식

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    br.readLine()
    val nList = br.readLine().split(" ").map { it.toInt() }
    br.readLine()
    val mList = br.readLine().split(" ").map { it.toInt() }

    for (m in mList) {
        var count = 0
        for (n in nList) {
            if (n == m) count++
        }
        bw.write("$count ")
    }

    bw.flush()
    bw.close()
}

2. groupingBy 방식

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    br.readLine()
    val nList = br.readLine().split(" ").map { it.toInt() }
    br.readLine()
    val mList = br.readLine().split(" ").map { it.toInt() }

    // 등장 횟수 계산
    val countMap = nList.groupingBy { it }.eachCount()

    // mList 각 숫자의 등장 횟수 출력
    mList.forEach { m ->
        bw.write("${countMap[m] ?: 0} ")
    }

    bw.flush()
    bw.close()
}

---

시간 복잡도 분석

1. 이중 반복문 방식

• 시간 복잡도: O(M × N)
  • 외부 루프: mList의 크기 M
  • 내부 루프: nList의 크기 N
  • 총 시간 복잡도: O(M × N)
• 최악의 경우 연산 횟수:
  • 2500억 번의 연산이 필요하므로, 문제에서 주어진 10,000,000 값을 넘게 되어 시간 초과가 발생 합니다.
• N = 500,000, M = 500,000
  M × N = 500,000 × 500,000 = 250,000,000,000

2. groupingBy 방식

• 시간 복잡도: O(N + M)
  • nList의 등장 횟수 계산: O(N)
  • mList의 각 숫자 조회: O(M) (맵에서의 조회는 평균적으로 O(1))
  • 총 시간 복잡도: O(N + M)
• 최악의 경우 연산 횟수:
  • 100만 번의 연산으로, 시간 초과 없이 문제를 해결할 수 있습니다.
• N = 500,000, M = 500,000
  N + M = 500,000 + 500,000 = 1,000,000

---

문제링크: https://www.acmicpc.net/problem/10816 
참고: https://kotlinlang.org/api/core/kotlin-stdlib/kotlin.collections/grouping-by.html