intro : 간만에 문제에서 뭘 원하는지 모르겠는 문제가 나왔다.

문제

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

출력

첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.

문제 풀이 (1772ms)

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 입력값의 개수
        int forCount = Integer.parseInt(br.readLine());
        // 원데이터를 저장할 배열 변수
        int[] originalArray = new int[forCount];
        // 정렬데이터를 저장할 배열 변수
        int[] sortArray = new int[forCount];
        // 입력값을 공백기준으로 나누기 위한 StringTokenizer 객체 생성
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 반복문을 통해 originalArray, sortArray에 데이터 할당
        for (int i = 0; i < forCount; i++) {
            String line = st.nextToken();
            originalArray[i] = Integer.parseInt(line);
            sortArray[i] = Integer.parseInt(line);
        }

        // 배열 오름차순으로 정렬
        Arrays.sort(sortArray);

        int index = 0;
        // Map<정렬데이터, index(순서)> 로 저장하기 위한 map 변수 선언
        Map<Integer, Integer> map = new HashMap<>();
        for (int value : sortArray) {
            // 중복된 데이터인 경우는 거르기 위함
            if (!map.containsKey(value)) {
                map.put(value, index);
                index++;
            }
        }
        // 원데이터를 몇번째 인덱스에 해당하는지 map 에서 찾기
        for (int ori : originalArray) {
            // sb.append() 메서드를 통해 저장
            sb.append(map.get(ori)).append(" ");
        }
        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(sb.toString());
        bw.flush();
        // 자원 반납
        bw.close();
        br.close();
    }
}

문제 해석

간만에 문제 자체만으로 무슨말인지 도저히 모르겠는 문제가 나왔다. 가끔 이런 문제를 보면 문제를 너무 성의없이 내는게 아닌가 싶을때가 있는데, 딱 이런문제가 그런 문제다. 정확히 무엇을 원하는지가 명확하지가 않다. 입력예제랑 출력을 보고 문제에서 원하는 바를 추측해 보았다.

[입력 예제 1]
5
2 4 -10 4 -9
------------------
[예제 출력 1]
2 3 0 3 1
------------------
[입력 예제 1 정렬 (오름차순)]
-10(0), -9(1), 2(2), 4(3), 4(4)

문제 추측

딱 위 내용을 보니까 대충 문제에서 원하는 바가 정렬한 값이 원래 값에 맞춰서 인덱스 값을 추출하는걸 원하는 거구나 싶었다. 다만 중복된 값을 하나의 인덱스만을 가지는거 같았다, 입력예제 1번에서의 4는 두번등장하는데 출력된 결과를 보면 3이 2번 출력된다. 만약 중복을 포함하는거라면 3,4 로 값이 나왔을거 같은데 그게 아닌거보니 중복을 제거해서 인덱스를 계산해야한다는 점을 알 수 있다.

(과연 이런식으로 추측해서 문제를 푸는게 맞나싶은데, 정말이지 이 문제는 문제 텍스트가 너무 성의가 없는거 같다.)

구현 방향

이 문제의 핵심은 주어진 좌표들을 압축하여 정수 인덱스로 변환하는 것 같았다. 이해한 내용을 기반으로 좌표 간의 상대적 크기를 반영하여 배열을 생성하였고 원데이터와, 정렬한 데이터를 두개로 나누어 관리하였다. 그후에 정렬한 데이터를 map 변수에 저장을 하는데, 이때 중복된 데이터를 저장하지 않기 위해 검증로직을 추가하였다. containsKey 메서드는 시간복잡도가 1이라 빨라서 나는 자주 애용한다.

그 이후 원데이터를 반복문을 돌면서 원데이터의 값을 map에서 꺼낸다, Hash값이기 떄문에 이 또한 시간 복잡도는 1이라 빠르게 값을 찾아서 StringBuilder에 값을 추가할 수 있다.

마무리

문제 자체를 정확히 이해하지 못하고 풀어서 뭔가 다양한 관점으로 보기 어려웠던게 좀 많이 아쉽다. 그리고 시간이 굉장히 오래걸리길래 다른 분들 풀이 시간을 확인해보았는데, 다들 1초 ~ 2초 사이를 소요하고 있으신거 같았다. 이 문제 특성상 입력값이 크게주어져서 시간이 굉장히 오래 소요 되는 것 같았다.

I am visible

contact

문제

입력

출력

문제 풀이 (1772ms)

문제 해석

문제 추측

구현 방향

마무리