[Java] 백준 - 20551번 : Sort 마스터 배지훈의 후계자 (Silver IV)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	X
본인의 실력으로 풀었는가?	O

 

20551번: Sort 마스터 배지훈의 후계자

 

 

 

 

 

 

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
    	//입출력 객체들 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        
       	//가장 첫 번째 줄은 배열의 길이와 질문의 개수가 나옴
        //띄어쓰기로 구분되어 있기 때문에
        //읽어 들이면서 split()으로 구분
		String[] nm = br.readLine().split(" ");
		
        //첫 번째 줄 숫자로 변환
		int n = Integer.parseInt(nm[0]);
		int m = Integer.parseInt(nm[1]);
		
        //배열 a 선언
		int[] a = new int[n];
        
        //입력 순서대로 정수로 변환하면서 배열 채우기
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(br.readLine());
		}
		
        //퀵 정렬 호출
		quick(a, 0, a.length-1);
		
		for (int i = 0; i < m; i++) {
			bw.write(check(Integer.parseInt(br.readLine()), a, 0, a.length-1) + "\n");
		}
		
		bw.flush();
		bw.close();
	}
	
	public static int check(int num, int[] a, int start, int end) {
		while (start+1 < end) {
			int mid = (start + end) / 2;
			
			if (a[mid] >= num) {
				end = mid;
			} else {
				start = mid;
			}
		}
		
		return a[start] == num ? start : a[end] == num ? end : -1;
	}
	
    //퀵 정렬 함수
	public static void quick(int[] a, int start, int end) {
    	//cutting 함수 호출 - 리턴값 정수
		int cut = cutting(a, start, end);
        
        
		if (start < cut-1) quick(a, start, cut-1);
		if (cut < end) quick(a, cut, end);
	}
	
	public static int cutting(int[] a, int start, int end) {
    	//중간 위치와 중간 위치의 값인 피벗 선언하기
		int mid = (start + end) / 2;
		int pivot = a[mid];
		
        //start가 end보다 작거나 같을 때까지 반복
		while (start <= end) {
        	//start위치의 값이 피벗보다 큰 경우까지 탐색
			while (a[start] < pivot) start++;
            
            //end위치의 값이 피벗보다 작은 경우까지 탐색
			while (a[end] > pivot) end--;
			
            //만약 start가 end보다 작거나 같으면 두 위치의 숫자 바꾸기
            //그리고 그 다음 위치로 각각 이동
			if (start <= end) {
				change(a, start, end);
				start++;
				end--;
			}
		}
		
		return start;
	}
	
    //두 위치 간의 숫자 바꾸는 함수
    public static void change(int[] a, int n1, int n2) {
		int temp = a[n1];
		a[n1] = a[n2];
		a[n2] = temp;
	}
}

 

문제	결과	메모리	시간	코드 길이
20551	맞았습니다!!	53696 KB	716 ms	1530 B