Baekjoon Online Judge

algorithm practice

단계별 문제풀기

12. 정렬

배열의 원소를 순서대로 나열하는 알고리즘을 배워 봅시다.

Java / Python

10. 좌표 압축

18870번

만약 정확한 값이 필요 없고 값의 대소 관계만 필요하다면, 모든 수를 0 이상 N 미만의 수로 바꿀 수 있습니다.

• Java

clone 함수를 통해 입력 받은 Number 함수를 복제하고, 정렬한다. Map을 활용해, <좌표값, 좌표값의 최소 인덱스>를 저장하고, 정렬한 배열을 이용해서 map에 이미 존재하는 좌표라면 무시하고 아니라면 map.put을 사용하여 좌표값과 인덱스를 저장하고 인덱스를 하나 증가시켜 주는 것을 반복한다.
마지막으로 기존 배열의 좌표값으로 map.get을 통해 인덱스 값을 얻어온다.

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] numbers = new int[N];

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

		int[] sort_n = numbers.clone();
		Arrays.sort(sort_n);

		Map<Integer, Integer> map = new HashMap<>();
		int idx = 0;
		for (int n : sort_n)
			if (!map.containsKey(n))
				map.put(n, idx++);

		for (int n : numbers)
			sb.append(map.get(n)).append(' ');

		bw.write(sb.toString());

		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

import sys
input = sys.stdin.readline

N = int(input())
numbers = list(map(int, input().split()))
sort_n = sorted(list(set(numbers)))
dic = {sort_n[i] : i for i in range(len(sort_n))}

for n in numbers:
    print(dic[n], end = ' ')

정렬단계 마지막 예제입니다..! (정렬 단계 추가된 문제)