/*
strcmp
string compare
strcmp(문자열1, 문자열2) == 0 완전히 같은 단어인지?
strcmp("abcd", "zzzz") < 0 사전식 순서대로 있는지
strcmp("zzzz", "abcd") > 0 사전식 반대순서로 있는지?
#include<stdio.h>
#include<string.h>
typedef struct
{
char sche[100];
int date;
}memo;
memo arr[101]={}, temp;
int main()
{
int n, i, j, min, y, m, d;
scanf("%d\n", &n);
for(i=1; i<=n; i++){
scanf ("%s %d %d %d", arr[i].sche, &y, &m, &d);
arr[i].date+=(y*10000);
arr[i].date+=(m*100);
arr[i].date+=d;
}
for (i=1; i<n; i++){
min=i;
for (j=i+1; j<=n; j++){
if (arr[min].date>arr[j].date){
min=j;
}
else if(arr[min].date==arr[j].date){
if(strcmp(arr[min].sche, arr[j].sche)>0){
min=j;
}
}
}
temp=arr[min];
arr[min]=arr[i];
arr[i]=temp;
}
for(i=1; i<=n; i++){
printf ("%s\n", arr[i].sche);
}
return 0;
}
3014 : 정렬을 빠르게!
- 기존 버블, 선택, 삽입 같은 정렬 사용 x
- 메모이제이션 이용 ( arr[i] : i가 몇 개 있는지?)
데이터 값의 범위가 있는 것 -> 혹시 메모이제이션???
arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] ...
0 0 1 0 1 0 2 0 1
#include<stdio.h>
int main()
{
int n, i, j, max, t;
int arr[100001]={};
scanf ("%d", &n);
for (i=0; i<n; i++){
scanf("%d", &t);
arr[t]++;
}
for(i=0; i<=100000; i++){
// i를 arr[i]번 출력
for(j=arr[i];j>0 ; j--){
printf ("%d ", i);
}
}
return 0;
}
이(등)분 탐색 = 이진 탐색 = binary search
"정렬이 되어있을때만!!"
반씩 잘라가면서 원하는 숫자의 위치 찾아가기
#include<stdio.h>
int a[5000]={};
int bs(int s, int e, int k) // a[s] ~ a[e] 에서 k값의 위치 리턴 , 없으면 -1리턴
{
int mid = (s+e)/2;
if(s>e) return -1; // 못찾았으면
if(a[mid]==k) return mid;
else if(a[mid]<k) return bs(mid+1,e,k);
else
}
int main()
{
for(int i=0;i<50;i++)
a[i]=i;
printf("%d",bs(0,49,30));
}*/
#include<stdio.h>
int a[1000001]={};
int bs(int s, int e, int k)
{
int mid=(s+e)/2;
if (s>e){
return -1;
}
if (a[mid]==k){
return mid+1;
}
else if (a[mid]<k){
return bs(mid+1, e, k);
}
else{
return bs(s, mid, k);
}
}
int main()
{
int n, m, i;
int num[100001]={};
scanf ("%d", &n);
for (i=0; i<n; i++){
scanf("%d",&a[i]);
}
scanf("%d", &m);
for(i=0; i<m; i++){
scanf("%d", &num[i]);
}
for(i=0; i<m; i++){
printf ("%d", bs(0, m, num[i]));
}
return 0;
}