[BOJ/백준] Swift - 좌표 압축(18870)

 

 

나는 왜 좌표가 무서운가,,

오랜시절부터 축적 되어온 수포자의 본능인가

 

 

 

 

좌표 압축(18870)

문제 링크 : 

https://www.acmicpc.net/problem/18870

만약 정확한 값이 필요 없고 값의 대소 관계만 필요하다면, 모든 수를 0 이상 N 미만의 수로 바꿀 수 있습니다.

 

 

 

 

let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
var dict = [Int : Int]()
var move = 0

for i in arr.sorted() {
    if dict[i] == nil {
        dict[i] = move
        move += 1
    }
}

print("\(arr.map{ String(dict[$0]!) }.joined(separator: " "))")

 

 

근데 실제로 너무(?) 그냥 문제부터 이해가 안된..

왜 딕셔너리로 풀어야하고?

뭔 압축값?

좌표 압축이라는 게 있는 개념인건가..싶어 찾아봤다.

 

 

 

좌표 압축이란?

좌표 압축은 주어진 데이터를 정렬한 후, 각 원소에 대해 그 값보다 작은 값의 개수를 기반으로 새로운 값을 할당하는 과정입니다. 이렇게 하면 원래의 값들보다 작고 연속적인 숫자들로 변환되므로, 메모리나 계산 효율성이 향상될 수 있습니다.

좌표 압축은 큰 값 범위의 좌표나 데이터를 작은 범위로 변환하여 효율적으로 처리하는 방법입니다. 주로 정렬 후 인덱스를 기준으로 변환되며, 메모리와 시간 성능을 개선하는 데 사용됩니다.

 

 

 

원래 있는 개념이구나..

 

 

좌표압축 예시

주어진 좌표들이 5, 100, 3, 10이라고 할 때, 좌표 압축을 적용하면 아래와 같다

1. 주어진 좌표들을 정렬하면 [3, 5, 10, 100]이 됩니다.
2. 각 좌표에 대해 그보다 작은 값들의 개수를 구합니다:
   • 3보다 작은 값은 없으므로 3 -> 0
   • 5보다 작은 값은 3 하나, 따라서 5 -> 1
   • 10보다 작은 값은 3, 5 두 개, 따라서 10 -> 2
   • 100보다 작은 값은 3, 5, 10 세 개, 따라서 100 -> 3
3. 따라서 좌표 압축 후의 값은 [0, 1, 2, 3]입니다.

 

사용이유 

1. 메모리 절약: 값이 크거나 범위가 넓을 때, 원래의 값들을 연속적인 작은 범위로 바꿔서 더 효율적으로 메모리를 사용할 수 있습니다.
2. 속도 향상: 큰 숫자를 처리할 때 계산이 느려질 수 있는데, 작은 범위로 압축된 값들을 처리하면 성능을 개선할 수 있습니다.
3. 정렬 최적화: 데이터를 정렬할 때 값의 범위가 작아지므로 정렬의 성능이 향상될 수 있습니다.

 

 

 

결국 구글링하면 딕셔너리로 많이 풀고 위에있는 풀이가 대부분의 풀이였다.

분석해보면,

 

각 좌표를 0부터 시작하는 인덱스로 압축하는 과정입니다.

각 좌표는 압축된 순서대로 중복을 제거하고,

해당 좌표가 정렬된 순서를 반영한 값으로 바뀝니다.

 

for 문은 

정렬된 좌표에 대해 딕셔너리 매핑하는 과정.

 

 

• dict[i] == nil: 해당 좌표가 딕셔너리에 아직 없다면 (즉, 첫 번째로 등장한 경우) 인덱스를 move로 설정합니다.
• dict[i] = move: 좌표 i의 압축된 인덱스를 move로 설정합니다.
• move += 1: 인덱스를 하나 증가시킵니다. 이때, 각 좌표는 중복을 제거하고 정렬된 순서대로 인덱스가 부여됩니다.

 

 

좌표 압축?.. 너 뭔데.. 외계어 같냐고..

