BOJ_18870 : 좌표 압축

👉 문제링크

18870번: 좌표 압축

---

---

🔸 문제 분석 🔸

• 입력받은 n개의 수에서 전체 입력 중에 더 작은 값의 개수를 출력한다.
  
  • 2차원 배열 arr[n][3]을 선언한다.
    • 1번째는 입력 값, 2번째는 입력 순서, 3번째는 압축 값을 저장한다.
  • 1번째 값 기준으로 오름차순 정렬한다.
  • 3번째 값을 채운다
    • 배열 앞에서 부터 더 작은 값은 0, 1, 2...로 커져간다.
    • 같은 값이 연속되서 나오면 값을 키우지 않고 그대로 저장한다.
  • 2번째 값 기준으로 정렬해 처음 입력 순서로 되돌린다.
  • 3번째 값을 출력한다.

🔸 코드 🔸

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

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][3];
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        // 2
//        Arrays.sort(arr, (o1, o2) -> o1[0] - o1[0]); // 람다식 표현
        Arrays.sort(arr, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });

        // 3
        int count = 0;
        arr[0][2] = count;
        for (int i = 1; i < n; i++) {
            if (!(arr[i][0].equals(arr[i-1][0])))
                count++;
            arr[i][2] = count;
        }

        // 4
        Arrays.sort(arr, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i][2] + " ");
        }
        System.out.println(sb);
    }
}

🔸 코드 해석 🔸

• 1) n개의 수와 그 순서를 입력받는다.
• 2) 입력 받은 수를 기준으로 오름차순 정렬한다.
• 3) 붙어있는 값이 같으면 그대로, 다르면 count + 1 값을 넣어 문제의 압축을 저장한다.
• 4) 순서 값으로 오름차순 정렬해서 처음 입력받은 순서로 되돌린다.
• 출력한다.

---

🔸 end 🔸

• 2차원 배열의 속 원소의 개수를 3개로 지정하는 방식을 사용했다.
  • 저번에도 보고 2번째 사용하는 방법인데, 잘 생각해낸 것 같다.
• 특정 값으로 정렬하는 오버라이드 메서드 compare에서 Integer를 사용했기 때문에, 원래는 o1-o2를 사용했는데 작동하지 않았다. '-' 연산자를 지원하지 않기 때문인데, Integer.compare()를 사용했다. (같은 결과)
  • 2번째 값을 넣는 for문에서도 if문에서 '!='연산자를 사용했는데 Integer 끼리의 연산은 지원하지 않기 때문에 제대로 작동하지 않았다. .equals()로 변경했다.
• 시간초과가 나서 입력과 출력형식을 빠르게 바꿨더니 통과되었다.
• LCD 패드에 문제분석과 코딩계획을 짜는 방법을 시도해 보았는데, 좋은 점이 많은 것 같아 더 연습할 생각이다.
  • 문제 분석이 더 확실하게 되었다. 문제를 계속 다시읽지 않고 계획대로 쭉 코딩했다.
  • 중간에 계획을 수정 할 때에도 헷깔리지 않았다. (int를 Integer로 변경 등...)