[백준 | Java] 18870번 좌표 압축 - Sort

18870번 / 좌표 압축

❓ 좌표 압축

🏷️ 관련 주제 : Sort

---

💦 나의 시도

Set과 정렬, Map을 사용한 방법

1. int N에 입력값을 형변환하여 할당 : 입력할 값의 개수
2. StringTokenizer st로 입력값 받기
3. int[] X를 길이 N인 int 배열로 선언 : 입력값을 넣을 배열
   좌표 압축 결과 $X'_i$의 값은 $X_i$ 보다 작은 서로 다른 $X_j$의 개수
   서로 다른 값의 개수를 세므로 중복값을 허용하지 않는 Set을 사용해보자.
4. Set xSet을 선언 : X의 원소를 중복되지 않게 담을 Set
5. 0 ~ (N - 1) 범위를 반복문 돌기
   • i는 반복문의 int 변수
   • X[i]에 StringTokenizer의 nextToken()값을 변환하여 할당
   • xSet에 X[i] 추가
6. Stream API를 사용하여 xSet의 원소를 오름차순 정렬하여 int[] xArr에 할당
   이때, xArr의 i번 인덱싀의 값의 좌표 압축 결과는 i
7. 각 좌표에 대한 좌표 압축 결과를 담을 Map<Integer, Integer> cntMap 선언
   • 키 : 좌표
   • 값 : 좌표 압축 결과
8. 0 ~ xArr.length 범위를 반복문 돌면서 cntMap에 xArr[i]를 키로, i를 값으로 넣기
9. for-each문으로 X의 원소를 하나씩 꺼내기(x)
   • cntMap에서 좌표 압축 결과를 꺼내(cntMap.get(x)) 공백(" ")을 붙여 BufferedWriter에 쓰기
10. BufferedWriter의 close() 메서드를 사용해 결과값 출력하기

---

 

---

📑제출 기록 및 오답 원인

---

💯 해결 방법

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] X = new int[N];
        Set<Integer> xSet = new HashSet<>();
        for (int i = 0; i < N; i++) {
            X[i] = Integer.parseInt(st.nextToken()); 
            xSet.add(X[i]);
        }


        int[] xArr = xSet.stream().sorted().mapToInt(i -> (int) i).toArray();
        Map<Integer, Integer> cntMap = new HashMap<>();

        for (int i = 0; i < xArr.length; i++) {
            cntMap.put(xArr[i], i);
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int x : X) {
            bw.write(cntMap.get(x)+ " ");
        }
        bw.close();

    }
}

---

🏷️ 문제 풀면서 참고한 내용

• Java의 int 타입은 -2,147,483,648 ~ 2,147,483,647 의 범위까지 저장할 수 있습니다.