오답노트 #18870 : 좌표 압축

풀이방법 및 문제점

2022.01.28 (1)

입력 수열의 값을 복사한 temp 배열을 크기순으로 정렬하면 각 좌표의 압축 결과를 쉽게 구할 수 있다.

그 다음 temp값과 기존 입력 수열의 값을 비교하여 본래 순서에 맞게 결과값을 화면에 출력하였다.

 

문제점: 시간초과.

데이터의 개수 N이 최대 100만 개이고 제한시간은 2초이다.

그런데 압축 결과값을 구하는 부분, 값을 출력할 순서를 알아내기 위해 기존 입력 수열을 조회하는 부분 모두 $N^2$의 시간복잡도를 가져서 시간을 많이 초과하였다.

 

2022.01.28 (2)

HashMap을 사용하여 코드를 짜보았다.

HashMap의 key에는 정수 값을, value에는 순위를 저장한 뒤 조회하는 방식이다.

그런데 또 시간이 초과된다.

얼마나 더 빨라져야 하는 거지?

버퍼드리더를 쓰든 스캐너를 쓰든 모두 시간이 초과된다.

 

2022.01.28 (3)

(2)의 코드에 스트링토크나이저를 써보았다. 시간이 초과된다.

알고리즘 자체를 잘못 짰나 싶어, 내가 참고한 블로그에서 쓰신 코드를 복붙하여 백준에 돌려보았다. 그런데 이 코드는 된다... 1900ms 정도 나온다.

뭐지...? 알고리즘의 내용은 같은데...

내가 * 기호로 쓸데 없는 import를 많이 해서인가? 확인해보니 이것도 아니었다.

 

이분과 나의 코드의 차이점은 출력과 반복문 두 가지다.

 

먼저 출력을 할 때

나는 for문 내에서 순위를 get해오는 즉시 하나씩 출력했고,

이분은 StringBuilder를 이용하여 출력용 문자열을 완성한 뒤 이것을 한 번에 출력했다.

 

다음은 반복문의 차이이다.

나는 아래와 같이 썼고

for(int i =0; i<n; i++)

 

이분은 이렇게 썼다.

for(int v : sorted)

 

처음 보는 작성법인데, 알아보니 이것은 향상된 for문이라고 한다. 배열의 모든 요소들에 대하여 순서대로 같은 작업을 반복하는 식이다.

그런데 일반 for문과 향상된 for문 간에 큰 성능 차이는 없다고 한다. 오히려 일반 for문이 더 빠르다는 소문이 돌았었다고 한다...

for문은 그대로 두고 출력 방식만 바꾸어보아야겠다.

 

2022.01.28 (해결)

해결되었다. 출력 방식이 문제였다.

System.out.print()가 append()보다 시간을 많이 잡아먹는 듯하다.

정답 게시물 바로가기

 

코드

Java(2022.01.28) (1)

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

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());
		
		String[] input = br.readLine().split(" ");
		int[] nums = new int[n];
		int[] result = new int[n];
		int[] temp = new int[n];
		
		for(int i = 0; i<n; i++) {
			nums[i] = Integer.parseInt(input[i]);
			temp[i] = nums[i];
		}
		
		Arrays.sort(temp);
		
		for(int i = 0; i<n; i++) {
			for(int j = i-1; j>=0; j--) {
				if(temp[j]<temp[i]) {
					result[i] = j+1; break;
				}
			}
		}
		
		for(int i =0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				if(nums[i] == temp[j]) {
					System.out.print(result[j]); break;
				}
			}
			if(i != n-1) System.out.print(" ");
		}
		

	}

}

Java(2022.01.28) (2)

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

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());
		
		String[] input = br.readLine().split(" ");
		int[] nums = new int[n];
		int[] temp = new int[n];
		Map <Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for(int i = 0; i<n; i++) {
			nums[i] = temp[i] = Integer.parseInt(input[i]);
		}
		
		Arrays.sort(temp);
		
		int rank = 0;
		for(int i = 0; i<n; i++) {
			if(!map.containsKey(temp[i])) {
				map.put(temp[i],rank);
				rank++;
			}
		}
		
		for(int i = 0; i<n; i++) {
			System.out.print(map.get(nums[i]));
			if(i<n-1) System.out.print(" ");
		}
		
	}

}

Java(2022.01.28) (3)

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);
		
		int rank = 0;
		for(int i = 0; i<n; i++) {
			if(!map.containsKey(temp[i])) {
				map.put(temp[i],rank);
				rank++;
			}
		}
		
		for(int i = 0; i<n; i++) {
			System.out.print(map.get(nums[i]));
			if(i<n-1) System.out.print(" ");
		}
		
	}

}