[Java] 백준 18870번: 좌표 압축

hansung's·2024년 3월 11일
백준
0

문제 url:
좌표 압축

문제:

🤔 문제 알아보기

수학 공식과 같은 요런 X가 나오면 일단 가슴이 떨린다. 설레는 것보단 부정맥에 가깝다. 그래도 문제는 풀어야 하니 같이 읽어보자,

일단 암튼, 뭐 좌표 압축을 한다고 한다.
나중에 Coordinate_Compression이라는 개념이 있다는 것을 보고 헉 했다.

장난은 여기 까지, 진지하게 문제를 살펴보면

먼저 첫 번째 TC를 살펴보면
2 4 -10 4 -9 이런 형태로 되어 있다. 여기서 해당 값을 오름차순을 하게 되면 해당 숫자가 몇 번째 인덱스에 위치하는 가를 묻는 문제라고 보면 된다.

여기서 주의할 점이 있다면, 4같은 경우는 중복된다. 하지만 중복값 같은 경우 같은 인덱스 숫자를 가리키는 데, 이 점을 유의해서 풀어야 할 것 같다.

자 이제 문제에 대해서 대충 틀은 이렇다는 것을 파악 했다.
그렇다면 조건에 어떤 제한이 있는지 살펴보자,

먼저 시간 제한은 2초다. 음.. 필자도 아직 경험이 없어 대충 1초당 1억번의 연산 횟수를 가진다 정도로만 기억하고 있다. 그럼 2초니깐 2억번? 정도 되지 않을까? 라고 판단했다.
필자는 배우는 입장이라 확실한 정보가 아니다

그 후 N은 1 ~ 1,000,000 즉, 최대 백만가지의 크기를 입력받을 수 있다는 얘기
X는 -10 ^ 9 ~ 10 ^ 9의 범위를 가지는데, 즉 -10억부터 10억까지의 숫자가 나올 수 있다는 것이다.

이 부분에서 즐겨쓰던 계수정렬은 처다도 보면 안되겠다는 생각을 가졌다.

여기까지가 필자가 생각하고 알아낸 문제점이다.

🤔 다시 알아본 문제

먼저 해당 문제는 이름부터 나와 있듯 좌표 압축(Coordinate_compression)문제이다.

좌표 압축이란?
CS 및 수학에서 일련의 좌표를 나타내는 데 필요한 메모리나 저장 공간을 줄이기 위해 사용되는 기술

개념을 찾아봤는데 예로는 압축 파일과 같은 Zip파일에 사용된다고 한다.

지금 단계에서는 좌표 압축은 여기까지만 하고,

다시 본문으로 돌아오면
아까 위에서도 살펴봤지만, 원본 데이터에 있는 값이 오름차순 된 값과 비교했을 때, 출력은 해당 값이 몇 번째 인덱스에 위치하는가? 이것이 문제의 핵심이라고 했다.

타 블로그의 말을 인용하면 원본 배열의 각 원소값에 대해서 순위를 매긴다고 한다.

즉 2 4 -10 4 -9를 정렬하면 -10 -9 2 4 4이러한 형태로 나타낼 수 있다. 그러면 -10부터 0순위 -9는 1순위 ... 4는 3순위로 매길 수 있는 것이다.

또한 4같은 경우 중복되어 나타나지만 같은 3순위를 가진다.
이 말은 중복값 같은 경우 하나의 순위만 가져야 하는데 그럴려면 중복값을 제거하고 순위를 매기면 될 것이다.

그렇다면 우리는 중복을 허용하지 않는 Set과 HashMap 자료구조를 활용할 수 있는 것이다.

문제를 제대로 이해했는지, TC를 직접 머리로 풀어본 다음 코드를 같이 보도록 하자

2 4 -10 4 -9 값이 존재하는데, 이를 정렬하면
-10 -9 2 4 4 가 나온다. 여기에 순위를 매기면

key-10-9244
value0순위1순위2순위3순위3순위

이런 형태로 나올 수 있다. 이걸 HashMap에 넣는다면, Key값에는 정렬된 값을 넣고 value에는 순위를 넣으면 추후 원본 원소의 값을 통해서 순위를 뽑을 수 있다.

이제 개념 정도는 파악되었으니 코드로 직접 보자

🐱‍👤 실제 코드

