[이것이 코딩테스트다] 6. 탐색 - 순차 탐색, 이진 탐색

이것이 취업을 위한 코딩테스트다.

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

 

순차 탐색(Sequential Search)

- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에 있는 데이터를 하나씩 확인하는 방법

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.print("문자열 갯수와 찾을 문자열을 입력 : ");
		Scanner sc = new Scanner(System.in);
		String temp = sc.nextLine();
		
		// 문자열 갯수 
		int N = Integer.parseInt(temp.split(" ")[0]);
		
		// 찾을 문자열 
		String target = temp.split(" ")[1];
		
		String[] strArr = new String[N];
		
		temp=sc.nextLine();
		for(int i=0;i<strArr.length;i++) {
			strArr[i] = temp.split(" ")[i];
		}
		
		sequential_search(strArr, N, target);
	}
	
	static void sequential_search(String[] strArr, int N, String target) {
		int index = -1;
		
		// 반복문을 돌며 탐색 
		for(int i=0; i<N; i++) {
			// 타겟과 같은 걸 찾으면 탈출 
			if(strArr[i].equals(target)) {
				index = i;
				break;
			}
		}
		
		if(index == -1) {
			System.out.println("찾지 못함!");
		}else {
			System.out.println(target + " 의 index : " + index);
		}
	}

}

문자열 갯수와 찾을 문자열을 입력 : 5 search greedy dfs bfs sorting search search 의 index : 4

 

 

이진 탐색(Binary Search) 

- 배열 내부의 데이터가 정렬되어 있어야 이진 탐색이 가능하다.

- 이진탐색은 위치를 나타내는 변수 3개를 사용하는데 시작점, 끝점, 중간점이다.

- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하며 탐색한다.

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String temp = sc.nextLine();
		
		// 문자열 갯수 
		int N = Integer.parseInt(temp.split(" ")[0]);
		
		// 찾을 숫자
		int target = Integer.parseInt(temp.split(" ")[1]);
		
		int[] intArr = new int[N];
		
		temp=sc.nextLine();
		for(int i=0;i<intArr.length;i++) {
			intArr[i] = Integer.parseInt(temp.split(" ")[i]);
		}
		
		// 정렬 
		Arrays.sort(intArr);
		
		int result = binary_search(intArr, 0, N-1, target);
		
		if(result == -1) {
			System.out.println("찾지 못함!");
		}else {
			System.out.println(target +" 의 index : " + result);
		}
	}

	static int binary_search(int[] arr, int start, int end, int target) {
		// 범위를 벗어난 경우 찾지못한걸로 간주하고 종
		if(start>end) {
			return -1;
		}
		
		// 몫만 추출 
		int mid = (start+end) / 2;
		
		// 중간점 위치의 데이터와 타겟이 같으면 중간점 반환 
		if(arr[mid] == target) {
			return mid;
		}
		// 중간점 위치의 데이터보다 타겟이 작으면 중간점 기준 왼쪽 탐색 
		else if(arr[mid] > target) {
			return binary_search(arr, start, mid-1, target);
		}
		// 중간점 위치의 데이터보다 타겟이 크면 중간점 기준 오른쪽 탐색 
		else {
			return binary_search(arr, mid+1, end, target);
		}
	}
}

10 7 1 2 3 4 5 6 7 8 9 10 7 의 index : 6

 

 

실전 문제

1. 부품 찾기

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[] myPartArr = new int[N];
		
		// 가게의 부품 배열에 부품 번호들 기록
		String temp = br.readLine();
		StringTokenizer st = new StringTokenizer(temp);
		
		for(int i=0;i<N;i++) {
			myPartArr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 손님이 요청한 부품 입력 받기
		int M = Integer.parseInt(br.readLine());
		
		// 손님이 요청한 부품 갯수만큼 크기 할당
		int[] needPartArr = new int[M];
		
		// 손님이 요청한 부품 배열에 부품 번호들 기록
		temp = br.readLine();
		st = new StringTokenizer(temp);
		
		for(int i=0;i<M;i++) {
			needPartArr[i] = Integer.parseInt(st.nextToken());
		}
		
		br.close();
		
		// 결과를 저장할 변수
		String[] result = new String[M];
		
		// 이진탐색을 이용하여 해결
		for(int i=0;i<M;i++) {
			int num = binary_search(myPartArr, 0, myPartArr.length-1, needPartArr[i]);
			
			if(num == -1) {
				result[i] = "no";
			}else {
				result[i] = "yes";
			}
		}
		
		for(int i=0;i<M;i++) {
			System.out.print(result[i]+" ");
		}
		
	}
	
	// 이진 탐색
	static int binary_search(int[] arr, int start, int end, int target) {
		if(start > end) {
			return -1;
		}
		
		int mid = (start+end) / 2;
		
		if(arr[mid] == target) {
			return mid;
		}
		else if(arr[mid] > target) {
			return binary_search(arr, start, mid-1, target);
		}
		else {
			return binary_search(arr, mid+1, end, target);
		}
	}

}

 

 

2. 떡볶이 떡 만들기

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,M;
		int[] arr;
		
		String temp = br.readLine();
		StringTokenizer st = new StringTokenizer(temp);
		
		// 떡의 개수
		N = Integer.parseInt(st.nextToken());
		
		// 손님이 요청한 길이
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		
		temp = br.readLine();
		st = new StringTokenizer(temp);
		
		// 떡의 가장 큰 길이
		int max = 0;
		
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(max < arr[i]) {
				max = arr[i];
			}
		}
		
		// 절단기의 최대 높이 = 떡의 최대 길이
		// 이진탐색을 통해 적절한 절단기의 높이를 찾는다.
		int result = binary_search(arr, 0, max, M );
		
		System.out.print(result);
	}
	
	static int binary_search(int[] arr, int start, int end, int target) {
		if(start>end) {
			return -1;
		}
		
		int mid = (start+end) / 2;
		int sum = 0;
		
		for(int i=0; i<arr.length;i++) {
			if(arr[i]>mid) {
				sum+= (arr[i]-mid);
			}
		}
		
		if(sum==target) {
			return mid;
		}
		else if(sum>target) {
			return binary_search(arr, mid+1, end, target);
		}
		else {
			return binary_search(arr, start, mid-1, target);
			
		}
	}

}