99클럽 코테 스터디 22일차 TIL - Java 백준 18870 좌표 압축

🌟 Today's Focus

BOJ 18870 좌표 압축

• 핵심 개념: 정렬, 중복 제거, 값-인덱스 매핑
• 자료구조: ArrayList/TreeSet, HashMap
• 알고리즘: 정렬

---

 

📝 Today I Learned

오랜만에 코테 푸는데 정렬이라고 좀 만만하게 봤다가 큰코 다침.

문제 분석 ( 재정의 )

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

 

"Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다."라는 문장의 의미를 처음에 이해 못했다;;
막상 까고 보니 "각 숫자보다 작은 서로 다른 숫자들의 개수를 세는 것"이더라...... 외국어 해석하는 줄 알았음.

아무튼 N개의 수를 공백으로 구분해서 던져주면, 그걸 '좌표 압축'해서 뱉어내야 된다는 건데.
처음에 도무지 이 규칙이 눈에 보이지가 않아서 정렬 힌트로 겨우 알아냈음.
좌표 압축이 결국 입력값으로 준 수들 간 크기 비교해서 그 수보다 작은 수가 이 배열 안에 있음 몇 개인지 뱉어내는 거였음.

앞서 해석한 외국어 "각 숫자보다 작은 서로 다른 숫자들의 개수를 세라"가 결국
=> 정렬해서 중복 제거하고 랭킹 매겨라 인 걸로 이해함.

문제 접근 & 풀이

그래서 처음엔

1. 원본 배열 저장하고 (나중에 또 써야 하니까 순서 유지하려고)
2. 중복 제거(어차피 압축결과는 같아서) & 정렬(순서 매겨야되니까)
3. 각 숫자의 압축값(순위) 매핑 -> 해시
4. 원본 순서대로 압축값을 해시에서 꺼내서 출력

방식으로 해봄.

틀림

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); 
        int[] original = new int[N]; 
        StringTokenizer st = new StringTokenizer(br.readLine()); 

        // original input[] 
        for(int i = 0; i < N; i++) {
            original[i] = Integer.parseInt(st.nextToken()); 
        }

        // remove dupl -> HashSet
        HashSet<Integer> set = new HashSet<>(); 
        for (int num: original) {
            set.add(num); 
        }

        Integer[] sorted = set.toArray(new Integer[0]); 
        Arrays.sort(sorted); 

        HashMap<Integer, Integer> rankMap = new HashMap<>();
        for (int i = 0; i < sorted.length; i++);

        StringBuilder sb = new StringBuilder(); 
        for (int num : original) {
            sb.append(rankMap.get(num)).append(" "); 
        }

        System.out.println(sb); 
        br.close(); 
    }
}

 

아는 자료구조 총동원해서 별짓 다함. 결과는 '틀렸습니다' ^___^

 

HashSet 버림 - 불필요한 자료구조 변환으로 인한 오버헤드

 

그래도 배열은 포기 못하고 대신 ArrayList + 정렬 방식으로 하니까 성공(1704ms)함.

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

        int N = Integer.parseInt(br.readLine());
        int[] original = new int[N]; 

        StringTokenizer st = new StringTokenizer(br.readLine()); 
        for (int i = 0; i < N; i++) {
            original[i] = Integer.parseInt(st.nextToken()); 
        }

        ArrayList<Integer> sorted = new ArrayList<>(); 
        for (int num : original) {
            sorted.add(num); 
        }
        Collections.sort(sorted); 

        HashMap<Integer, Integer> rankMap = new HashMap<>(); 
        int rank = 0; 
        for (int i = 0; i < sorted.size(); i++) {
            if(!rankMap.containsKey(sorted.get(i))) {
                rankMap.put(sorted.get(i), rank++);
            }
        }

        StringBuilder sb = new StringBuilder(); 
        for (int num : original) {
            sb.append(rankMap.get(num)).append(" "); 
        }
        System.out.println(sb); 
        br.close(); 
    }
}

아니 근데 어찌어찌 다 풀고 나니까 TreeSet이 정렬도 자동이고 중복도 제거해준다네
쓰면 코드 가독성 확 올라갈 거 같았음.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

        int N = Integer.parseInt(br.readLine()); 
        int[] original = new int[N]; 

        StringTokenizer st = new StringTokenizer(br.readLine()); 
        for(int i = 0; i < N; i++) {
            original[i] = Integer.parseInt(st.nextToken()); 
        }

        TreeSet<Integer> treeSet = new TreeSet<>(); 
        for (int num: original) {
            treeSet.add(num); 
        }

        HashMap<Integer, Integer> rankMap = new HashMap<>(); 
        int rank = 0; 
        for (int num: treeSet) {
            rankMap.put(num, rank++); 
        }

        StringBuilder sb = new StringBuilder(); 
        for (int num : original) {
            sb.append(rankMap.get(num)).append(" "); 
        }

        System.out.println(sb); 
        br.close(); 
    }
}

1764ms로 통과함. 근데 왜 시간 차이가 나는지 궁금했음.
같은 시간복잡도(O(N log N))던데.
알아보니 TreeSet은 매 삽입마다 트리 재구성이 필요하다고.
ArrayList는 한 번의 정렬로 캐시 효율성이 높다고 함.

 

💭 Reflection

TreeSet<Integer> treeSet = new TreeSet<>();
for(int num : original) {
    treeSet.add(num);
}

HashMap<Integer, Integer> rankMap = new HashMap<>();
int rank = 0;
for(int num : treeSet) {
    rankMap.put(num, rank++);
}

1. 문제가 이해되지 않을 때는 구체적인 예제로 차근차근 접근하면 된다. 요즘엔 종이에 냅다 그리거나 쓰면서 하는데 도움이 된다. 처음엔 어려워 보였던 문제 설명도 예제를 통해 이해하니 명확해졌다.
2. 같은 시간복잡도(O(N log N))를 가진 알고리즘이라도 실제 수행시간은 다를 수 있다. ArrayList는 한 번에 정렬하는 반면, TreeSet은 매 삽입마다 정렬을 유지해야 해서 조금 더 느렸다.
3. 가끔은 코드 한 줄을 줄이는 것보다 의도를 명확히 하는 게 더 중요할 수 있다. TreeSet 버전이 비록 조금 더 느리지만, 코드의 의도가 가장 잘 드러나서 유지보수하기 좋다.

다음에는 이런 자료구조들의 내부 구현을 좀 더 자세히 공부해봐야겠다. 특히 TreeSet이 사용하는 레드-블랙 트리가 어떻게 구현되어있는지 궁금해졌다.