#18870 : 좌표 압축

풀이방법

사용된 것:

HashMap

StringTokenizer

StringBuilder

 

 

2022.01.28

오답노트 #18870 : 좌표 압축

주어진 정수들에 순위를 매겨 그 순위를 출력하는 문제이다.

값이 같은 정수끼리는 순위도 같다.

가장 작은 정수가 0위이며 클수록 순위는 1씩 증가한다.

 

수들을 입력된 순서대로 저장하는 배열,

수들을 정렬하여 오름차순으로 정렬할 배열,

각 수마다의 순위를 저장할 HashMap이 필요하다.

 

오름차순으로 정렬한 배열을 처음부터 하나씩 HashMap의 key로 추가하면서, value에는 순위를 저장한다.

 

value의 값을 저장할 int형 변수 rank는 초기값이 0이다. 즉 HashMap에 첫 번째로 저장되는 수의 value는 0인 것이다.

다음의 과정을 통해 중복을 고려할 수 있다.

각 수를 저장할 때, 만약 이번에 체크하는 수가 기존의 key 중에 없다면(중복값이 아니라면) HashMap에 추가하는 동시에 rank를 1 증가시킨다.

이번에 체크하는 수가 기존의 key 중에 있다면(이미 map에 넣은 수 즉 중복값이라면) HashMap에 추가를 하지 않고, rank 값도 그대로 유지한다.

이렇게 하면 손쉽게 중복을 고려하여 순위를 매길 수 있다.

 

최대 입력 개수가 워낙 많아서 출력마저도 시간이 적게 드는 방식을 택해야 성공할 수 있었다.

 

각 정수마다의 순위를 get 해오자마자 즉시 출력하면 System.out.print()를 N번 반복하게 되는데, 이렇게 하면 시간초과가 발생한다.

StringBuilder를 이용해, get 한 값을 붙인 다음 한 번에 출력하면 스트링빌더.append()를 N번 반복하고 System.out.print()는 한 번 수행하게 되는데, 이렇게 하면 시간 내에 성공한다.

 

아무래도 System.out.print()가 append보다 오래 걸리나 보다...

 

지금까지는 올바른 출력값을 구해오는 과정의 복잡도와 소요시간만 고려했는데 이렇게 출력까지 신경써야 하는 경우가 있다니 놀랍다. 좋은 교훈을 얻었다.

 

그리고, 출력값 사이에 공백이 필요한 문제를 풀 때 나는 여태 마지막 값 뒤에는 공백을 안 넣으려 애썼다. 그러나 쓸데없는 짓이었다. 걱정 말고 모든 값 뒤에 공백을 붙이자.

 

코드

Java(2022.01.28)

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

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;


public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] nums = new int[n];
		int[] temp = new int[n];
		Map <Integer,Integer> map = new HashMap<Integer,Integer>();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
        //오리지널 배열과 복사본 배열에 모두 값을 저장
		for(int i = 0; i<n; i++) {
			nums[i] = temp[i] = Integer.parseInt(st.nextToken());
		}
		
        //복사본 배열을 정렬
		Arrays.sort(temp);
		
        //각 수와 순위를 HashMap에 저장
		int rank = 0;
		for(int i : temp) {
			if(!map.containsKey(i)) {
				map.put(i,rank);
				rank++;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
        //출력할 문자열 생성
		for(int i : nums) {
			sb.append(map.get(i)).append(" ");
		}
		
        //정답 출력
		System.out.print(sb);
		
	}

}