2531번 회전초밥 (조건변경으로 난이도 업)

위에 문제의 조건에서 초밥의 가짓수 d를 억 단위로 조건을 줄경우 어떻게 풀어야 할까?

  2<= d <= 3000 일때는 인덱스에다 그냥 떄려 박아서 풀었다. 

하지만 억단위로 넘어갈 경우 인덱스를 쓸수 없다.

그래서 직접만든 sort함수로 같은 종류의 반복되는 초밥을 제거 한다음 오름차순으로 바꿔준다.

그리고 오름차순이기 때문에 이분탐색이 가능하므로 시간복잡도를 줄일수 있다.

ex) 입력

8 300000000 4 300000000

70000000 

90000000 

70000000 

300000000 

20000000 

70000000 

90000000 

250000000

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

#define A 3001

int fish[10 * A], max = 1, realMax;           

int count;

int sort_fish[10 * A], N, d, k, c;

int real_sort_fish[10 * A];

int binary_search_fish[10 * A];

void sort() // 일단 sort_fish[]에 입력받은  fish[]를 반복되면서 오름차순으로 바꾼다.  

{

for (int i = 1; i <= N; i++)

{

for (int j = i + 1; j <= N; j++)

{

if (sort_fish[i] > sort_fish[j])

{

int temp = sort_fish[j];

sort_fish[j] = sort_fish[i];

sort_fish[i] = temp;

}

}

}

for (int i = 1; i <= N; i++)                        // 요것은 sort_fish[]는 오름차순이지만 반복되는것이 있기때문에

{                                                        //  real_sort_fish[]에 반복 되는것을 제거해줬다.

if (real_sort_fish[count] != sort_fish[i])

{

count++;

real_sort_fish[count] = sort_fish[i];

}

}

}

int binary_search(int b) // b는 찾고자 하는 수이고  이분탐색을 이용해 본래 푼 방법의 log N만큼만 시간복잡도를 곱해주는 꼴

{

int left = 1, right = count,mid;

while (1)

{

mid = (left + right) / 2;

if (real_sort_fish[mid] > b)

right = mid;

else

left = mid;

if (real_sort_fish[mid] == b)

{

return mid;

}

if (real_sort_fish[left] == b)

return left;

if (real_sort_fish[right] == b)

return right;

}

}

int main()

{

// N : 회전 초밥 벨트에 놓인 접시의 수    d : 초밥의 가짓수

scanf("%d %d %d %d", &N, &d, &k, &c); // k : 연속해서 먹는 접시의 수    c : 쿠폰 번호 (서비스)

for (int i = 1; i <= N; i++)

{

scanf("%d", &fish[i]);

sort_fish[i] = fish[i];

}

sort(); // real_sort_fish[] 배열을 만듬. <-- 오름차순으로 중복안되게 fish들을 정리해둔것.

int service = binary_search(c);            // 서비스는 어차피 받으므로 무조건 넣어둔다.

binary_search_fish[service]++;            // binary_search_fish[]에는 먹은 초밥들에 대해 저장하는 배열

for (int i = 1; i <= k; i++)                //  첫번째 접시부터 연속되게 먹을수 있는 접시들을 처음에 미리 넣어둔다.

{

int u = binary_search(fish[i]);

binary_search_fish[u]++;

if (binary_search_fish[u] == 1)

max += 1;

}

for (int i = 1; i <= N - 1; i++)                 // 저 위에 문제대로 연속해서 먹는 접시의 수가 4면 일단 위에서 1,2,3,4의 접시는 먹었고 인덱스에 저장됨

{                                                     // 그래서 2,3,4,5로 변경을 해야하는데 이때 인덱스에 1번째 접시를 인덱스에서 빼고 5번째 접시를 인덱스

if (i + k <= N)                           // 에 더하면 됨 .. 요렇게 접시 끝까지 ㄱㄱ 하는데 if문 두개 나눈이유는 작은 test case를 해보면 알겠지만

{                                            //  fish[] 배열을 넘어버리기 때문에 나눠줘야함 ..  해보면 알음 

int u = binary_search(fish[i]);

binary_search_fish[u]--;

if (binary_search_fish[u] == 0)            // 초밥이 빠져나가는 상황에서 만약 0으로 된다면 max값을 -1 한다 (꼬리쪽은 하나씩 없어짐)

max -= 1;

u = binary_search(fish[i + k]);

binary_search_fish[u]++;

if (binary_search_fish[u] == 1)            // 초밥이 더해지는 상황에서 만약 1로 된다면 max값을 +1한다 . (만약 2가된다해도  똑같은

max += 1;                                                                                                                    종류의 초밥은 취급 x)

}

else

{

int t = i + k - N;

int u = binary_search(fish[i]);

binary_search_fish[u]--;

if (binary_search_fish[u] == 0)

max -= 1;

u = binary_search(fish[t]);

binary_search_fish[u]++;

if (binary_search_fish[u] == 1)

max += 1;

}

if (realMax < max)

realMax = max;

}

printf("%d", realMax);

return 0;

}

원래 문제의 입력에서 초밥의 종류들에 한해 곱하기 천만을 한거임 . 그러므로 결과는 같아야한다.