StringTokenizer를 사용해보자

한포도·2024년 11월 25일
DPStringTokenizer백준알고리즘
0

Coding Test

목록 보기
1/2
post-thumbnail

백준 동전2 문제의 최적화 기법 분석

안녕하세요! 오늘은 백준의 동전2 문제에서 사용한 두 가지 접근 방식을 비교하면서, 실행 시간을 단축시키기 위해 적용한 최적화 기법들을 살펴보려고 합니다. 실무에서 사용할 때 주의할 점들도 함께 이야기해보겠습니다.

첫번째 나의 정답

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(" ").map { it.toInt() }
    val coins = buildSet {
        repeat(n) {
            add(readLine().toInt())
        }
    }.sorted()
    
    val dp = IntArray(k + 1) { 10001 }
    dp[0] = 0 
    
    coins.forEach { coin ->
        for (amount in coin..k) {
            dp[amount] = minOf(dp[amount], dp[amount - coin] + 1)
        }
    }
    
    print(if (dp[k] == 10001) -1 else dp[k])
}

깔끔하고 이해하기 쉽습니다. Kotlin의 표준 라이브러리를 활용해서 간결하게 작성된 코드입니다. DP를 사용해야겠다 해서 사용했지만 묘하게 실행이 오래걸려서 이거 한번 줄여보자! 하고 삽질을 막 했습니다.

단축 버전 정답

import java.util.*

fun main() {
    val br = FastReader()
    val n = br.nextInt()
    val k = br.nextInt()

    val coins = IntArray(n)
    var size = 0
    var minCoin = Int.MAX_VALUE

    for (i in 0 until n) {
        val coin = br.nextInt()
        if (coin <= k && !containsCoin(coins, size, coin)) {
            coins[size++] = coin
            if (coin < minCoin) minCoin = coin
        }
    }

    if (size == 0 || minCoin > k) {
        print(-1)
        return
    }

    val dp = IntArray(k + 1) { 10001 }
    dp[0] = 0
  
    if (size > 1) insertionSort(coins, size)

    for (i in 0 until size) {
        val coin = coins[i]
        var amount = coin
        while (amount <= k) {
            val newCount = dp[amount - coin] + 1
            if (newCount < dp[amount]) {
                dp[amount] = newCount
            }
            amount++
        }
        
        if (dp[k] < 10001) {
            val remainingMin = (k - amount) / coin + 1
            if (remainingMin >= dp[k]) break
        }
    }
    
    print(if (dp[k] == 10001) -1 else dp[k])
}

private class FastReader {
    private val br = System.`in`.bufferedReader()
    private var st: StringTokenizer? = null
    
    fun nextInt(): Int {
        while (st == null || !st!!.hasMoreTokens()) {
            st = StringTokenizer(br.readLine())
        }
        return st!!.nextToken().toInt()
    }
}

private fun containsCoin(coins: IntArray, size: Int, target: Int): Boolean {
    for (i in 0 until size) {
        if (coins[i] == target) return true
    }
    return false
}

