[PS] 백준 18870 좌표 압축 java 풀이

18870번: 좌표 압축 (acmicpc.net)

초기 문제 접근

• 일단 문제 이해부터가 어려워서 질문 게시판을 찾아보니,그냥 이 배열 중 자기보다 낮은 원소의 개수를 출력하는 것 이었음
• 근데 최대 N이 1,000,000 이니까 이중 for 문 쓰면 무조건 터질 것 같음
• 정렬하고 하나하나 비교하나..?
• 조금 찾아보니 이진 탐색을 사용하면 된다고 나와있음

GPT의 문제 접근

• 하지만 단순히 Map 사용으로 문제를 해결할 수 있었음
• 각 순위를 표시할 rank = 0을 선언함
• 정렬한 배열을 첫 번째 인덱스부터 순회함
• Map 안에 현재 순회하는 값이 없다면 새로 삽입 후 rank++
• 결과적으로 숫자 별로 순위가 Map에 저장이 됨

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N;

    public static void main(String[] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			N = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int[] original = new int[N];
			int[] sorted = new int[N];
			
			for (int i = 0; i < N; i++) {
				original[i] = Integer.parseInt(st.nextToken());
				sorted[i] = original[i];
			}
			
			Arrays.sort(sorted);
			
			Map<Integer, Integer> compressionMap = new HashMap<>();
			
			int rank = 0;
			for (int i = 0; i < N; i++) {
				if (!compressionMap.containsKey(sorted[i])) {
					compressionMap.put(sorted[i], rank++);
				}
			}
			
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < N; i++) {
				sb.append(compressionMap.get(original[i])).append(" ");
			}
			
			System.out.println(sb);
		}

}