개념공부부터? ..

 

 

 

도저히 위에 챗지피티 말이 이해가 안돼서 

다시 세밀하게 물어봤다.

이거 보니까 이해 좀됨 ;;;

 

좌표로 표현하는 값이 큰수면 어쨌든 불편하고 곤란하니까

압축을 하는 것.

순서는 이렇게 진행됨.

 

정렬  → 중복제거 → 인덱스매핑(이거 때문에 dic사용) → 원본배열의 값을 인덱스로 대체.

시간복잡도는 O(nlogn)

 

좌표 압축의 원리

좌표 압축은 말 그대로 좌표의 값을 축소하여 작은 값으로 변환하는 기법입니다. 이 기법은 값의 순서만 보존하고 값 자체는 변환합니다. 이렇게 함으로써, 원래의 값에 비해 메모리를 적게 사용하거나, 효율적인 계산을 할 수 있습니다.

예를 들어, 좌표 값이 1, 100, 1000이라면, 1000과 같은 큰 수를 처리할 때 어려움이 있을 수 있습니다. 그러나 이들 값의 상대적인 순서만 알면 되기 때문에, 이를 0, 1, 2와 같은 작은 숫자로 압축할 수 있습니다.

좌표 압축을 사용하는 상황

좌표 압축은 수의 범위가 너무 클 때, 즉 숫자들이 매우 크거나 많은 범위를 가질 때 효과적입니다. 예를 들어:

• 범위가 매우 큰 숫자들을 다룰 때:
  • 좌표 값이 수십억에 달할 때, 이 숫자들을 메모리에 모두 담는 것은 비효율적일 수 있습니다. 그럴 때 좌표 압축을 사용하여 작은 범위의 값들로 변환할 수 있습니다.
• 중복되는 값이 많을 때:
  • 예를 들어, 좌표 값이 1부터 100까지 반복해서 나오는 경우, 중복된 값들을 압축하여 작은 인덱스를 부여할 수 있습니다.

좌표 압축의 과정

좌표 압축의 기본 원리는 간단합니다:

1. 주어진 값들을 정렬합니다.
2. 정렬된 값에 인덱스를 매핑합니다.
3. 원본 값들은 정렬된 인덱스로 변환됩니다.

예시로 좌표 압축 진행

입력: 좌표가 [10, 30, 20, 20, 10]이라고 할 때:

1. 정렬:

주어진 좌표를 오름차순으로 정렬합니다.

[10, 20, 20, 30, 10]

정렬 후:

[10, 10, 20, 20, 30]

2. 중복 제거:

중복되는 값들은 한 번만 나타내면 되므로, 정렬된 배열에서 중복을 제거합니다.

[10, 20, 30]

3. 인덱스 매핑:

이제 정렬된 값들에 인덱스를 매핑합니다. 좌표 압축에서는 인덱스를 부여합니다.

10 → 0

20 → 1

30 → 2

4. 원본 배열의 값을 압축된 인덱스로 변경:

마지막으로 원래의 좌표들을 인덱스 값으로 변환합니다.

[10, 30, 20, 20, 10] → [0, 2, 1, 1, 0]

결과:

0 2 1 1 0

이제 원래의 값들을 0, 1, 2라는 작은 숫자로 압축한 상태가 됩니다.

좌표 압축의 활용 예시

좌표 압축을 사용하면 더 작은 범위의 값으로 효율적인 메모리 사용이 가능해집니다. 예를 들어, 수학적인 계산이나 그래픽 처리 등에서 특정 좌표 값들을 다룰 때 유용합니다.

요약:

• 좌표 압축은 주어진 값들을 정렬하고 인덱스를 부여하여, 값의 순서만 유지하고 값 자체는 압축하는 기법입니다.
• 값의 범위가 크거나 중복이 많은 데이터에서 효율적으로 메모리를 사용하고, 계산을 간단하게 할 수 있습니다.
• 중복 값은 제거하고, 각 값의 상대적인 순서에 맞춰 새로운 인덱스를 할당하여 데이터를 압축합니다.