/*
#include <stdio.h>
int a[100005]= {};
void s(int l, int r)
{
int temp=a[l];
a[l]=a[r];
a[r]=temp;
}
int p(int l, int r)
{
int piv = (l+r)/2;
printf("p piv %d\n", a[piv]);
printf("sort p1 data: ");
for(int i=l; i<=r; i++)
{
printf("%d ", a[i]);
}
printf("\n");
while(l < r)
{
while(a[l]<a[piv] && l<r)
{
//s(l, r);
l++;
}
while(a[r]>a[piv] && l<r)
{
//s(l, r);
r--;
}
printf("pick %d %d\n", l, r);
if(l<r)
{
s(l, r);
if(l==piv)
{
piv=r;
}
}
}
return piv;
}
void q(int l, int r)
{
printf("sort q data: ");
for(int i=0; i<5; i++)
{
printf("%d ", a[i]);
}
printf("\n");
if(l<r)
{
int piv=p(l, r);
q(l, piv-1);
q(piv+1, r);
}
}
void main()
{
int n, i;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
q(0, n-1);
for(i=0; i<n; i++)
{
printf("%d ", a[i]);
}
}
*/
/*
#include <stdio.h>
int a[100005]= {};
//5
//1
//4
//5
//8
//2
void s(int l, int r)
{
int t=a[l];
a[l]=a[r];
a[r]=t;
}
int p(int b, int e)
{
int pivot=(b+e)/2;
int l=b;
int r=e;
for( ; l<r; )
{
for( ; a[l]<a[pivot]&&l<r; )
l++;
while(a[r]>a[pivot]&&l<r)
r--;
if(l<r)
{
s(l,r);
if(l==pivot)
pivot=r;
}
}
s(pivot,r);
return r;
}
void q(int l, int r)
{
int piv;
if(l<r)
{
piv=p(l,r);
q(l, piv-1);
q(piv+1, r);
}
}
void main()
{
int i, n;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
q(0, n-1);
for(i=0; i<n; i++)
{
printf("%d\n", a[i]);
}
}
*/
/*
#include <stdio.h>
int a[100005]= {};
int main()
{
int n, i, j, k;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &k);
a[k]++;
}
for(j=0; j<=100000; j++)
{
for(i=0; i<a[j]; i++)
{
printf("%d ", j);
}
}
}
*/
/*4421
#include <stdio.h>
int a[30][30]= {};
int q[1000]= {};
int t, z=0;
int s()
{
int i, j, temp;
for(i=0; i<t; i++)
{
for(j=0; j<t-1; j++)
{
if(q[j]>q[j+1]) {
temp=q[j+1];
q[j+1]=q[j];
q[j]=temp;
}
}
}
printf("%d\n", t);
for(j=0; j<t; j++)
{
printf("%d\n", q[j]);
}
}
void k(int i, int j)
{
z++;
a[i][j] = 0;
if(a[i-1][j]==1)
{
//a[i-1][j]=0;
k(i-1, j);
}
if(a[i+1][j]==1)
{
//a[i+1][j]=0;
k(i+1, j);
}
if(a[i][j+1]==1)
{
//a[i][j+1]=0;
k(i, j+1);
}
if(a[i][j-1]==1)
{
//a[i][j-1]=0;
k(i, j-1);
}
//s(t, q[z]);
}
int main()
{
int n, i, j;
scanf("%d", &n);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%1d", &a[i][j]);
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(a[i][j]==1)
{
z = 0;
k(i, j);
q[t++]=z;
}
}
}
s();
return 0;
}
*/
/*
#include <stdio.h>
char a[105][105]= {};
int t=0;
void s(int i, int j)
{
int x, y;
a[i][j]='.';
for(x=i-1; x<=i+1; x++)
{
for(y=j-1; y<=j+1; y++)
{
if(a[x][y]=='L')
{
s(x, y);
}
}
}
}
int main()
{
int w, i, j, h;
int x, y;
scanf("%d %d", &w, &h);
for(i=1; i<=h; i++)
{
for(j=1; j<=w; j++)
{
scanf(" %c", &a[i][j]);
}
}
for(i=1; i<=h; i++)
{
for(j=1; j<=w; j++)
{
if(a[i][j]=='L')
{
s(i, j);
t++;
}
}
}
printf("%d", t);
}
*/
2605 4023 4503 4697
프로그래머스 1