9642 - Omar’s Bug

문제 번역

Omar는 다음 이분탐색 코드를 만들었습니다.

int findFirstGreaterThanOrEqual(int array[], int N, int X) {
    int start = 0, end = N;
    while (start < end) {
        int middle = (start + end) / 2;
        if (array[middle] > X) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }
    return start;
}

 

파라미터는 다음 조건을 만족합니다.

1. $array$는 1개 이상 99개 이하의 수가 들어있습니다.
2. $array$의 모든 숫자는 서로 다르고 오름차순입니다.
3. $array$에 있는 수는 최대 100입니다.
4. $N$은 $array$의 크기입니다.
5. $X$는 최대 100입니다.

만약 $X$보다 크거나 같은 값이 $array$에 있다면 그 중 가장 작은 값의 인덱스를 리턴해야 합니다. 만약 그런 값이 없다면 $N$을 리턴해야 합니다. 

 

하지만 해당 코드는 의도대로 동작하지 않습니다. $N, X, Y$가 주어졌을 때 $Y$가 1이면 해당 코드가 의도대로 동작하는 $array$를, 2면 의도대로 동작하지 않는 $array$를 출력하세요. 그러한 $array$가 여러개면 사전순으로 가장 빠른 $array$를 출력하세요.

step 1

만약 $array$에 $X$가 없다면 해당 코드는 의도대로 동작합니다.

만약 $array$에 $X$가 있다면 해당 코드는 의도대로 동작하지 않습니다.

• $array[middle]$이 $X$면 $start = middle + 1$이고 $X$가 범위 밖으로 나가게 됩니다.
• $end$는 항상 $X$의 인덱스보다 큽니다. 즉, 위의 경우가 반드시 발생하게 됩니다.

step 2

$array = [1, 2, ..., N]$로 준비합니다. 만약 $Y$가 1인데 $X$가 $array$안에 있다면 $X$부터 그 이후의 값에 1을 더해줍니다. 만약 $Y$가 2인데 $X$가 $array$안에 없다면 마지막 값을 $X$로 바꿔줍니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
int b[200];
int find(int x, int y) {
    int start = 0, end = x;
    while (start < end) {
        int middle = (start + end) / 2;
        if (b[middle] > y) {
            end = middle;
        }
        else {
            start = middle + 1;
        }
    }
    return start;
}
int main() {
    int t, x, y, z, i;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &x, &y, &z);
        for (i = 0;i < x;i++) b[i] = i + 1;
        int t = find(x,y);
        for (i = 0;i < x;i++) {
            if (b[i] >= y) break;
        }
        if (t == i && z == 1 || t != i && z == 2) {
            for (i = 0;i < x;i++) printf("%d ", b[i]);
            printf("\n");
            continue;
        }
        if (z == 1) {
            int cnt = 0;
            for (i = 0;i < x;i++) {
                if (b[i] == y) cnt = 1;
                printf("%d ", b[i] + cnt);
            }
            printf("\n");
            continue;
        }
        else {
            for (i = 0;i < x-1;i++) {
                printf("%d ", b[i]);
            }
            printf("%d ", y);
            printf("\n");
        }
    }
    return 0;
}