백준 1920번: 수 찾기

1920번: 수 찾기



처음 코드
#include <stdio.h>
#include <stdlib.h>

void bubble_sort(int f_arr[], int len);

int main(void)
{
    int N, M, cnt0, cnt1, isNumExist, f_indx, b_indx, mid_indx;

    scanf("%d", &N);

    int * nums = malloc(N*sizeof(int));

    for (cnt0=0; cnt0<N; cnt0++)
        scanf("%d", &nums[cnt0]);

    bubble_sort(nums, N);

    scanf("%d", &M);

    int * result = malloc(M*sizeof(int));

    //--------------
    // printf("\n\n");
    // for (cnt0=0; cnt0<N; cnt0++)
    //     printf("%d ", nums[cnt0]);
    // printf("\n\n");
    //--------------

    for (cnt0=0; cnt0<M; cnt0++)
    {
        scanf("%d", &result[cnt0]);

        f_indx = 0;
        b_indx = N;
        isNumExist = 0;

        for (cnt1=0; cnt1<(N); cnt1++)
        {
            mid_indx = (f_indx + b_indx) / 2;
            // printf("%d- --%d-- -%d\n", f_indx, mid_indx, b_indx);

            if (result[cnt0] == nums[mid_indx])
            {
                // printf("found! %d\n", nums[mid_indx]);
                isNumExist = 1;
                break;
            }
            else if (result[cnt0] < nums[mid_indx])
            {
                if ((N >> (cnt1+1)) == 0)
                    b_indx--;
                b_indx -= N >> (cnt1+1);
            }
            else
            {
                if ((N >> (cnt1+1)) == 0)
                    f_indx++;
                f_indx += N >> (cnt1+1);
            }
        }
        // printf("---\n");

        result[cnt0] = (isNumExist == 1) ? 1 : 0;
    }

    for (cnt0=0; cnt0<M; cnt0++)
        printf("%d\n", result[cnt0]);

    return 0;
}

void bubble_sort(int f_arr[], int len)
{
    int i, j, tmp, isSorted = 1;

    for (i=0; i<len; i++)
    {
        isSorted = 1;
        for (j=0; j<len-1; j++)
        {
            if (f_arr[j] > f_arr[j+1])
            {
                isSorted = 0;
                tmp = f_arr[j];
                f_arr[j] = f_arr[j+1];
                f_arr[j+1] = tmp;
                continue;
            }
        }

        if (isSorted)
            break;
    }
}

직접 버블정렬로 N개의 정수 정렬하고
이진탐색으로 입력받는 숫자마다 존재여부 판단하려 함.

실패.
버블정렬 생각보다 느림 + 이진탐색 잘못 구현.

2번째 시도 코드
#include <stdio.h>
#include <stdlib.h>

int compare(int * a, int * b);
void bubble_sort(int f_arr[], int len);

int main(void)
{
    int N, M, cnt0, cnt1, isNumExist, f_indx, b_indx, mid_indx, K;

    // Length of Number's Array
    scanf("%d", &N);

    // Make new array and put numbers in array
    int * nums = malloc(N*sizeof(int));
    for (cnt0=0; cnt0<N; cnt0++)
        scanf("%d", &nums[cnt0]);
    qsort(nums, N, sizeof(nums[0]), compare);

    // Input M and M numbers
    scanf("%d", &M);
    int * result = malloc(M*sizeof(int));

    for (cnt0=0; cnt0<M; cnt0++)
    {
        // Input number
        scanf("%d", &result[cnt0]);

        // Variables for Binary Search
        f_indx = 0;  // Foot index
        b_indx = N;  // Back index
        isNumExist = 0;  // determine whether number is in array or not

        for (cnt1=0; cnt1<=N; cnt1++)
        {
            // index variable setting
            mid_indx = (f_indx + b_indx) / 2;
            K = b_indx - mid_indx;

            // if size between index is less than 4, use Linear Search
            if ((b_indx-f_indx) < 4)
            {
                for (int idontwannagoschool=f_indx; idontwannagoschool<=b_indx; idontwannagoschool++)
                {
                    if (result[cnt0] == nums[idontwannagoschool])
                    {
                        isNumExist = 1;
                        break;
                    }
                }
            }
            // if number was found, exit loop
            else if (result[cnt0] == nums[mid_indx])
            {
                isNumExist = 1;
                break;
            }
            else if (result[cnt0] < nums[mid_indx])
                b_indx -= K;
            else
                f_indx += K;
        }
        result[cnt0] = (isNumExist == 1) ? 1 : 0;
    }

    for (cnt0=0; cnt0<M; cnt0++)
        printf("%d\n", result[cnt0]);

    return 0;
}

