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

분노의 시간초과 문제...

결과는 계속 맞는데 시간초과때문에 미치게 만든 문제였다.
무수한 시간초과의 수집 우하하

일단 문제를 푸는 기본 구조는,

1. arr에 x좌표를 입력받는다.
2. arr을 똑같이 복사한 sort를 만들고 sort를 정렬한다.
3. arr에서 x좌표 순서대로 sort에서의 해당 좌표의 인덱스를 출력한다.

• 처음에는 Collections.sort로 리스트 정렬을 했다. 리스트에서 해당 값을 가지는 요소의 인덱스를 출력했는데 결과는 맞게 나오지만 시간초과가 계속 떴다..
• 선택정렬도 해봤는데 역시나 시간초과 ㅎㅎ
• 인터넷에서 HashMap을 사용해야한다는 힌트를 얻었다. HashMap 이용해서 출력했는데 또 시간초과..?
• StringBuilder까지 사용했더니 드디어 성공

StringBuilder를 처음에 리스트정렬, 선택정렬과 사용했다가 시간초과가 뜨길래 아, 이게 문제가 아닌가 했지만 HashMap 사용했을 때는 얘가 문제가 됐다. 자바 너 자꾸 그럴래?

🔑 실패했던 java 풀이1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		ArrayList<Integer> point=new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for(int i=0; i<N; i++){
			point.add(Integer.parseInt(st.nextToken()));
		}
		
		ArrayList<Integer> list=new ArrayList<>(point);
		ArrayList<Integer> result=new ArrayList<>();
		Collections.sort(list);
		
		for(Integer i: list) {
			if(!(result.contains(i))) 
				result.add(i);
		}

		for(int i=0; i<N; i++)
			sb.append(result.indexOf(point.get(i))+" ");
		System.out.print(sb);
	}
}

🔑 실패했던 java 풀이2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb= new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		
		int point[]=new int[N];
		ArrayList<Integer> list=new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		for(int i=0; i<N; i++){
			point[i]=Integer.parseInt(st.nextToken());
			if(!list.contains(point[i]))
				list.add(point[i]);
		}
		
		Collections.sort(list);

		for(int i=0; i<N; i++) {
			for(int j=0; j<list.size(); j++) {
				if(point[i]==list.get(j))
					sb.append(j+" ");
			}
		}
		System.out.print(sb);
		
	}
}

🔑 java 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		
		int arr[]=new int[N];
		int sort[]=new int[N];
		HashMap<Integer,Integer> map = new HashMap<>();
		StringTokenizer st= new StringTokenizer(br.readLine()," ");
		
		for(int i=0; i<N; i++) 
			arr[i]=Integer.parseInt(st.nextToken());
		sort = arr.clone();
		Arrays.sort(sort);
		int index=0;
		for(int i=0; i<N; i++) {
			if(!map.containsKey(sort[i]))
				map.put(sort[i], index++);
		}
		for(int i=0; i<N; i++)
			sb.append(map.get(arr[i])+" ");
		System.out.print(sb);
		br.close();
	    
	}
}

아 힘들어