백준알고리즘:p18870 좌표압축

분류: 정렬

 

▶문제

입력받은 숫자의 순위를 정해서, 입력받은 순서대로 순위를 나타내면 된다. 

 

 

▶통과 못한 코드_시간초과

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
package sort;

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

public class p18870 {
//좌표정렬_시간초과
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		String[] temp = br.readLine().split(" ");
		int[] arr = new int[n];
		ArrayList<Integer> list = new ArrayList<>();
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(temp[i]);
			
			//중복제거 하면서 list에 넣기-순위용
			if(!list.contains(arr[i])) {
				list.add(arr[i]);
			}
		}
	
		Collections.sort(list); //순위정렬
		//arr값과 같은 list의 인덱스값 출력
		StringBuilder sb = new StringBuilder();
		for(int k=0; k<n; k++) {
			sb.append(Collections.binarySearch(list, arr[k])+" ");//이진탐색
		}System.out.println(sb);
	}

}

 

list에서 값을 찾는게 시간이 오래걸려서 그런것 같다. 

그래서 차라리 새 list를 만드는 것이 나을 것

 

▶통과한 코드_int[]+map

package sort;

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

public class p18870_1 {
//백준_성공 2308ms
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		String[] temp = br.readLine().split(" ");
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(temp[i]);
	}
		int[] sortNums = arr.clone();//정렬용 하나 더 만들기
		Arrays.sort(sortNums);
		
		HashMap<Integer, Integer> map = new HashMap<>();
		int index=0;
		for(int x: sortNums) {
			if(!map.containsKey(x)) {
				map.put(x, index);//(숫자, 순위)
				index++;
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++) {
			sb.append(map.get(arr[i])+" ");
		}System.out.print(sb);
	}
}

▶풀이방식

arr는 입력받은 순서를 유지하는 용도

sortNums는 map에 숫자-순위를 저장하기 위한 배열로 arr값을 복사해서 정렬한다. 

map에 중복이 안되도록 확인하면서 (sortNums을 통해) 숫자와 순위를 저장한다. 

arr[i] 와 일치하는 map의 value를 차례로 출력한다.

 

---

채점결과

 

링크 www.acmicpc.net/problem/18870

18870번: 좌표 압축

---

참고한 블로그들

girawhale.tistory.com/38

hoho325.tistory.com/243

binarysearch이진탐색 쓰진 않았지만 일단..

blog.naver.com/5550304/222180523027