백준 20551번 문제 풀이

💡 최적화 전략

 

1. 정렬
   • arr.sort() → O(N \log N)
2. 값 → 첫 등장 인덱스 매핑
   • Dictionary<Int, Int>에 최초 등장 인덱스만 저장 → O(N)
3. 질의 처리
   • print(indexMap[query] ?? -1) → 평균 O(1)

전체 시간 복잡도:

O(N\log N) + O(N) + O(M) = O(N\log N + M)

// 1) 첫 번째 줄 입력 및 파싱
let firstLine = readLine()!
let parts = firstLine.split(separator: " ").map { Int($0)! }
let n = parts[0], m = parts[1]

// 2) 배열 입력 및 정렬
var arr = [Int]()
arr.reserveCapacity(n)
for _ in 0..<n {
    arr.append(Int(readLine()!)!)
}
arr.sort()

// 3) 값 → 첫 등장 인덱스 매핑
var indexMap = [Int: Int]()
for (i, value) in arr.enumerated() {
    if indexMap[value] == nil {
        indexMap[value] = i
    }
}

// 4) 질의 처리
for _ in 0..<m {
    let query = Int(readLine()!)!
    print(indexMap[query] ?? -1)
}

📚 키워드 정의

 

• Dictionary: 해시 테이블 기반 컬렉션. 키를 통해 값을 평균 O(1)에 읽고 쓸 수 있음.
• reserveCapacity(_:): 배열의 예상 크기를 미리 할당해, 추가 시 메모리 재할당을 줄여 성능을 개선.
• sort(): Swift 표준 라이브러리의 병합/힙 기반 최적화 정렬 알고리즘 사용.