[BOJ/Swift] 좌표 압축 18870

Baekjoon Online Judge

단계별로 풀어보기 / 정렬 / 좌표 압축 18870

문제에 모든 정보 및 저작권 https://www.acmicpc.net/

---

Todo:

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

Constraints:

입력 제약:
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력 제약:
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한:

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

Input-Output

(출처 : https://www.acmicpc.net/problem/18870)

Solution.swift

let caseCount = Int(readLine()!)!
let inputs = readLine()!.split(separator: " ").map{ Int(String($0))! }
let sorted = Set(inputs).sorted(by: <)

// 답 1
var result = [Int:Int]()
(0..<sorted.count).forEach{ result.updateValue($0, forKey: sorted[$0]) }
print(inputs.map{ String(result[$0]!) }.joined(separator: " "))

// 답 2
let result = Dictionary(uniqueKeysWithValues: zip(sorted, (0..<sorted.count)))
print(inputs.map({ String(result[$0]!) }).joined(separator: " "))

github Code Repository

How I tried this:

문제를 이해하는게 가장 힘들었다.
무슨 원리로 압축을 한다는 건지.. 다른 문제풀이를 슬쩍 당연히
양심적으로 문제를 이해하는 목적으로만 보았다.

결론은 좌표압축 이라는 알고리즘이 존재했다.
존재의 이유는 모든 좌표를 다 가지고 있으면 범위가 커지기 때문에
중복되는 값을 줄이고 정렬해서 좌표 테이블을 가지고
테이블의 인덱스를 좌표대신 가지고 있다가 제공해주는 형태로 볼 수 있다.

처음 구현해 본 코드는 시간초과가 나왔다.

let result = inputs.map{ original -> String in
    let index = sorted.firstIndex(of: original)!
    return String(index)
}
print(result.joined(separator: " "))

생각해보니 firstIndex(of:)
중복처리를 Set() 변환으로 하고 오름차순 정리가 된 배열이여서
오류 없을거란 생각만 하고 썻는데 매번 탐색을 한다고 봐야될 것 같다..

그런점에서 생각을 바꿔서 딕셔너리로 값을 연결시켜서 위 정답중

첫번째 방법으로
처음 입력된 좌표들 중복 제거하고 오름차순 정렬
입력된 좌표를 한번 순회하며 각 좌표 대신 인덱싱(딕셔너리)
총 두번에 순회
-> 시간초과

두번째 방법으로
처음 입력된 좌표들 중복 제거하고 오름차순 정렬
입력된 좌표를 한번 순회하며 각 좌표 대신 인덱싱(딕셔너리) (초기화)
-> 시간초과

오잉?

일단 swift로 푼 다른분과 크게 다른 점은 없었고
다른 언어에서는 이진 탐색을 이용해서 탐색 속도를 줄이는 형태로 구현하고 있었다..

어떻게 더 좋은 방법을 생각해낼까 고민하다 밑져야 본전으로
String의 각 Charactor 순회하는 동작에서 Int() -> Int(String())
가 생각나서 해봤는데 왠걸 .... 맞았다..
위 두 코드 모두 맞길래 신나서 처음 실패한 것도 넣어봤는데
처음 실패는 실패가 맞다.. ㅎ 그냥 내가 잘못 푼..

What I got is:

문자열 각 값들 .map 할때 조심할 것..

I have to study:

• Int(String()) 왜 더 빠른가?

문제에 관한 모든 저작권 : https://www.acmicpc.net/