백준 1920풀이 - cin / cout 으로는 안 풀려

오늘은 풀이한 문제 중 백준 1920문제를 들고 나왔습니다.
의외성이 있어 공유합니다 :)

https://www.acmicpc.net/problem/1920

단순한 이진 탐색 문제인데요.

1) 최대 10만개의 숫자를 입력,
2) 다시 최대 10만개의 숫자를 입력받고
3) 각 숫자가 1)번의 10만개에 들어있는지 검색하는 문제입니다.

그냥 입력받은 수를 숫자 오름차순 정렬해서, 2진 탐색, 존재여부만 판단하는 되는 문제이나,
비교적 쉬움애도 불구하고 풀기 어려워 7번만에 제출, 통과했는데요.
바로 "시간초과"가 그 주범입니다.

이진 탐색 풀이의 원리

이진 탐색은 아래와 같습니다.

예를 들어 7개의 수가 있다고 할 때,

34

121

56

777

1024

10

142

이 숫자를 모두 작은 숫자에서 큰 숫자로 오름차순 정렬합니다.

10

34

56

121

142

777

1024

그리고 여기서 특정 숫자를 딱 던져주면서,
"이 중에 특정 숫자가 들어있나요?" 물어보는 겁니다.

특정 숫자가 777 이라고 가정해볼까요?
그러면 앞에서 부터 차례대로 찾는게 아니라,

먼저 4번째 위치를 찾습니다. 거기에는 121이 들어 있지요.
숫자를 찾는 컴퓨터의 입장에서는 아직 개봉한 위치만 숫자를 알 수 있을 뿐 다른 곳에 들어 있는 숫자를 알 수가 없습니다. 물론 처음부터 새로 찾으면 알수 있긴 하겠지만, 이 문제는 빠른 시간내에 탐색을 성공해야 하는 문제입니다.

?

?

?

121

?

?

?

비록 다른 곳의 숫자는 알 수 없으나 확실한 것은 숫자가 오름차순으로 정렬되어 있기 때문에,
찾고자 하는 숫자 777은 오른쪽 어딘가에 있다고 알 수가 있겠지요

X

X

X

121

?

?

?

그러면 이제 범위를 좁혀서 우측의 3개 중, 가운데 위치를 탐색하는 것입니다.
오! 2번만에 탐색에 성공했습니다!

X

X

X

121

?

777

?

이와 같이 범위를 점점 좁혀나가면서 결과를 찾아가는 방법을 이진 탐색 ( 또는 이분 탐색 ) 이라고 하는데요.
숫자가 들어 있는 칸의 갯수가 1024개이고 숫자순으로 정렬되어 있다면,
11번 안에 무조건 찾거나 또는 없다는 사실을 알 수 있습니다.

문제는..

문제는 찾아야 할 후보가 되는 수가 최대 100,000만개나 되는데요.
이분탐색을 구현하여 문제를 풀이하였으나 '시간초과' 오류가 발생하는 상황이었습니다.

처음 작성한 코드는 아래와 같습니다.

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

long a[100000];
long n;

bool bsearch(long b)
{
    long left = 0, right = n - 1;
    long mid, mid_value;
    while (left <= right)
    {
        mid = ( left + right ) >> 1;
        mid_value = a[mid];
        if (mid_value == b)return true;
        else if (b < mid_value) right = mid - 1;
        else if (mid_value < b) left = mid + 1;
    }

    return false;
}

int main()
{
    // n과 n개의 수 입력
    cin >> n;
    for (long i = 0; i < n; ++i)
        cin >> a[i];

    // 이진 탐색을 위한 정렬
    sort(a, a + n);

    // 탐색할 숫자 m 입력
    long m;
    cin >> m;

    // m개의 숫자를 입력받으면서
    long b;
    for (long i = 0; i < m; ++i)
    {
        cin >> b;
        if (bsearch(b))cout << "1" << endl;
        else cout << "0" << endl;
    }

    return 0;
}