import java.io.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbd = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        //원본 배열
        int[] original_arr = new int[N];
        //정렬된 배열
        int[] sort_arr = new int[N];

        //순위를 매길 HashMap 사용
        /*
         * HashMap을 사용하는 이유:
         * HashMap을 활용하면, 키값은 중복이 안되기 때문에 중복 데이터를 없앨 수 있으며
         * 해당 키값에 대한 값을 불러올 수 있어. 순위 알고리즘에서 사용되는 자료구조이다.
         */
        HashMap<Integer, Integer> rank_list = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            original_arr[i] = sort_arr[i] = Integer.parseInt(st.nextToken());

        }

        Arrays.sort(sort_arr);

        int rank = 0;

        for (int val : sort_arr) {
            if(!rank_list.containsKey(val)) {
                rank_list.put(val, rank);
                rank++;
            }
        }

        for (int val : original_arr) {
            sbd.append(rank_list.get(val)).append(" ");
        }

        System.out.println(sbd);

    }
}

😁 코드 리뷰

  1. 원본 배열 및 정렬된 배열 생성
//원본 배열
int[] original_arr = new int[N];
//정렬된 배열
int[] sort_arr = new int[N];

먼저, 해당 배열을 정의 해주는데, 왜 두 개의 배열을 생성해주는가 하면,
배열을 정렬하게 되면 반드시 원본이 훼손된다. 그렇게 되면, 출력값을 구할 때 원본 데이터를 활용해야 하는데, 사용하지 못하는 경우가 발생한다.

그래서 배열을 이렇게 두 개를 생성하는 것이다.
※배열 크기가 N인 이유는 우리가 N개만큼 입력 받기 때문

  1. HashMap 생성 및 원소 초기화
 		//순위를 매길 HashMap 사용
        /*
         * HashMap을 사용하는 이유:
         * HashMap을 활용하면, 키값은 중복이 안되기 때문에 중복 데이터를 없앨 수 있으며
         * 해당 키값에 대한 값을 불러올 수 있어. 순위 알고리즘에서 사용되는 자료구조이다.
         */
        HashMap<Integer, Integer> rank_list = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            original_arr[i] = sort_arr[i] = Integer.parseInt(st.nextToken());

        }

특별히 어려운 코드는 아니지만, 못보던 형태가 있어 가져와봤다.

 original_arr[i] = sort_arr[i] = Integer.parseInt(st.nextToken());
 
 						↓
 int Token = Integer.parseInt(st.nextToken();
 original_arr[i] = Token;
 sort_arr[i] = Token;

개발 경험이 적기 때문에 해당 형태는 본적이 없었다. 하지만 밑의 코드가 위의 코드와 같은 기능을 한다고 하니 참고하면 좋을듯 하다.

  1. 핵심 로직
		Arrays.sort(sort_arr);

        int rank = 0;

        for (int val : sort_arr) {
            if(!rank_list.containsKey(val)) {
                rank_list.put(val, rank);
                rank++;
            }
        }

        for (int val : original_arr) {
            sbd.append(rank_list.get(val)).append(" ");
        }

        System.out.println(sbd);

아까 위에서 말했듯, sort_arr배열은 오름차순으로 정렬할 것이다.

그 후, 위에서 선언했던 rank_list(HashMap)에 정렬한 sort_arr값들을 하나씩 넣을 것이다.

그렇다면 어떻게 넣을 것이냐!
가장 먼저 나오는 -10 같은 경우 0 번째 인덱스가 될 것이다. 그 후 마지막 4같은 경우 3 번째 인덱스의 값을 가지는데,
이를 나타내기 위해 우리는 rank라는 int형 변수를 활용하고자 한다. 

		int rank = 0;

        for (int val : sort_arr) {
            if(!rank_list.containsKey(val)) {
                rank_list.put(val, rank);
                rank++;
            }
        }

그러면 위의 코드는 -10 ~부터 4까지의 값을 반환한 후,
정렬된 원소값은 key
rank는 출력에 쓰기 위한 value로 Map에 넣을 수 있는 것이다.

여기서 우리가 HashMap을 사용한 이유는 중복을 허용하지 않기 때문이라고 했다.
Map을 짧게 설명하면, Map의 value값은 중복이 가능하지만, Key값은 중복이 되지 않는다.
그래서! 4같은 경우는 하나만 받을 수 있으며, .containsKey()메서드를 이용해
현재 HashMap에 4와 같은 키값이 존재하는지를 Boolean type으로 반환 받아
중복을 제거하는 로직을 만들 수 있다.

그런 다음, 마지막 출력 파트를 살펴보면

		for (int val : original_arr) {
            sbd.append(rank_list.get(val)).append(" ");
        }

        System.out.println(sbd);

원본 배열의 원소값을 이용해 Map에 해당 값을 Key값에 넣어 Value(순위)를 출력 조건에 맞게 가져올 수 있는 것이다.

🤢 회고

사실 살펴보면 그렇게 어려운 문제는 아니었다. 다만 필자가 HashMap에 대한 이해도가 전무했고, 이러한 형태를 잘 파악하지 못한게 컸을 뿐이다
결국 잘 몰랐다는 얘기

이제, 가면 갈수록 문제가 어려워 진다. 그래서 필자도 다른 블로그 처럼 조금 더 짜임새 있고 간결하고 전문성있게 포스팅을 하고 싶지만, 필자도 또 필자와 같은 처지에 놓인 사람들을 위해 어리숙해도 A-Z까지 설명하고 살펴보고자 하여 장황하게 글을 적게 되었다.

필자의 블로그는 공부를 위한 그러면서 필자와 같은 처지에 놓인 사람을 위한 블로그이다. 이러한 점을 고려해주면, 해당 블로그 글이 조금 재밌어지지 않을까? 한다.

💢 트러블슈팅

필자 역시 해당 문제를 푸는데 손이 놀지는 않았다.
필자는 HashMap 대신, indexOf를 활용한 문제를 생각해보았고, 그에 따라 문제를 풀어보았다.

먼저 코드를 보면 다음과 같다.

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;

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());

        Integer[]arr = new Integer[N];

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

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Integer[]arr_clone = arr.clone();
        Arrays.sort(arr);

        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr_clone));

        StringBuilder sbd = new StringBuilder();
        sbd.append(Arrays.asList(arr_clone).indexOf(arr[0])).append(" ");
        for(int i = 1; i < N; i++) {
            if(arr[i] == arr[i-1]) {
                sbd.append(Arrays.asList(arr_clone).indexOf(arr[i-1])).append(" ");

            } else {
                sbd.append(Arrays.asList(arr_clone).indexOf(arr[i])).append(" ");
            }
        }

        System.out.println(sbd);

    }
}

