[백준] no18870: 좌표압축

문제

주어진 숫자들에 대해 순차적으로 랭킹을 구한다

중복은 허용하지 않으며, 자기보자 작은 숫자의 개수를 파악하는 문제

 

문제 링크 : https://www.acmicpc.net/problem/18870

 

---

원리

1. BFS

2. 랭킹 시스템

 

---

풀이방법

숫자 저장 -> sort -> 비교하며 랭킹을 HashMap에 저장 -> 랭킹 대입

 

---

나의 코드

1. 단순반복 [로컬은 통과하지만, 당연히 시간초과]

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 T = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    Integer[] arr = new Integer[T];
    for(int i=0; i<T ; i++) arr[i] = Integer.parseInt(st.nextToken());

    for(int i=0; i<arr.length; i++) {
        Set<Integer> set = new HashSet<>();
        for(int j=0; j<arr.length; j++) {
            if(arr[i]>arr[j] && !set.contains(arr[j])) set.add(arr[j]);
        }
        bw.append(""+set.size()+" ");
    }
    bw.close();
}

 

2. 두 개의 ArrayList를 이용한 비교. 중복을 제외하고 정렬한 Index값은 곧 개수 [ 시간초과. 왜?? ]

* 참고로 stream을 사용할 때, 백준은 Java11이라 .toList()를 못찾는다.

   java.util.stream.Collectors를 import 해주고, collect(Collectors.toList())로 해줘야 한다.

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 T = Integer.parseInt(br.readLine());
    
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    List<Integer> baseList = new ArrayList<>();
    List<Integer> sideList = new ArrayList<>();
    for(int i=0; i<T ; i++) {
        Integer num = Integer.parseInt(st.nextToken());
        baseList.add(num);
        sideList.add(num);
    }

    List<Integer> sortList = sideList.stream().distinct().sorted().collect(Collectors.toList());

    for(int i=0; i<baseList.size(); i++) bw.append(""+ sortList.indexOf(baseList.get(i))+" ");

    bw.close();
}

 

3. 두 개의 ArrayList에 담은 요소를 HashMap을 통한 랭킹 시스템으로 해결 [ 2424ms ]

: 사실상 2번 코드랑 큰 차이가 없다.

: Map에서 직접 랭크를 받아서 주느냐, List순서대로 인덱스(=랭크)를 넣어주느냐의 차이. 

: 근데 얘는 되는것을 보니, List는 순차적 순회인 반면 Map은 랜덤하게 바로 값을 찾아주어 속도가 더 빨라서 인 듯하다.

: 아마 테스트 케이스 중 10^-9 > 10^9 사이를 전체적으로 순회하는 부분에서 갈리는 듯하다.

: 즉, 대용량 랭킹에서 Map이 더 강세를 보이는 듯하다.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class no18870 {

    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 T = Integer.parseInt(br.readLine());

        List<Integer> baseList = new ArrayList<>();
        List<Integer> sideList = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<T; i++) {
            Integer num = Integer.parseInt(st.nextToken());
            baseList.add(num);
            sideList.add(num);
        }

        List<Integer> sortList = sideList.stream().sorted().collect(Collectors.toList());

        int rank = 0;
        for(int num:sortList) {
            if(!map.containsKey(num)) {
                map.put(num, rank);
                rank++;
            }
        }

        for(int key:baseList) bw.append(""+map.get(key)+" ");

        bw.close();
    }
}

 

---

레퍼런스 코드

참고 링크 : https://st-lab.tistory.com/279