📝 문제
백준 - 20551번: Sort 마스터 배지훈의 후계자 (Silver IV)
📝 답안
📌 작성 코드
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;
}
}📌 결과
📌 quick 함수 설명
✔ 테스트케이스 1번일 때 첫 호출인 quick(a, 0, 4)일 때 cutting(a, 0, 4) 실행 과정
a 배열 : [ 9, 0, -1, 3, 2]
start = 0
end = 4
mid = (0 + 4) / 2 = 2
pivot = -1
=> start <= end이기 때문에 while문 실행
start : 0 → a[0] = 9 > -1
end : 4 → a[4] = 2 > -1
end : 3 → a[3] = 3 > -1
end : 2 → a[2] = -1 = -1
만약 start가 end보다 작거나 같으면 두 위치의 숫자 자리 바꾸기
=> start = 0, end = 2이기 때문에 자리 변동 있음
a 배열 : [-1, 0, 9, 3, 2]
return 값 : 0
✔ cutting() 함수 이후 quick() 함수를 다시 호출하므로써 배열이 정렬될 때까지 반복
cut = 0
start = 0
end = 4
=> start < (0-1) 가 false이기 때문에 첫 번째 if문은 넘어감
=> 0 < end 가 true이기 때문에 quick(a, 0, 4) 함수 호출
이 때 처음 호출된 quick(a, 0, 4)와 동일하게 호출되나 배열이 조금 변경됬기 때문에 다른 결과 값이 나옴
📌 check 함수 설명
✔ 정렬 후 위치 리턴하는 check 함수. 첫 실행인 check(-1, a, 0, 4) 실행 과정
a 배열 : [-1, 0, 2, 3, 9]
num = -1 (위치를 찾을 숫자)
start = 0
end = 4
=> start + 1 < end 가 true이기 때문에 while문 실행
mid = (0 + 4) / 2 = 2
pivot = a[2] = 2
=> pivot과 num을 비교하여 pivot이 num보다 클 경우 end를 변경하고, 작거나 같을 경우 start를 변경
2 > -1 이기 때문에 start = 0, end = 2
pivot과 num 비교를 반복하여 start와 end의 위치가 마주하는 위치까지 반복
위의 경우에는 start = 0, end = 1이 되었을 경우 while문이 멈춤
return값은 만약 start나 end 위치의 숫자 중 num이 있을 경우 해당 위치 값을 리턴하고, 그렇지 않으면 -1 리턴
📌 주의해야할 사항
Arrays.sort와 indexOf를 활용할 경우 시간 초과로 문제를 풀 수 없음