// very very slow sort function...
/*void bubble_sort(int f_arr[], int len)
{
    int i, j, tmp, isSorted = 1;

    for (i=0; i<len; i++)
    {
        isSorted = 1;
        for (j=0; j<len-1; j++)
        {
            if (f_arr[j] > f_arr[j+1])
            {
                isSorted = 0;
                tmp = f_arr[j];
                f_arr[j] = f_arr[j+1];
                f_arr[j+1] = tmp;
                continue;
            }
        }

        if (isSorted)
            break;
    }
}*/

// for qsort()
int compare(int * a, int * b)
{
    return (*a > *b) ? 1 : -1;
}

C에 원래 있는 qsort로 버블정렬 대체,
이진탐색 제대로 구현해서(지난달에 학교에서 한 번 해본 기억 생각남) 다시 시도.

실패.
범위를 조금씩 수정해도 계속해서 시간초과.

3번째 시도 코드
#include <stdio.h>
#include <stdlib.h>

/*
struct FNum {
    int value = 0;
    int index = 0;
} typedef fnum;*/

int compare(int * a, int * b);
void bubble_sort(int f_arr[], int len);

int main(void)
{
    int N, M, i, ni=0, mi=0;

    // Input numbers and sort them
    scanf("%d", &N);
    int * nums = malloc(N*sizeof(int));
    for (i=0; i<N; i++)
        scanf("%d", &nums[i]);
    qsort(nums, N, sizeof(int), compare);

    // Input questions and sort them
    scanf("%d", &M);
    int * questions = malloc(M*sizeof(int));
    for (i=0; i<M; i++)
        scanf("%d", &questions[i]);
    // copy array before sort it
    int * sample = malloc(M*sizeof(int));
    for (i=0; i<M; i++)
        sample[i] = questions[i];
    qsort(questions, M, sizeof(int), compare);

    // results setting
    int * results = malloc(M*sizeof(int));
    for (i=0; i<M; i++)
        results[i] = 0;

    //----------------------------------------------------

    // eureka
    while (ni < N)
    {
        // printf("nums: %d, questions: %d\n", nums[ni], questions[mi]);
        if (nums[ni] == questions[mi])
        {
            // printf("\tfound: %d\n", nums[ni]);
            for (i=0; i<M; i++)
            {
                if (sample[i] == nums[ni])
                    results[i] = 1;
            }
            mi++;
        }
        else if (nums[ni] > questions[mi])
            mi++;
        else
            ni++;
    }

    // print result
    for (i=0; i<M; i++)
        printf("%d\n", results[i]);

    return 0;
}

// for qsort()
int compare(int * a, int * b)
{
    return (*a > *b) ? 1 : -1;
}

문제 분류도 1차원 배열이었고
단일 for로만 풀 수 있다는 힌트를 얻어서
정렬된 N값들과 질문들을 나란히 세운 뒤 한 번의 반복만으로 수 찾기

실패.
작동은 잘 하는 것 같지만, 찾은 수의 결과를 저장하는 게 문제.
인덱스가 처음 입력이 아닌 정렬된 순서로 바껴서
다시 원래 인덱스를 찾으려면 이중 for문이 되어버림.


성공 코드
#include <stdio.h>
#include <stdlib.h>

int compare(int * a, int * b);

int main(void)
{
    int N, M, i, j, fi, bi, mid, d;

    // Input numbers and sort them
    scanf("%d", &N);
    int * nums = malloc(N*sizeof(int));
    for (i=0; i<N; i++)
        scanf("%d", &nums[i]);
    qsort(nums, N, sizeof(int), compare);

    // Input questions and sort them
    scanf("%d", &M);
    int * questions = malloc(M*sizeof(int));
    int * results = malloc(M*sizeof(int));
    for (i=0; i<M; i++)
        scanf("%d", &questions[i]);

    for (i=0; i<M;i++)
    {
        results[i] = 0;
        fi = 0; bi = N;
        while (fi <= bi)
        {
            mid = (fi + bi) / 2;
            if (nums[mid] < questions[i])
                fi = mid+1;
            else if (nums[mid] > questions[i])
                bi = mid-1;
            else
            {
                results[i] = 1;
                break;
            }
        }
    }

    for (i=0; i<M; i++)
        printf("%d\n", results[i]);

    return 0;
}

