[Baekjoon]백준 1920 수 찾기(실버 4) - Python, C++

문제설명

문제를 살펴보면 이분 탐색 테마의 문제인데, 첫번째에 비교 대상인 리스트가 주어지고

두번째에 결과값에 영향을 끼치는 리스트를 하나 입력을 받는다 이후에 처음으로 입력받은 리스트에

두번째로 입력받은 리스트의 값이 존재하면 1을, 아니라면 0을 출력하면 된다

Python의 딕셔너리로 풀어도 가능할 거 같긴 하지만 문제 출제 의도에 맞게 이분 탐색을 직접 구현하여 코드를 작성하였다

 

코드 설명을 하기전에 이분 탐색에 대해 설명을 하자면 정렬된 리스트를 기준으로 하며, 해당 값을 찾을 때

먼저 중간에 위치한 값과 비교를 한다 리스트에 정렬이 되어있기 때문에 해당 위치의 값과 비교를 하였을 때 값이 작다면

더 낮은 index에 값이 존재할 것이고, 크다면 더 높은 index에 값이 존재할 것이라는 추측이 가능하다

이러한 로직을 활용하여 찾는 값의 위치를 확인하는 문제이다

 

따로 함수를 구현하여 작성하였는데, 제일 왼쪽 index와 제일 오른쪽 index를 각각 선언해주고, 중간값을 찾는다

그리고 그 중간값에 위치한 값과 비교 대상을 비교하여 값이 크기가 크다면 left_idx의 값을 mid + 1로 선언한다

이렇게 선언하면 중간값보다 큰 리스트부터 제일 마지막 index까지의 리스트 안에서 비교를 반복하게 될 것이다

값이 작은 경우에는 right_idx의 값을 mid - 1로 선언하여 비교를 계속해서 이어나가면 된다

만약 찾는 값이 등장하면 return 1을 해주고, while문을 빠져나오게 되면(즉, 값이 없다면) return 0을 해주면 된다

def binary_sort(N):
    left_idx = 0
    right_idx = num - 1
    while left_idx <= right_idx:
        mid = (left_idx + right_idx) // 2
        if N > res[mid]:
            left_idx = mid + 1
        elif N < res[mid]:
            right_idx = mid - 1
        else: # 값을 찾은 경우
            return 1
    return 0 # 값을 찾지 못한 경우
        

num = int(input())
res = list(map(int, input().split()))
res.sort()

M = int(input())
cmp = list(map(int, input().split()))

for i in cmp:
    print(binary_sort(i))

C++로도 같은 로직을 사용하여 작성하였는데, 시간초과가 발생하는 것을 확인할 수 있었다

그래서 검색을 해본 결과 ios::sync_with_stdio(false);와 cin.tie(NULL);을 사용하면 시간초과가 해결된다고 해서

시도를 해보아도 그대로 시간초과가 발생하는 것을 확인할 수 있었다

검색을 더 해본 결과 cin, cout 대신에 scanf와 printf를 쓰면 실행시간을 줄일 수 있다는 것을 알 수 있었고

밑의 코드로 맞았습니다를 확인할 수 있었다 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binary_sort(int N, const vector<int>& res) {
    int left_idx = 0;
    int right_idx = res.size() - 1;
    while (left_idx <= right_idx) {
        int mid = (left_idx + right_idx) / 2;
        if (N > res[mid])
            left_idx = mid + 1;
        else if (N < res[mid])
            right_idx = mid - 1;
        else // 값을 찾은 경우
            return 1;
    }
    return 0; // 값을 찾지 못한 경우
}

int main() {
    int num;
    cin >> num;

    vector<int> res(num);
    for (int i = 0; i < num; ++i) {
        scanf("%d", &res[i]);
    }
    sort(res.begin(), res.end());

    int M;
    cin >> M;

    vector<int> cmp(M);
    for (int i = 0; i < M; ++i) {
        scanf("%d", &cmp[i]);
    }

    for (int i = 0; i < M; ++i) {
        printf("%d\n", binary_sort(cmp[i], res));
    }

    return 0;
}

첫번째 시간 초과는 cin, cout을 사용한 버전, 두번째 시간 초과는 ios::sync_with_stdio(false);와 cin.tie(NULL);를 사용한

버전, 이후에 scanf와 printf를 사용하였는데 length Error가 발생하였고 그래서 ios::sync_with_stdio(false);와 cin.tie(NULL);

코드를 삭제하였더니 맞았습니다! 를 확인할 수 있었다