728x90
▣ 입력설명
임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요.
▣ 입력설명
- 첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
▣ 출력설명
- 첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
▣ 입력설명
8 32 23 87 65 12 57 32 99 81 |
▣ 입력설명
3 |
<내 코드>
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
int main() {
int N, M;
int i, j, temp;
scanf("%d %d", &N, &M);
int* arr = malloc(sizeof(int) * N);
for (i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
//버블 정렬
for (i = 0; i < N; i++) {
for (j = 0; j < i; j++) {
if (arr[i] < arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
int inx = N / 2;
int answer=-1;
while (inx != 0 || inx > N) {
if (arr[inx] == M) {
answer = inx + 1;
break;
}
else if (arr[inx] > M) inx = inx / 2;
else inx = inx + inx / 2;
}
printf("%d", answer);
return 0;
}
<전상일씨 코드>
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
int compare(const void* n1, const void* n2) {
if (*(int*)n1 > * (int*)n2)
return 1;
else if (*(int*)n1 < *(int*)n2)
return -1;
else return 0;
}
int num[1000000];
int main() {
int lt = 0, rt, mid;
int n, m, i, j;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%d", &num[i]);
}
rt = n - 1;
qsort(num, n, sizeof(int), compare);
while (1) {
mid = (rt + lt) / 2;
if (num[mid] == m) break;
else if (num[mid] < m) {
lt = mid + 1;
}
else
rt = mid - 1;
}
printf("%d\n", mid + 1);
return 0;
}
qsort라는 퀵 정렬함수를 사용한걸 볼 수 있다.
rt와 lt를 사용해서 코드를 작성했다.
728x90
반응형
'Algorithm' 카테고리의 다른 글
부분집합(MS 인터뷰, DFS:완전탐색) (0) | 2021.02.05 |
---|---|
영지 선택(2차원 배열 구간합, DP) (0) | 2021.02.03 |
[개념] 정렬 알고리즘 (0) | 2021.01.25 |
[개념] 탐색(검색) 알고리즘 (0) | 2021.01.25 |
N!에서 0의 개수 (0) | 2021.01.22 |