CodingTest #27 Java 18870 (좌표 압축) 문제 풀이

출처 핀터레스트

 

쉬우면서도 어려운 문제였다.

 

나 같은 경우는 한 배열로 두 번의 Arrays.sort함수를 사용했다.

 

코드를 보자.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Test18870 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        Item[] arr = new Item[N];


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

        //value형식으로 sort해주기
        Arrays.sort(arr, (e1, e2) -> {
            if(e1.value < e2.value) {
                return -1;
            } else if(e1.value == e2.value) {
                return 0;
            } else {
                return 1;
            }

        });

        int rank = 0;
        //이전 값
        Integer beforevalue = null;

        for(int i = 0; i < N; i++) {
            //이전 값이 null이 아니고, 이전값과 값이 같으면
            if(beforevalue != null && beforevalue == arr[i].value) {
                beforevalue = arr[i].value;
                arr[i].value = rank - 1;
                continue;
            }
            beforevalue = arr[i].value;
            arr[i].value = rank;
            rank++;
        }


        //여기서는 id형식으로 sort해주기
        Arrays.sort(arr, (e1, e2) -> {
            if(e1.id < e2.id) {
                return -1;
            }else if(e1.value == e2.value) {
                return 0;
            } else {
                return 1;
            }
        });


        for(int i = 0; i < N; i++) {
            sb.append(arr[i].value).append(" ");
        }

        System.out.print(sb);

    }

    static class Item {

        final int id;
        int value;

        Item(int id, int value) {
            this.id = id;
            this.value = value;
        }
    }
}

 

우선 정렬을 위한 인덱스값이 필요하므로, 모델 클래스를 하나 만들어 준다.

 

static class Item {

        final int id;
        int value;

        Item(int id, int value) {
            this.id = id;
            this.value = value;
        }
    }

id 값의 index값을 넣고 int에 nextToken()으로 받은 값들을 넣어준다.

 

그리고 한번에 정렬을 해주는데,

 

value값에 따른 정렬을 우선적으로 해준다.

 

그리고 for문을 통해 오름차순으로 정렬한 이 배열을 다음과 같이 작성하여,

 

(랭크를 매기는 알고리즘이다)

 

for(int i = 0; i < N; i++) {
            //이전 값이 null이 아니고, 이전값과 값이 같으면
            if(beforevalue != null && beforevalue == arr[i].value) {
                beforevalue = arr[i].value;
                arr[i].value = rank - 1;
                continue;
            }
            beforevalue = arr[i].value;
            arr[i].value = rank;
            rank++;
        }

 

이 로직이 끝나게 되면

 

다시 한번 정렬을 해준다.

 

이번에는 각자 자리에서 순위가 매겨져야 하기 때문에,

 

현재 위치에서 정렬된 값을 넣어준다.

S

그렇게 마무리로 StringBuilder 메서드로 마무리한 결과물이 나온다.

 

for(int i = 0; i < N; i++) {
    sb.append(arr[i].value).append(" ");
}

System.out.print(sb);

 

나 같은 경우 문제풀이 시간이 다음과 같이 나왔다.

 

 

아래 나온 3700ms이 내 코드 결과물이다..

 

두배 가량 차이가 나는 것을 볼 수 있다.

 

역시나 Strongers님의 풀이를 아직까진 따라잡는 것은 역부족인 것 같다.

 

위에 1840ms가 바로 아래 코드에서 나온 것이다.

 

https://st-lab.tistory.com/279

[백준] 18870번 : 좌표 압축 - JAVA [자바]