샘플도 정상 풀이 되는 코드이고, 이 정도면 빠르고 완벽해! 하고
백준에서 채점해 보니 '시간초과'가 등장합니다.

결론은 C 언어의 기본 입출력 명령어를 사용하니 풀이가 되었는데요.
cin 은 scanf 로, cout 은 printf 명령어로 바꿔주면 됩니다.
이 경우 입력받는 시간과 출력하는 시간이 상당히 단축되는 장점이 있습니다.

cin >> m; ▶ scanf("%ld", &m);
cout << "1" << endl; ▶ printf("1\n");

최종소스

코드는 구구절절 설명 드리기보다는 주석으로 대체합니다.

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

long a[100000];
long n;

// a 배열의 n 개 요소에서 이진 탐색
// a 배열은 정렬되어 있어야 함
bool bsearch(long b)
{
    // 좌우 끝점을 설정
    long left = 0, right = n - 1;
    // 중앙 위치를 저장할 변수
    long mid, mid_value;
    // 좌우가 맞닿을 때까지 반복
    while (left <= right)
    {
        // 중앙 위치를 구하고
        mid = ( left + right ) >> 1;
        mid_value = a[mid];
        // 숫자를 찾았는지 확인, 찾았으면 true 반환
        if (mid_value == b)return true;
        // 목표숫자보다 찾은 숫자가 크면 우 끝점위치 조정, 다시 탐색
        else if (b < mid_value) right = mid - 1;
        // 목표숫자보다 찾은 숫자가 작으면 좌 끝점위치 조정, 다시 탐색
        else if (mid_value < b) left = mid + 1;
    }

    // 못찾았으면 false 반환
    return false;
}

int main()
{
    // n과 n개의 수 입력
    scanf("%ld", &n);
    for (long i = 0; i < n; ++i)
        scanf("%ld", &a[i]);

    // 이진 탐색을 위한 정렬
    sort(a, a + n);

    // 탐색할 숫자 m 입력
    long m;
    scanf("%ld", &m);

    // m개의 숫자를 입력받으면서
    long b;
    for (long i = 0; i < m; ++i)
    {
        scanf("%ld", &b);
        // 바로 바로 이분탐색하여 결과를 출력
        // 찾으면 1, 못찾으면 0 출력
        if (bsearch(b))printf("1\n");
        else printf("0\n");
    }

    return 0;
}

문제 유형이 꽤 많은 것 같습니다. 모든 유형의 문제를 풀고나서 68밀리초의 빠른 처리속도를 뽐내고 있군요 :)

앞으로도 다른 알고리즘 문제는 cin, cout 대신
scanf, printf 를 사용하는 것으로 가닥을 잡아야 할 것 같습니다.

 

실무 유사 상황?

사실 실무에서도 비슷한 사례가 있습니다.
C#이나 비주얼 베이직의 윈폼(WinForm)으로 개발한 프로그램으로 출력결과를 화면에 보여주는 경우인데요.

일련의 반복작업이 집중 실행될 때,
라벨이나 텍스트 상자의 Text 속성을 자주 갱신하면 처리 속도가 매우 느려집니다.
이는 단순히 언어 차원의 문제가 아닙니다.

실제가 아닌 가상으로 꾸며본 화면입니다.

한건 한건 처리가 0.001초만에 이루어지는 경우라면,
100건을 처리할 때만 한번씩 화면을 갱신하거나,
0.1초마다 한번씩 화면을 갱신하는 방법을 사용해야 처리속도에 지장이 없습니다.

이래 저래 바쁘다 보니, 몇문제 못풀었지만
앞으로 백준 랭킹 5,000위까지는 진입 목표입니다 :)

필요하신 분에게 도움이 되시길 바랍니다. 그러면 이만 :)

도움이 되셨다면 공감 한방, 댓글은 굿잡!
감사합니다~