문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

접근 방식

이 문제는 “완주하지 못한 1명을 찾는 것”이 핵심이며, 동명이인이 존재할 수 있으므로 단순한 차집합으로는 해결되지 않습니다. 처음에는 반복문으로 이름을 삭제하는 방식으로 풀었지만 성능에서 실패했습니다. 그 다음 해시맵 카운트 방식으로 해결했고, 이후 Kotlin 제공 함수와 다른 접근을 확인해보기 위해 그룹핑/정렬 방식도 추가로 시도했습니다.

실패한 시도: 반복문으로 삭제

                        kotlin
                    
1
2
3
4
5
6
if (participant.size == 1) return participant[0]

val arr = participant.toMutableList()
completion.forEach { arr.remove(it) }

return arr[0]

리스트에서 매번 삭제하므로 최악의 경우 O(n^2)로 커져 효율성 테스트에서 통과하지 못했습니다.

2) 해시맵 카운트 (증가/감소)

반복문 삭제 방식이 실패한 뒤, 본질이 빈도수 비교라는 점을 보고 이 방식으로 해결했습니다.

                        kotlin
                    
1
2
3
4
5
6
7
8
9
10
val countName = HashMap<String, Int>()
for (p in participant) {
    countName[p] = countName.getOrDefault(p, 0) + 1
}

for (c in completion) {
    countName[c] = countName[c]!! - 1
}

return countName.entries.first { it.value > 0 }.key

참가자를 +1, 완주자를 -1로 누적하고 값이 1 이상 남아 있는 키가 정답입니다. 코드도 단순하고, 평균 시간복잡도가 O(n)입니다.

1) 그룹핑 + 비교 (groupingBy / eachCount)

해시맵 방식으로 해결한 뒤, Kotlin에서 제공하는 컬렉션 함수를 더 사용해보고 싶어서 추가로 시도했습니다.

                        kotlin
                    
1
2
3
4
5
6
7
8
9
val countName = participant.groupingBy { it }.eachCount().toMutableMap()
val completionName = completion.groupingBy { it }.eachCount()

val result = countName.keys.minus(completionName.keys)
return result.firstOrNull() ?: run {
    val filtered = countName.filter { (_, v) -> v > 1 }
    val diffKey = filtered.entries.firstOrNull { (k, v) -> v != (completionName[k] ?: 0) }?.key
    diffKey ?: ""
}

참가자/완주자를 각각 이름별 카운트로 만든 뒤 비교합니다. Kotlin 컬렉션 함수로 표현이 간결하지만, 같은 이름이 있을 경우 키 차이가 없기 때문에 값 비교를 위한 분기가 생겨 로직이 길어집니다.

3) 정렬 후 위치 비교

맵을 쓰지 않는 다른 방법이 있을까 생각하다가 정렬 비교 방식도 시도했습니다.

                        kotlin
                    
1
2
3
4
5
6
7
val p = participant.sorted()
val c = completion.sorted()

for (i in c.indices) {
    if (p[i] != c[i]) return p[i]
}
return p.last()

두 배열을 정렬한 뒤 같은 인덱스로 비교합니다. 불일치 지점이 정답이고, 끝까지 같으면 마지막 참가자가 정답입니다. 구현이 쉽지만 정렬 때문에 O(n log n)입니다.

시간 복잡도

그룹핑/카운트 비교: 평균 O(n)
해시맵 카운트: 평균 O(n)
정렬 비교: O(n log n)

회고

반복문으로 삭제하는 방식은 직관적이지만, 입력이 커지면 성능에서 통과하지 못했다.
배열 순서는 중요하지 않다는 점을 보고 해시맵 카운팅으로 방향을 잡았다.
동명이인 처리 때문에 “빈도수 비교”가 본질이라는 것을 명확히 알게 됐다.

결론

성능과 단순함을 함께 고려하면 해시맵 카운트 방식이 가장 균형 잡힌 해법이다.
구현 속도가 중요하거나 입력이 크지 않다면 정렬 방식이 상대적으로 직관적이기 때문에 실전에서 쓸 만하다.