[Swift] 백준 10816번 숫자카드 2

문제 출처: 백준 10816번 숫자카드 2

문제

---

풀이

---

처음에 Binary Search를 이용해서 풀려고 몇 번 시도해 봤는데요.
문제의 범위도 넓고 제한 시간이 1초라서 자꾸 시간 초과가 나더라구요… (정렬 때문인가…?)
그래서 저는 계수 정렬, 딕셔너리를 이용해 2가지 방법으로 풀어봤습니다.

계수 정렬 풀이

let n = readLine()!
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = readLine()!
let arr2 = readLine()!.split(separator: " ").map { Int(String($0))! }

/// 배열의 길이는 숫자의 범위(-10000000 ~ 10000000)만큼
var counting = Array(repeating: 0, count: 20000001)
var result = ""

// 처음 입력받은 배열을 순회
for i in arr {
  // i == 1일 경우 index = 10000001
  // i == 0일 경우 index = 10000000
  // i == -1일 경우 index = 9999999
  if i > 0 {
    counting[i + 10000000] += 1
  } else {
    counting[10000000 + i] += 1
  }
}

// 
for i in arr2 {
  if i > 0 {
    result += "\(counting[i + 10000000]) "
  } else {
    result += "\(counting[10000000 + i]) "
  }
}

// 결과 출력
print(result)

1. 문제에 주어지는 입력값들을 입력받습니다.
2. 첫 번째 배열을 순회하면서 조건에 맞게 counting 배열의 요소를 증가시킵니다.
3. 두 번째 배열을 순회하면서 조건에 맞게 counting 배열의 값을 result에 더합니다.

이렇게 풀 경우 메모리: 266640 KB, 시간: 768 ms 결과가 나오게 됩니다.

알고리즘 문제 특성상 범위가 정해져 있기 때문에 계수 정렬을 이용해 풀어봤는데요.
시간초과는 나지 않았지만 역시 메모리 사용량이 많습니다.
그리고 n과 m을 사용하지 않고서 풀 수 있었습니다.

---

딕셔너리 이용 풀이

let n = readLine()!
var arr = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = readLine()!
let arr2 = readLine()!.split(separator: " ").map { Int(String($0))! }

var dict: [Int: Int] = [:]
var result = ""

for i in arr {
  if dict.keys.contains(i) {
    dict[i]! += 1
  } else {
    dict[i] = 1
  }
}

for i in arr2 {
  if dict.keys.contains(i), let count = dict[i] {
    result += "\(count) "
  } else {
    result += "0 "
  }
}

print(result)

1. 문제에 주어지는 입력값들을 입력받습니다.
2. 첫 번째 배열을 순회하면서 dict에 키가 있으면 값을 증가시키고 없으면 요소를 추가합니다.
3. 두 번째 배열을 순회하면서 dict에 키가 있으면 값을 result에 더해주고 없으면 0을 더해줍니다.

이렇게 풀 경우 메모리: 126908 KB, 시간: 684 ms 결과가 나오게 됩니다.

딕셔너리의 경우 [키: 값]으로 데이터를 찾기 때문에 정렬을 해주지 않아도 문제를 풀 수 있었습니다.
아 그리고 2가지 방법 모두 값을 문자열에 더해주는 방식이기 때문에 마지막 공백문자를 제거해야 하는 줄 알았는데 제거하지 않아도 정답처리 됬습니다.