private fun insertionSort(arr: IntArray, size: Int) {
    for (i in 1 until size) {
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}

FastReader를 활용한 입력 최적화

입력 처리에서 가장 큰 성능 차이를 만드는 부분이 바로 FastReader입니다. 

private class FastReader {
    private val br = System.`in`.bufferedReader()
    private var st: StringTokenizer? = null
    
    fun nextInt(): Int {
        while (st == null || !st!!.hasMoreTokens()) {
            st = StringTokenizer(br.readLine())
        }
        return st!!.nextToken().toInt()
    }
}

💡 FastReader의 최적화 원리

  1. StringTokenizer 재사용

    • 일반적인 split(" ")는 매번 새로운 String 배열을 생성합니다
    • StringTokenizer는 객체를 재사용해서 메모리를 아끼고 GC 부하도 줄입니다
    • 정규식 기반 split보다 단순 토큰 파싱이 더 빠릅니다

  2. BufferedReader 최적화

    • BufferedReader를 클래스 레벨에서 한 번만 생성해서 재사용합니다
    • System.in을 매번 새로 감싸지 않아도 되니 시스템 리소스를 절약할 수 있습니다
    • 버퍼링된 데이터를 한 번에 읽어와서 처리하므로 디스크 접근이 줄어듭니다

  3. 직접 정수 파싱

    • split(" ").map { it.toInt() }는 리스트 생성과 map 변환 과정이 필요합니다
    • FastReader는 토큰을 바로 정수로 변환하니 중간 과정이 없어서 훨씬 빠릅니다
    • 문자열을 숫자로 변환할 때 다음과 같은 최적화를 수행합니다:
      private fun parseInteger(s: String): Int {
    var num = 0
    var i = 0
    var isNegative = false
    
    // 부호 처리
    if (s[0] == '-') {
        isNegative = true
        i++
    }
    
    // 직접 숫자 계산 (charAt - '0'이 Integer.parseInt보다 빠름)
    while (i < s.length) {
        num = num * 10 + (s[i] - '0')
        i++
    }
    
    return if (isNegative) -num else num
}
    • 이 방식은 Java의 Integer.parseInt()보다 2-3배 정도 빠릅니다
    • 문자열 파싱 시 추가 객체를 생성하지 않습니다
    • 예외 처리 로직이 없어 순수 계산에만 집중합니다

🔍 StringTokenizer에 대해 더 자세히 알아보기

StringTokenizer는 Java 1.0부터 있던 클래스입니다. 문자열을 토큰으로 분리하는 가장 기본적인 방법입니다. 현대 Java/Kotlin 개발에서는 잘 사용되지 않지만, 알고리즘 문제 풀이에서는 여전히 많이 사용됩니다.

기본 사용법과 제약사항

// split 사용 시
val input = "1 2 3 4 5"
val numbers = input.split(" ").map { it.toInt() }  // 새로운 문자열 배열 생성 + map으로 변환

// StringTokenizer 사용 시
val st = StringTokenizer(input)
while (st.hasMoreTokens()) {
    val number = st.nextToken().toInt()  // 바로 파싱, 중간 배열 없음
}

입력 데이터 형태에 따른 제약

  1. 단순한 구분자
// 기본 공백 구분 - 잘 동작
val st1 = StringTokenizer("1 2 3")

// 다중 구분자 설정 - 가능하지만 권장하지 않음
val st2 = StringTokenizer("1,2;3", ",;")

// 복잡한 패턴 - StringTokenizer로 처리 불가
val complexInput = "key1=value1;key2=value2"  // key-value 쌍 파싱은 적절하지 않음
  1. 데이터 포맷
// 잘 동작하는 경우
"1 2 3 4 5"         // 공백으로 구분된 숫자
"abc def ghi"       // 공백으로 구분된 단어

// 주의가 필요한 경우
"1, 2, 3, 4, 5"     // 쉼표와 공백이 같이 있는 경우
"1  2     3"        // 다중 공백

// 부적절한 경우
"[1,2,3],[4,5,6]"   // 배열 형태의 데이터
"name=kim;age=20"   // key-value 형태
"2023-11-25"        // 날짜 형식

장점

  • 문자열을 파싱할 때 중간에 배열을 만들지 않습니다
  • 내부적으로 문자 단위로 순회하면서 처리하기 때문에 빠릅니다
  • 메모리 사용량이 정규식 기반 split보다 훨씬 적습니다
  • 특히 공백으로 구분된 숫자를 읽을 때 최고의 성능을 보여줍니다

단점

  • Java 1.0 시절 API라 현대적인 기능이 없습니다
  • 한 번 파싱한 토큰은 다시 돌아갈 수 없습니다 (Iterator 패턴)
  • 정규식을 지원하지 않아서 복잡한 패턴은 처리하지 못합니다
  • 불변성(immutability)을 보장하지 않아서 멀티스레드 환경에서 위험합니다
  • 연속된 구분자를 하나로 처리하지 않습니다 (split의 기본 동작과 다름)
  • 복잡한 데이터 구조나 중첩된 형식은 처리하기 어렵습니다

그래서 실무에서는 권장되지 않지만, 알고리즘 문제처럼 단순한 입력(특히 공백으로 구분된 숫자 데이터)을 빠르게 처리해야 하는 경우에는 아직도 좋은 선택이 될 수 있습니다.

⚠️ 실무에서 사용할 때 주의할 점

  1. 사용해도 괜찮은 경우

    • 알고리즘 문제 풀이처럼 순수하게 성능이 중요한 경우
    • 대량의 숫자 데이터를 빠르게 파싱해야 하는 경우
    • 레거시 시스템에서 성능 개선이 절실한 경우

  2. 피해야 하는 경우

    • 일반적인 웹 애플리케이션이나 서버 개발
    • 코드의 유지보수성이 중요한 프로젝트
    • 팀 프로젝트에서 다른 개발자들과 협업해야 하는 경우

  3. 대안

    • 입력 데이터 포맷을 JSON이나 Protocol Buffers 같은 표준 형식으로 바꾸기
    • Scanner나 BufferedReader를 활용한 더 현대적인 방식 사용하기
    • Kotlin의 표준 라이브러리 기능 활용하기

동전 처리 최적화

두 번째로 살펴볼 부분은 동전을 처리하는 방식입니다.

val coins = IntArray(n)
var size = 0
var minCoin = Int.MAX_VALUE

for (i in 0 until n) {
    val coin = br.nextInt()
    if (coin <= k && !containsCoin(coins, size, coin)) {
        coins[size++] = coin
        if (coin < minCoin) minCoin = coin
    }
}

💡 최적화 원리

  1. 조기 필터링

    • k보다 큰 동전은 애초에 저장하지 않습니다
    • 중복되는 동전도 제외
    • 최소 동전값을 추적해서 불가능한 케이스를 빨리 걸러낼 수 있습니다

  2. 메모리 최적화

    • Set 대신 배열을 사용해서 메모리 사용량을 줄임
    • 정렬도 삽입 정렬을 사용해서 추가 메모리 할당을 피했습니다

결론

이러한 최적화 기법들은 백준과 같은 알고리즘 문제 풀이에서는 좋을수도 있지만 잘 보고 활용합시다! 1/2로 줄였지만 코드는 그렇지 않아버림...

  1. 실제로 이 정도의 성능 최적화가 필요한 상황인가
  2. 코드의 유지보수성과 가독성 측면에서 적절한가
  3. 표준 라이브러리 사용으로도 충분한가
profile
한포도
응애 개발맨
다음 포스트

Kotlin 확장 함수를 활용한 코딩 테스트

0개의 댓글