어느 정도 접근은 유사?하다고 볼 수 있다. 원본 배열과 정렬 할 배열을 생성하고, 이를 통해 해당 인덱스 값을 뽑아쓰고자 생각했고, 거기에 필요한 메서드인 indexOf를 활용한 것이다.

나중에 알았지만. indexOf는 문자열에 해당 문자가 존재하는가를 살펴볼 때 사용한다고 한다.
그래서 배열에 indexOf를 사용하려면 Arrays.asList()메서드를 사용한 후 indexOf를 사용해야 한다.

Arrays.asList란?
배열인 형태를 List형태로 변환시켜주는 것,

그래서 위의 배열을 보면 int가 아닌 Integer인 것을 볼 수 있는데,
이를 처음에는 int를 활용하니 값을 아예 찾지 못했다.

※ indexOf는 반환할 인덱스가 없으면 -1을 반환,
그 이유를 찾아보니, Arrays.asList() 의해 List로 바뀌게 되어 Integer 객체로 받아야 되는데 int형을 받게 되어 저렇게 인덱스를 찾지 못한다고 한다.

그래서 위의 배열 타입이 Integer인 것이다.

아무쪼록, 저렇게 하고 indexOf로 인덱스 값을 반환하려고 딱 하니! 아래와 같은 값이 나온 것이다.

4를 아예 잘 찾지도 못하고... 이유를 찾아보니
indexOf()메서드는 내부적으로 해당 요소의 값을 찾을 때 값의 동일성을 확인하기 위해 equals() 메서드를 사용한다고 한다.

그러나 Integer 객체들 사이의 동일성은 값의 동일성과 달라 4와 같이 같은 값이더라도 서로 다른 객체로 볼 수 있다는 것입니다.
즉. 숫자는 같은 4일지라도 다른 객체의 주솟값을 가지고 있을 수 있다는 얘기이다.

해당 이유가 정확한 이유인지는 모르겠다. 혹시 이 글을 끝까지 읽은 전문가가 계신다면 답변해주시면 정말로 감사하겠습니다!.

어쨋든... 이번 문제를 통해 HashMap과 좌표압축에 대해서 조금 더 알아 갈 수 있어 좋았다.


z.. 약간 기념비 같은 문제다.

💜 참고자료

[백준] 18870번 : 좌표 압축 - JAVA [자바] Stranger's LAB

profile
hansung's
ABAPER를 꿈꾸는 개발자
이전 포스트

[Java] 백준 10814번: 나이순 정렬

다음 포스트

[Java] toString? 그게 뭔데

0개의 댓글