글 읽기 - 이 방법으로는 안되는건가요?ㅠㅠ

dufdlf000 3년 전 0

lower_bound , upper_bound를 써야한다는데 이 방법으로 하면 안되는건가요? 아니면 제 코드에 문제가 있는건가요? ㅠㅠ 도움 부탁드립니다.

#include <iostream>

using namespace std;

int partition(int array[], int left, int right);

void quickSort(int left, int right, int array[]);

int searchArray(int array[], int target, int left, int right);

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    int N, tempNum, M, cnt = 0, arrayCnt = 0;
    cin >> N;
    int array[N], array2[N], countArray[N];
    for (int i = 0; i < N; i++) {
        cin >> array[i];
    }
    quickSort(0, N - 1, array);
    tempNum = array[0];
    for (int i = 1; i < N; i++) {
        if (tempNum == array[i]) {
            cnt++;
        } else {
            cnt++;
            array2[arrayCnt] = tempNum;
            countArray[arrayCnt++] = cnt;
            tempNum = array[i];
            cnt = 0;
        }
    }
    cnt++;
    array2[arrayCnt] = tempNum;
    countArray[arrayCnt] = cnt;
    cin >> M;
    int curArray[M];
    for (int i = 0; i < M; i++) {
        cin >> curArray[i];
        int temp = searchArray(array2, curArray[i], 0, M - 1);
        if (temp != -1) {
            cout << countArray[temp] << " ";
        } else {
            cout << 0 << " ";
        }
    }
    return 0;
}
int searchArray(int array[], int target, int left, int right) {
    int mid = (left + right) / 2;
    if (left > right) {
        return -1;
    }
    if (array[mid] == target) {
        return mid;
    } else if (target < array[mid]) {
        return searchArray(array, target, left, mid - 1);
    } else {
        return searchArray(array, target, mid + 1, right);
    }
}

int partition(int array[], int left, int right) {
    int low = left;
    int high = right + 1;
    int pivot = array[left];
    do {
        do {
            low++;
        } while (low <= right && pivot > array[low]);
        do {
            high--;
        } while (high >= left && pivot < array[high]);
        if (low < high) {
            swap(array[low], array[high]);
        }
    } while (low < high);
    swap(array[left], array[high]);
    return high;
}

void quickSort(int left, int right, int array[]) { //반환된 pivot을 기준으로 양쪽을 2분할하여 다시 정렬
    if (left < right) {
        int q = partition(array, left, right);
        quickSort(left, q - 1, array);
        quickSort(q + 1, right, array);
    }
}

harinboy 3년 전 0

40줄 매개변수에 0, M-1이 조금 이상한 것 같습니다.

방법 자체는 좋아보이네요!

dufdlf000 3년 전 0

harinboy님 right를 무엇으로 주어야할까요,,,? M으로 줘도 틀렸다고 나옵니다 ㅠㅠ

harinboy 3년 전 0

M은 수를 탐색하고 출력하는 횟수입니다.

array2 전체에서 curarray[i]가 있는 위치를 찾는 건데, 예를 들어 M이 1이라고 array2[0]~array2[1]의 범위에 찾는 값이 있으라는 보장이 없겠죠?

array2의 인덱스의 범위를 매개변수로 주셔야합니다.

참고로 필요한 변수는 이미 선언하셨습니다.

dufdlf000 3년 전 0

harinboy님

정말 감사합니다 ㅠㅠ 정말 부끄럽네요ㅠㅠ 조금만 더 유의깊게 봤으면 해결할 수 있었는데 괜히 방법이 틀렸나 해서 자세히 못 봤네요 ㅠㅠㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 방법으로는 안되는건가요?ㅠㅠ

dufdlf000 3년 전 0

harinboy 3년 전 0

dufdlf000 3년 전 0

harinboy님 right를 무엇으로 주어야할까요,,,? M으로 줘도 틀렸다고 나옵니다 ㅠㅠ

harinboy 3년 전 0

dufdlf000 3년 전 0

harinboy님

정말 감사합니다 ㅠㅠ 정말 부끄럽네요ㅠㅠ 조금만 더 유의깊게 봤으면 해결할 수 있었는데 괜히 방법이 틀렸나 해서 자세히 못 봤네요 ㅠㅠㅠㅠㅠ

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말