[BaekJoon] 18870번 좌표 압축 문제 풀이 (Success)

18870번: 좌표 압축

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
public class Main {
 
    static List<Long> list2;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N = Integer.parseInt(br.readLine());
 
        Set<Long> set = new TreeSet<>();
 
        List<Long> list = new ArrayList<>();
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < N; i++) {
            long num = Long.parseLong(st.nextToken());
            set.add(num);
            list.add(num);
        }
 
        list2 = new ArrayList<>();
 
        for (Long l : set) {
            list2.add(l);
        }
 
        StringBuffer sb = new StringBuffer();
 
        for (int i = 0; i < N; i++) {
            sb.append(list2.indexOf(list.get(i)) + " ");
        }
 
        bw.write(sb + "");
 
        bw.flush();
        bw.close();
    }
 
}
 

🤔 해설

1. Set<Long> set = new TreeSet<>();

    - TreeSet 이진검색트리* 방법으로 오름차순정렬

 

* 이진검색트리

    - 각 노드가 왼쪽 서브 트리의 모든 값보다 크고 오른쪽 서브 트리의 모든 값보다 작음

    - 평균적으로 O(log n)의 시간 복잡도

 

2. List<Long> list = new ArrayList<>();

    - 입력 순서대로 list에 저장

    ▶ 입력 순서대로 출력하기 위해 list2에서 인덱스 값 출력용으로 활용

 

3. list2 = new ArrayList<>();

    - static으로 선언했으나, 당시 메서드를 따로 만들어서 작업하려고 했던 부분으로 instance로 생성해도 됨

    - 정렬된 set값을 list2에 저장

    ▶ Treeset은 index를 통해 접근할 수 없어, 인덱스를 통해 접근하는 list 생성

 

4. list2.indexOf(list.get(i)) + " ")

    - set값이 저장된 list2는 오름차순 정렬되어있으므로, 입력 순서가 저장된 list 값을 대입해 list2의 index 값을 출력

 

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        int[] origin = new int[N];
        int[] sorted = new int[N];
 
        Map<Integer, Integer> map = new HashMap<>();
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        for (int i = 0; i < N; i++) {
            int element = Integer.parseInt(st.nextToken());
            sorted[i] = element;
            origin[i] = element;
        }
 
        Arrays.sort(sorted);
 
        int rank = 0;
        for (int v : sorted) {
            if (!map.containsKey(v)) {
                map.put(v, rank);
                rank++;
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int key : origin) {
            int ranking = map.get(key);
            sb.append(ranking).append(" ");
        }
        
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 

1. int[] origin = new int[N];

    - 입력 순서가 저장된 int[]

 

2. int[] sorted = new int[N];

    - origin 배열을 정렬한 sorted[]

 

3. if (!map.containsKey(v)) {...}

    - 오름차순 정렬된 sort값을 0, 1, 2로 변환

    - !map.containsKey(v)

        - 같은 값일 경우, 순위가 동일해야하므로 기존에 key값이 없을 경우만 map에 저장

        - 같은 값을 가진 숫자가 2개 이상이더라도, 다음 값은 rank+1만큼만 증가

 

4. for (int key : origin) {...}

    - 기존 입력값의 순위(rank) 값 출력

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        int[] origin = new int[N];
 
        Map<Integer, Integer> map = new TreeMap<>();
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        for (int i = 0; i < N; i++) {
            int element = Integer.parseInt(st.nextToken());
            origin[i] = element;
            map.put(element, 0);
        }
 
        int ranking = 0;
        for (int key : map.keySet()) {
            map.replace(key, ranking);
            ranking++;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int key : origin) {
            sb.append(map.get(key)).append(" ");
        }
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 

1. Map<Integer, Integer> map = new TreeMap<>();

    - Map: 중복값 제거

    - TreeMap: 오름차순 정렬

 

2. for (int key : map.keySet()) {...}

    - key값의 value를 ranking 값으로 변환

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

[백준] 18870번 : 좌표 압축 - JAVA [자바]