[Algorithm/Kotlin] 백준 7568번 덩치: StringBuilder를 활용한 풀이법

 

 

덩치 등수 매기기 문제는 주어진 사람들의 키와 몸무게를 비교하여 각자의 상대적인 순위를 구하는 알고리즘 문제입니다. 이번 글에서는 문제를 두 가지 방식으로 해결하며, 효율성을 개선하기 위해 StringBuilder를 활용한 방식을 소개합니다.

 

문제 설명

덩치 비교 기준

사람의 덩치는 키와 몸무게 두 가지 값으로 표현됩니다. 예를 들어 (x, y)는 한 사람의 몸무게 x와 키 y를 나타냅니다. 두 사람 A와 B의 덩치 (x, y)와 (p, q)를 비교할 때:

• A의 덩치가 더 크다면: x > p 그리고 y > q를 만족해야 합니다.
• 두 값 중 하나라도 크거나 같지 않으면 A와 B의 덩치는 비교할 수 없습니다.

등수 계산

주어진 N명의 사람들에 대해:

1. 자신보다 덩치가 더 큰 사람의 수를 구합니다.
2. 등수는 이 수에 1을 더한 값입니다.

입력과 출력

입력 예제

5
55 185
58 183
88 186
60 175
46 155

 

출력 예제

2 2 1 2 5

 

 

• (55, 185)보다 큰 덩치를 가진 사람은 1명 → 등수: 2
• (58, 183)보다 큰 덩치를 가진 사람은 1명 → 등수: 2
• (88, 186)보다 큰 덩치를 가진 사람은 없음 → 등수: 1
• (60, 175)보다 큰 덩치를 가진 사람은 1명 → 등수: 2
• (46, 155)보다 큰 덩치를 가진 사람은 4명 → 등수: 5

 

첫 번째 풀이: 리스트를 이용한 방식

 

처음에는 각 사람의 덩치와 그보다 큰 덩치의 사람들을 리스트에 저장하여 결과를 확인했습니다.

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

    val n = br.readLine().toInt()
    val weightHeightPairs = mutableListOf<Pair<Int, Int>>()

    repeat(n) {
        val (weight, height) = br.readLine().split(" ").map { it.toInt() }
        weightHeightPairs.add(Pair(weight, height))
    }

    val results = mutableListOf<Pair<List<Int>, List<List<Int>>>>()

    for (i in weightHeightPairs.indices) {
        val currentPair = weightHeightPairs[i]
        val filteredPairs = weightHeightPairs.filterIndexed { index, otherPair ->
            index != i && otherPair.first > currentPair.first && otherPair.second > currentPair.second
        }
        results.add(currentPair.toList() to filteredPairs.map { it.toList() })
    }

    bw.write("$weightHeightPairs\n") // 원본 리스트 출력
    bw.write("결과: ${results.joinToString(separator = "\n") { "${it.first} -> ${it.second}" }}\n")

    bw.flush()
    bw.close()
}

 

 

출력 예제

[(55, 185), (58, 183), (88, 186), (60, 175), (46, 155)]
결과: [55, 185] -> [[88, 186]]
[58, 183] -> [[88, 186]]
[88, 186] -> []
[60, 175] -> [[88, 186]]
[46, 155] -> [[55, 185], [58, 183], [88, 186], [60, 175]]

 

장점

• 중간 데이터를 확인하기 쉽습니다.
• 디버깅에 용이하여 알고리즘의 흐름을 이해하기 좋습니다.

단점

• 중간 데이터를 저장하기 위해 추가 메모리가 필요합니다.
• 결과를 출력할 때 joinToString을 사용하여 리스트를 문자열로 변환해야 하므로, 성능이 다소 저하될 수 있습니다.

 

개선된 풀이: StringBuilder 활용

위 풀이의 단점을 개선하기 위해 StringBuilder를 사용하여 문자열을 바로 생성하는 방식으로 변경했습니다.

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

    val n = br.readLine().toInt()
    val weightHeightPairs = mutableListOf<Pair<Int, Int>>()

    repeat(n) {
        val (weight, height) = br.readLine().split(" ").map { it.toInt() }
        weightHeightPairs.add(Pair(weight, height))
    }

    val resultBuilder = StringBuilder()

    for (i in weightHeightPairs.indices) {
        val currentPair = weightHeightPairs[i]
        val filteredPairs = weightHeightPairs.filterIndexed { index, otherPair ->
            index != i && otherPair.first > currentPair.first && otherPair.second > currentPair.second
        }
        resultBuilder.append(filteredPairs.size + 1).append(" ")
    }

    bw.write(resultBuilder.toString().trim())

    bw.flush()
    bw.close()
}

 

출력 예제

2 2 1 2 5

 

개선 사항

1. 중간 데이터 제거:
   •    리스트 대신 문자열을 바로 생성하므로 메모리 사용량이 줄어듭니다.
2. 문자열 변환 작업 최소화:
   •    최종 출력 시 joinToString 없이 바로 결과를 생성합니다.
3. 성능 향상:
   •    대규모 데이터에서 더 효율적으로 동작합니다.

 

StringBuilder의 역할

StringBuilder란?

StringBuilder는 문자열을 효율적으로 생성, 수정할 수 있도록 도와주는 클래스입니다. 일반적으로 문자열 연결(+) 작업은 새로운 문자열 객체를 생성하므로 비효율적입니다. 반면, StringBuilder는 내부 버퍼를 사용하여 이러한 작업을 최적화합니다.

사용 이유

• 메모리 절약: 문자열 객체를 계속 생성하지 않으므로 메모리 사용량이 감소합니다.
• 성능 향상: 문자열 연결 및 수정 작업에서 빠른 속도를 제공합니다.

두 방식 비교

특징리스트 사용 방식StringBuilder 사용 방식

메모리 사용량	추가 리스트 저장 공간 필요	추가 메모리 사용 없음
문자열 생성	joinToString를 사용해 리스트를 문자열로 변환	문자열을 바로 생성
디버깅 용이성	중간 데이터를 저장하므로 디버깅이 쉬움	중간 데이터를 저장하지 않으므로 디버깅이 어려움
적합한 상황	중간 데이터를 자주 참조하거나 확인해야 할 때 사용	대규모 데이터 처리나 최종 출력이 필요한 경우 사용

 

결론

• 리스트 사용 방식은 디버깅이나 중간 결과를 확인해야 할 때 유용합니다.
• StringBuilder 사용 방식은 성능과 메모리 효율성을 우선시할 때 적합합니다.

 

---

문제: https://www.acmicpc.net/problem/7568