[백준] 18870번 : 좌표 압축 _ JAVA ( 주석 설명 )

* 배운 점

입력된 값에 중복은 있으나 출력은 입력 수만큼 해야 한다는 생각에

'HashMap 은 key 중복이 안 되므로 사용하면 안된다'  고 넘겨짚었다. -> 'key value 를 상황에 따라 적절히 넣어주면 된다.'

문제를 풀면서 자료구조가 언제 어떻게 쓰이면 될 지 정확히 이해하고 넘어가도록 하자

 

---

 

1번 (시간초과)

→ 2번과 비슷하게 접근했으나,

HashMap 자료구조를 사용하지 않고 직접 중복된 값을 제거하는 과정 + list.indexof() 에서 시간초과가 났을 것으로 예상한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
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()); //수직선 위의 좌표의 개수를 입력받는다.
        ArrayList<Integer> ary = new ArrayList<>(N); //좌표를 저장하기 위해 좌표의 개수만큼의 ArrayList 공간을 생성한다.


        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;++i){
            ary.add(Integer.parseInt(st.nextToken())); //수직선 위의 좌표를 입력받는다.
        }

        ArrayList<Integer> duplicate = (ArrayList<Integer>) ary.clone(); //정렬된 값에서, 정렬되기 전의 값들의 인덱스를 검색하기 위해 복사 배열을 만든다.

        Collections.sort(duplicate); //복사된 배열을 정렬한다.

        for(int i=0;i<duplicate.size()-1;++i){ //중복된 값은 제거해준다.
            if(duplicate.get(i).equals(duplicate.get(i+1))){
                duplicate.remove(i);
                i--; //재차 검사를 위해 i--를 해준다.
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N;++i){
            sb.append(duplicate.indexOf(ary.get(i))).append(' '); //정렬된 복제 ArrayList에서 처음 입력받은 ArrayList의 인덱스 값을 찾는다.
        }

        System.out.println(sb); //좌표 압축한 결과를 출력한다.
    }
}

 

---

 

2번

→ 기존 입력받은 자료구조에서 규칙(순위)을 찾아 그에 맞게 정렬을 한 후,

중복을 제거하기 위해 HashMap 의 key - value 에 '정렬 값' - '순위' 를 저장한다.

그리고 기존에 입력받은 값들을 전체 한 번 순회하며 key 값과 매칭함으로써 원하는 값을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 입력을 위해 버퍼를 이용해 입력을 받는다.
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine()); //수직선 위의 좌표의 개수를 입력받는다.
        ArrayList<Integer> list  = new ArrayList<>(N); //좌표 수만큼의 ArrayList 공간을 생성한다.


        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){ //입력받은 값을 ArrayList에 저장한다.
            list.add(Integer.valueOf(st.nextToken()));
        }

        ArrayList<Integer> clone = (ArrayList<Integer>) list.clone(); //정렬 리스트를 따로 저장하기 위해 복사를 한다.
        Collections.sort(clone); //오름차순으로 정렬한다.


        HashMap<Integer,Integer> map = new HashMap(N); //정렬한 좌표를 중복 없이 저장하기 위해 HashMap 구조를 사용한다.
        int rank = 0; //자신보다 작은 수가 몇 개 있는지
        for(int i=0;i<clone.size();++i){
            int input = clone.get(i); //정렬한 좌표에서 각 인덱스별로 추출하여 map 에 저장한다.
            if(!map.containsKey(input)) { //key : 좌표값, value : 순위 을 넣는다. //containsValue 를 검사하는 이유는 중복된 수 index 를 계산하지 않기 위함이다.
                map.put(input, rank);
                rank++; //순위를 올린다.
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;++i){
            sb.append(map.get(list.get(i))).append(' '); //비정렬된(입력) 리스트 차례대로 값을 가지고 와 map - key 와 맞춰보며 순위를 찾는다.
        }

        System.out.println(sb); //순위를 출력한다.
    }
}