오늘의 문제: 29723
N개의 과목 중 M개의 과목만 시험을 보는데, 그중 K개의 과목이 공개되었을 때, 최소 점수와 최대 점수를 구하는 문제이다.
🤔 문제 분석 및 초기 접근
문제의 요구사항을 분석해보면:
1. 내가 받은 N개 과목과 그 점수들이 주어짐
2. 시험에 나오는 M개 과목 중 K개 과목은 공개되어 무조건 포함됨
3. 비공개 과목들(M-K개)은 나머지 과목 중에서 선택됨
4. 최솟값과 최댓값을 구해야 함
딕셔너리를 이용해 과목별 점수를 관리하고, 정렬을 통해 최소/최대 점수를 계산하는 방식으로, 접근했다.
var hint = readLine()!.split(separator: " ").compactMap { Int($0) }
let publicSubjectCount = hint.removeLast()
let testCount = hint.removeLast()
let mySubjectCount = hint.removeLast()
var myRecord = [String: Int]()
for _ in 0..<mySubjectCount {
let record = readLine()!.split(separator: " ").map { String($0) }
myRecord[record.first!, default: 0] += Int(record.last!)!
}
var result = Int()
for _ in 0..<publicSubjectCount {
let subject = readLine()!
result += myRecord[subject]!
myRecord.removeValue(forKey: subject)
}💡 핵심 아이디어 및 구현
핵심 아이디어는 다음과 같다:
1. 공개된 과목들의 점수는 확정적으로 더하고
2. 남은 과목들을 점수 기준으로 정렬한 후
3. 최소값을 위해서는 가장 낮은 점수들을, 최대값을 위해서는 가장 높은 점수들을 선택
let repeatCount = testCount - publicSubjectCount
var sortedMinRecord = myRecord.sorted(by: { $0.value < $1.value })
var sortedMaxRecord = myRecord.sorted(by: { $0.value > $1.value })
var minResult = result
var maxResult = result
for _ in 0..<repeatCount {
guard !sortedMinRecord.isEmpty else { break }
minResult += sortedMinRecord.first!.value
sortedMinRecord.removeFirst()
}
for _ in 0..<repeatCount {
guard !sortedMaxRecord.isEmpty else { break }
maxResult += sortedMaxRecord.first!.value
sortedMaxRecord.removeFirst()
}
print("\(minResult) \(maxResult)")🔄 코드 최적화 및 개선
AI에게 더 효율적인 코드가 있는지 물어보았고, 다음과 같은 개선 사항을 제안 받았다:
// 최소값과 최대값 계산 최적화
let sortedValues = myRecord.values.sorted()
let repeatCount = min(testCount - publicSubjectCount, sortedValues.count)
var minResult = result
var maxResult = result
// 최소값: 작은 값부터 더함
for i in 0..<repeatCount {
minResult += sortedValues[i]
}
// 최대값: 큰 값부터 더함
for i in 0..<repeatCount {
maxResult += sortedValues[sortedValues.count - 1 - i]
}이 방식의 장점:
1. 딕셔너리에서 값만 추출해 정렬하므로 메모리 사용량 감소
2. 두 개의 정렬된 배열을 만들지 않고 하나만 사용
3. removeFirst()를 호출하지 않아 배열 복사 비용 절감
4. 인덱스 범위 체크를 min 함수로 간결하게 처리
하지만 결국 시간 복잡도는 O(n log n)으로 동일하며, 공간 복잡도만 약간 개선되는 정도이다.
🧮 왜 O(n log n)이지? 정렬 알고리즘과 시간 복잡도
알고리즘 문제를 풀다 보면 '시간 복잡도'라는 말을 자주 듣게 된다. 이 문제의 핵심 연산인 정렬은 왜 O(n log n)의 시간 복잡도를 가질까?
- 빅오 표기법 (Big O Notation): 알고리즘의 성능을 나타내는 방법이다. 입력 데이터의 크기(n)가 증가할 때 실행 시간(또는 사용 공간)이 얼마나 늘어나는지를 표현한다.
- O(n log n)의 의미: 데이터가 n개일 때, 대략 n log(n) 번의 연산이 필요하다는 뜻이다. 예를 들어 데이터가 1,000개면 약 1,000 log₂(1000) ≈ 10,000번의 연산이 필요하다.
- 정렬의 한계: 비교를 통해 순서를 결정하는 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)은 이론적으로 O(n log n)보다 빠를 수 없다. n개의 항목을 정렬하는 데 필요한 최소 비교 횟수가 약 n log n번이기 때문이다.
- Swift의
sorted(): Swift의sorted()메서드는 내부적으로 효율적인 알고리즘을 사용해 평균적으로 O(n log n) 성능을 보장한다.
따라서 이 문제에서 myRecord.values.sorted() 부분이 전체 실행 시간을 좌우하며, 이 때문에 전체 시간 복잡도는 O(n log n)이 된다. 입력 크기가 커질수록 O(n²) 같은 비효율적인 알고리즘과의 성능 차이는 매우 커진다.
✅ 결과 및 회고
처음에는 최소값과 최대값을 계산하는 부분에서 실수했다. 특히 guard 구문에서 잘못된 변수를 검사하고 있었고, 이로 인해 제대로 동작하지 않았다.
// 잘못된 코드
for _ in 0..<repeatCount {
guard !sortedMinRecord.isEmpty else { break }
minResult += sortedMaxRecord.popLast()!.value // sortedMaxRecord를 사용해 버림
}실수를 발견하고 수정한 후, 플레이그라운드에서 테스트해보니 정상적으로 동작함을 확인했다. 문제 해결의 핵심은 정확한 변수 사용과 배열 처리였다.
✨ 오늘 배운 점 정리
- 딕셔너리와 정렬을 활용한 문제 해결 방법
- 배열에서 요소를 제거하는 방법 (
removeFirst()vs 인덱스 접근) guard구문을 사용한 안전한 배열 접근- 코드 리뷰와 테스트의 중요성
- 메모리 효율성을 고려한 자료구조 선택
- 시간 복잡도 O(n log n)의 의미와 정렬 알고리즘의 효율성 이해
