18870번: 좌표 압축 [JAVA]

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

18870번: 좌표 압축

접근방식

1) [시간초과] Set에 중복없이 저장하고, List로 만들어서 정렬. 그리고 indexOf()로 인덱스 번호 가져오면 됨 

→ 맨 밑 쪽 indexOf()의 시간복잡도가 O(n)이기 때문에  for문에서의 시간복잡도가 O(n^2)로 시간초과 뜬다.

package codingTestStudy.week1;

import java.util.*;
public class B_18870 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        int N = sc.nextInt();

        for (int i = 0; i < N; i++) {
            int n = sc.nextInt();
            list.add(n);
            set.add(n);
        }

        List<Integer> listXY = new ArrayList<>(set);
        Collections.sort(listXY);

        for (int i : list)
            System.out.print(listXY.indexOf(i) + " ");
        //--indexOf()의 시간복잡도는 O(n)
        //  for문에서 O(n^2)라 시간초과 뜸
    }
}

 

2) [시간초과] HashMap에 key값 저장하고 keySet() 정렬해서 HashMap에 idx 넣어줌. 그리고 인덱스 번호 가져옴

→ 왜인지 아직 모르겠음 ㅠ.ㅠ....

package codingTestStudy.week1;

import java.util.*;
public class B_18870 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        List<Integer> listXY;
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            int n = sc.nextInt();
            list.add(n);
            map.put(n, -1);
        }

        listXY = new ArrayList<>(map.keySet());
        Collections.sort(listXY);
        for (int i = 0; i < listXY.size(); i++)
            map.put(listXY.get(i), i);

        for (int i : list)
            System.out.print(map.get(i) + " ");
    }
}

 

3) [통과]  HashMap 사용해서 key로 value 가져와서 출력하고 싶었다.

1. set에 넣어서 중복제거 & 후에 출력하려면 원본배열 필요하므로 원본배열도 저장

2. 리스트에 저장해서 정렬

3. HashMap에 <숫자, 순서>로 key, value값 넣음

4. 원본배열 값을 key로 사용하며 map에 저장된 value 출력

import java.io.*;
import java.util.*;
public class B_19970 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] coords = new int[N];
        Set<Integer> set = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            coords[i] = Integer.parseInt(st.nextToken());
            set.add(coords[i]);
        }

        // 정렬
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);

        // HashMap에 <숫자, 순서>로 key, value 값 넣는다.
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < list.size(); i++) {
            map.put(list.get(i), i);
        }

        // coords 배열값을 key로 사용하여 map에 저장된 값 출력
        StringBuilder sb = new StringBuilder();
        for (int i : coords)
            sb.append(map.get(i)).append(' ');
        System.out.println(sb);
    }
}