[백준] 18870번 좌표압축 (이분탐색_JAVA)

풀어야지 풀어야지 하다가

드디어 푼 이분탐색 문제!

 

---

문제

 

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 이분탐색

 

일단 문제는 중복 제거와 정렬이다.

배열을 2개 만든 후 하나는 set으로 중복 제거를 해준다. 그 후 정렬을 한 뒤, 중복제거를 하지 않은 배열을 반복문으로 돌면서 정렬된 배열의 인덱스를 출력하는 방식으로 풀었다.

 

정리하자면, set과 정렬 그리고 이분탐색으로 풀었다.

 

 

풀이 과정

 1.

배열 크기인 n을 입력받고, 배열 arr을 생성 후 배열 값을 입력받는다.

 

2.

중복제거를 위해 set을 생성 후, arr값 하나씩 set에 저장한다.

 

3.

set의 크기는 중복이 제거된 arr크기이므로 새로운 배열 arr2를 set의 크기만큼 생성한다.

그 후 set에서 값을 하나씩 꺼내서 arr2에 저장한다. 그 배열을 Arrays.sort로 정렬한다.

 

4.

정답 출력을 위해 StringBuilder를 생성한다.

배열 arr을 처음부터 반복문을 돌면서 현재 arr의 값을 arr2에서 어떤 인덱스에 있는지 찾는다.

 

5.

이분탐색을 시작한다.

start는 0, end는 arr2배열의 개수로 둔다. strat가 end보다 작다면, 이분탐색을 계속 반복한다.

mid는 (start+end)/2로 두고. arr2[mid]와 내가 찾고자 하는 arr배열의 값과 비교한다.

만약 찾고자 하는 target보다 arr[mid]가 크다면 end값을 mid-1로 변경한다. 만약 arr[mid]가 작다면 start값을 mid+1로 변경한다.

만약 arr2[mid]값과 내가 찾고자 하는 값이 같다면, mid가 정렬된 배열의 인덱스이므로 출력해야하는 수가 된다. 그러므로 StringBuilder에 저장한다.

 

6.

모든 반복문이 끝난 후 StringBuilder을 출력한다.

 

 

---

코드

 

import java.util.*;

public class Test_18870_좌표압축 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		
		//중복제거
		Set<Integer> set = new HashSet();
		for(int i=0; i<n; i++) {
			set.add(arr[i]);
		}
		
		int[] arr2 = new int[set.size()];
		int idx = 0;
		
		Iterator<Integer> iter = set.iterator();
		while(iter.hasNext()) {
			arr2[idx++] = iter.next();
		}
		
		//정렬
		Arrays.sort(arr2);
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<arr.length; i++) {
			int num = arr[i];	//찾아야 하는 수
			
			int start = 0;
			int end = arr2.length-1;
			
			while(start<=end) {	//이분탐색
				int mid = (start+end)/2;
				
				if(num<arr2[mid])end = mid-1;
				else if(num>arr2[mid]) start=mid+1; 
				else {
					sb.append(mid + " ");
					break;
				}
			}
		}
		
		//출력
		System.out.println(sb.toString());
	}
}

 

 

(❁´◡`❁)

끝!