// for qsort()
int compare(int * a, int * b)
{
    return (*a > *b) ? 1 : -1;
}

???
이거 왜 맞지
그냥 단순하게
3번째 시도 코드에서 질문들 입력받은거 정렬 안하고
N값들만 정렬 후 각 질문마다 이진 탐색으로 찾았는데
생각보다 쉽게 되버려서 허망함…


학교에서 하던 코드업에서도 막힌 문제 있었는데
알고보니 동일한 문제였음.
1430: 기억력 테스트 2
:thinking: :thinking: :thinking:
잘 하면 이번주 방과후 시간에 풀 수 있을지도…?
결국 시험기간 다 되어서야 풀었다고 합니다

그리고 결국 못 참고 이진 탐색 코드를 봐버렸는데

이게 내가 예전에 만들어봤던 코드

fi = 0;
bi = N;
 while (fi <= bi)
{
    k = bi - fi;
    mid = (fi + bi) / 2;
    if (nums[mid] < questions[i])
        fi += k;
    else if (nums[mid] > questions[i])
        bi -= k;
    else
    {
        results[i] = 1;
        break;
    }
}

이게 위키백과 왈 정석 코드

// loop version : A[0 ~ N-1]
int binarySearch(int A[], int low, int high, int target){
    while(low <= high){
        int mid = (low + high) / 2;
        if(A[mid] == target) return mid;
        if(A[mid] > target) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

그림판에다 일일히 칸 그려보면서 k값 만들어서 좋아했는데
더 깔끔하고 빠른 방법이 있었네요…

그동안 여기 싸놓은 똥도 처리해야 되는데
학교 공부가 진짜 만만치 않네요
게임은 안해도 아직까지는 욕구 제어가 잘 되지 않는 느낌입니다
기말때 국영수 등급 못올리면 진짜 큰일나는데
나사 한 번 빠지면 숙제고 뭐고 계속 몰입해서…

1 Like
C++
#include <algorithm>
#include <iostream>
#include <vector>

auto main() -> int {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int N, M; std::cin >> N;
    std::vector<int> v(N);
    for (auto& i : v) std::cin >> i;
    std::cin >> M;

    std::sort(v.begin(), v.end());

    while (M--) {
        int x; std::cin >> x; 
        std::cout << std::binary_search(v.cbegin(), v.cend(), x) << '\n';
    }

    return 0;
}
2 Likes
Java 16

채점 현황

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] input = new int[sc.nextInt()];
		for(int i = 0; i < input.length; i++) {
			input[i] = sc.nextInt();
		}
		Arrays.sort(input);
		
		int[] numbers = new int[sc.nextInt()];
		for(int i = 0; i < numbers.length; i++) {
			numbers[i] = sc.nextInt();
		}
		sc.close();
		
		int[] result = new int[numbers.length];
		int m = 0, n = input.length - 1;
		
		for(int i = 0; i < result.length; i++) {
			while (m <= n){
				int mid = (m + n) / 2;
				if (input[mid] > numbers[i]) n = mid - 1;
		        else if (input[mid] < numbers[i]) m = mid + 1;
		        else {
		            result[i]++;
		            break;
		        }
		    }
			m = 0;
			n = input.length - 1;
		}
		
		for(int i = 0; i < result.length; i++) {
			System.out.println(result[i]);
		}
	}
}
1 Like

결국 어거지로 풀긴 했네요
근데 보니깐 코드업에서는 시간초과던ㄷ
이제 씻고 자야긋다

자바가 안쓰는 사이에 16버전도 나왔군요

4년전만해도 자바 9였나? 그게 제일 최신이었는데 말이죠…
근데 솔직히 제 기준으로는 8이랑 16이랑 별로 큰 차이가 느껴지진 않는것 같아요.