[Java] 백준 18870 - 좌표 압축

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

18870번: 좌표 압축

시나리오

주어진 좌표 \(X_i\)을 압축 알고리즘을 적용하여 결과 좌표 \(X'_i\)를 출력하는 문제이다.

여기서 압축 알고리즘에 대한 규칙은 제시되어 있지 않아 추론해봐야 하는데, 문제 조건 중 좌표를 압축한 결과 \(X'_i\)의 값은 \(X_i > X_j\)를 만족하는 서로 다른 좌표의 개수와 같아야 한다고 한다.

이점과 주어진 예제를 고려해봤을 때,  좌표 \(X_i\) 위의 값의 중복을 없앤 뒤 오름차순으로 0부터 N까지 1씩 증가하도록 매핑한 결과 좌표가  \(X'_i\)가 되는 것을 발견할 수있었다.

내가 말하고도 무슨말인지 모르겠으니 예를 들면

좌표 \(X_i\)위의 값이 2 4 -10 4 -9 이라면, 중복을 없앴을 때 2 4 -10 -9가 되며, 오름차순으로 정렬하면 -10 -9 2 4가 된다.

이를 0부터 N까지 1씩 증가시켜 매핑시키면 각각의 값은 0 1 2 3이 되고 원본의 순서대로 새로운 좌표  \(X'_i\)에 찍으면 2 3 0 3 1이 되는 것이다.

 

이를 토대로 의사 코드(주석)를 먼저 작성했고 문제를 풀었다.

내 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //1. n입력, Xn입력받기
        //1-1. 입력받아서 배열 복사 -> set으로 중복제거 한 결과 -> 찍어야할 좌표값 구함.


        //기존 배열을 기반으로 완탐하며 그 요소를 map의 key로 설정하여 얻음
        //value출력 souf("%d ", v)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Integer> originalCoordi = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            originalCoordi.add(Integer.parseInt(st.nextToken()));
        }

        Map<Integer, Integer> map = makeNewCoordi(originalCoordi);

        //3. X'i 출력

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int originalValue = originalCoordi.get(i);
            sb.append(map.get(originalValue)+" ");
//            System.out.printf("%d ", map.get(originalValue));
        }
        System.out.println(sb.toString());
    }

    //2. 압축 알고리즘 구현
    //2-1 서로 다른 좌표 구하기
    // set으로 중복제거 -> 개수 카운트해서 n의 값 구하기 (n은 X'i에 찍을 좌표 개수)
    // set요소로 list만들어 정렬 -> k,v값 완성!
    //2-2 중복이 걸러진 set을 기반으로 map(k:원래 좌표값, v: 압축된 좌표값) 생성(2:2, 4:3, -10:0, -9: 1)
    private static Map<Integer, Integer> makeNewCoordi(List<Integer> origin) {
        Set<Integer> set = new HashSet<>(origin);
        //setToList
        List<Integer> setToList = new ArrayList<>(set);
//        for (int e : set) {
//            setToList.add(e);
//        }

        //sorting
        Collections.sort(setToList);

        Map<Integer, Integer> map = new HashMap<>();

        //create Map
        for (int i = 0; i < setToList.size(); i++) {
            map.put(setToList.get(i), i);
        }

        return map;
    }
}

//새로 알게된 사실 HashSet의 생성자는 Collection받아 모든 요소 추가하는 ㅇㅇ
//배열말고 리스트쓰자

//Collection끼리는 생성자에 집어넣어서 모든 요소 옮길 수 있음

처음엔 배열을 사용하다 Set을 사용할 땐 List가 훨씬 편리하다는 것을 발견해 List로 바꾸었으며 그 과정에서 새로운 사실을 알게됐다. 그 내용은 아래 정리하도록 하겠다.

그리고 결과값 \(X'_i\)을 한줄로 출력해야 하는데 처음엔 멋모르고 System.out.printf()문을 List의 크기만큼 호출하다 시간초과가 났다.

그래서 여러 방법을 생각해보다 StringBuilder가 효율적이라는 사실이 생각나 List의 크기만큼 반복문을 돌며 StringBuilder객체에 append하는 것으로 코드를 수정했다. 그 결과, 정답 처리를 받을 수 있었다.

 

새로알게된 점

1. Collection 자료구조는 객체 생성 시, 기존 Collection자료구조를 생성자 매개변수로 넘겨 Collection.addAll()을 호출한 것과 같은 결과를 낼 수 있다.
2. 문자열을 n번 출력해야 한다면 System.out.println()을 n번 호출하는 것보다 StringBuilder에 n번 append하는 것이 훨씬 효율적이다.
3. "%d "식으로 문자열을 append하다 보니 마지막에 의도치 하는 whitespace가 생겨 String.strip()을 사용해 제거하고 제출하였는데, 제거하지 않고 제출해도 정답처리는 나오더라.. 참고하도록 하자.