[JAVA] 좌표 압축 (백준 18870번)

 

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

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

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

 

=> 무슨 소리지...???

 

요약 

수직선 위에 N개의 좌표의 => 각 번호가 몇 번째로 큰 숫자인지 출력 (압축)

EX) 1 2 1 5 3 (총 5개 좌표) => 압축 0 1 0 3 2  => 1이 0 번째로 큰 수 , 2는 1번째로 큰 수 ... 

 

 

1. 시간초과 접근 방법)

1. N개의  좌표 list => tmp에 담아서 복사 

2. 복사한 tmp 중복제거, 좌표 정렬

3. Ex) list = Arrays.asList(1,2,1,5,3)  , tmp = Arrays.asList(1,2,3,5)

4. tmp의 value를 돌면서 => list.IndexOf(tmp의value) => 0 1 0 3 2  

 

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
  

        List<Integer> list = new ArrayList<>();
        for(int i=0; i<N; i++){
            list.add(Integer.parseInt(st.nextToken()));
        }

        List<Integer> tmp = new ArrayList<>(new HashSet<>(list)); // 중복제거
        Collections.sort(tmp); // 정렬
        
        for(int i=0; i<N; i++){
            int value = list.get(i);
            int index = tmp.indexOf(value);
            
            System.out.print(index + " ");
        }
    }
}

 

틀린이유 => indexOf(value)를 N번 반복하면 **O(N²)**의 시간 복잡도, 출력을 반복하는게 문제

 

 

 

2. 정답) 

수정한 부분

1. indexOf 대신 HashMap을 활용 => HashMap에 key, value로 (값, 몇 번째로 큰지)  저장

2. 출력 => StringBuilder 활용

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
  
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<N; i++){
            list.add(Integer.parseInt(st.nextToken()));
        }

        List<Integer> tmp = new ArrayList<>(new HashSet<>(list)); //중복제거
        Collections.sort(tmp); // 정렬

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < tmp.size(); i++) {
            map.put(tmp.get(i), i); // 값 → 압축된 좌표
        }
  
        StringBuilder sb = new StringBuilder();
        for (int value : list) {
            sb.append(map.get(value)).append(" ");
        }
        System.out.println(sb);
    }
}