백준 18870 좌표압축 자바 java

 

간단해 보이는 문제였으나 등급이 높은 만큼 막히는 부분이 있었던 문제이다.

 

특히 동일한 값을 제외하는 것이 관건이었다.

 

첫 번째 방법은 브루트 포스 처럼 값을 하나하나 비교하며 푸는 방법이다.

 

 자기 자신보다 작은 값을 비교하여 리스트에 저장하고 이를 set로 바꾸어 중복된 값을 제거했다.

 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int arr[] = new int[N];
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
            	// 모든 값을 비교하기 위한 이중 반복문
                if (arr[i] > arr[j]) {
                    list.add(arr[j]);
                    // 본인보다 작은 값을 list에 저장한다
                }
            }
            Set<Integer> set = new HashSet<>(list);
            // list의 값을 set형태로 바꾸어 중복을 제거한다.

            System.out.print(set.size() + " ");
            list.clear();
            // 리스트 값을 제거한다.
        }

        // 자기보다 작은 값의 개수이나 값이 겹칠 경우 제외한다.
        // 일단 자기보다 작은 값을 모두 저장 후 겹치는 값 제거!

        sc.close();
    }

}

 

 

하지만 이 방법은 시간초과가 발생한다.

 

이 방법은 시간복잡도 평균 O(n^2)이므로 계산할 값이 커질 수록 처리사간도 기하급수적으로 커진다.

 

그렇다면 새로운 방법을 찾아보야한다.

 

다른 사람이 쓴 코드를 참고하였다.

 

HashMap를 이용해보자

 

2 4 -10 4 -9 라는 값이 들어왔다고 치자, 그렇다면 결과는 2 3 0 3 1 이 된다. 

 

패턴을 분석해 보자면 숫자가 작을수록 빠른 순번을 가진다는 것을 알 수 있다. 

 

-10은 -, -9는 1 , 2는 2, 4는 3이다.

 

이것을 어떻게 코드로 나타낼까?

 

1. 입력받은 값을 두 개의 다른 배열에 저장한다.

2.  첫 번째 배열은 기존 값을 유지하도록 놔두고, 두 번째 배열은 오름차순으로 정렬한다.

3. for-each문을 이용하여 정렬된 값에 순서대로 0부터 순서를 매긴다.

    즉 -10이면 0, -9면 1이 순서대로 들어가는 키와 값으로 들어가는 것이다.

4. for-each문에 if와 containsKey를 사용하여 중복값을 제거한다. 

    즉 이 for-each문을 돌림으로서 중복된 값을 제거하고 key에는 정렬된 배열, value에는 0부터 순위가 들어가게 되었다.

5. 또 다른 for-each문을 돌려 이번에는 정렬되지 않는 arr1의 key에 해당하는 value값을 출력함으로서 문제를 마무리 한다.

 

 

import java.util.Scanner;
import java.util.HashMap;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int arr1[] = new int[N];
        // 원본 배열

        int arr2[] = new int[N];
        // 정렬 배열

        HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();
        // 두 개의 int를 받는 HashMap 선언

        for (int i = 0; i < N; i++) {
            arr2[i] = arr1[i] = sc.nextInt();
        }
        // arr1, arr2에 입력된 값을 넣음

        Arrays.sort(arr2);
        // arr2를 정렬

        int rank = 0;

        for (int v : arr2) {
            if (!rankingMap.containsKey(v)) {
                // 겹치는 값이 없다면
                rankingMap.put(v, rank);
                // v는 arr2를 순서대로 넣는 것
                // rank는 0부터 순서대로 넣는 것
                rank++;
            }
        }
        // 정렬된 배열은 순회하며 map에 넣어준다.

        StringBuilder sb = new StringBuilder();

        for (int key : arr1) {
            // 정렬되지 않은 arr1에
            int ranking = rankingMap.get(key);
            // arr1 각 값에 해당하는 rankingMap 값을 가져온다.
            sb.append(ranking).append(' ');
            // 순서대로 공백을 포함하여 이어붙이기
        }

        System.out.print(sb);
        // 출력
        sc.close();
    }

}