[백준] 1253번_좋다 C++

03 Apr 2023 in Study on Coding Test

투 포인터를 활용하는 문제

정답제출코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[2000];
int N;

bool IsGood(int target, int index)
{
    int left = 0, right = N-1;

    while(left < right)
    {
        if (left == index)
        {
            left++;
            continue;
        }
        else if (right == index)
        {
            right--;
            continue;
        }

        if (arr[left] + arr[right] == target)
            return true;

        else if (arr[left] + arr[right] > target)
            right--;
        else if (arr[left] + arr[right] < target)
            left++;
    }
    return false;
}
int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    // 예외처리 : N이 2 이하라면 다른 수 2개를 합할 수 없으므로 0을 리턴한다.
    if (N <= 2)
    {
        cout << 0;
        return 0;
    }

    sort(arr, arr + N);

    int ans = 0;

    for (int i = 0; i < N; ++i)
    {
        if (IsGood(arr[i], i))
            ans++;
    }

    cout << ans;

    return 0;
}

우선, N이 2 이하라면 두 수를 합할 수 없으니 좋은 수는 없다. 따라서 예외처리를 해준다.

그리고 순차적으로 좋은 수인지 판별을 해준다.

원리는 투 포인터와 이분 탐색을 합친 느낌이다.

우선 수 들을 입력받은 뒤에 정렬을 해준다.

그 다음에 left와 right 포인터를 지정해주었고, left 포인터는 인덱스 0에서 증가하고,

right 포인터는 맨 오른쪽인 N-1 지점부터 감소하기 시작한다.

만일 두 수를 합친 결과가 타겟에 비해서 높다면 right 포인터를 왼쪽으로 옮기고,

반대로 타겟에 비해서 낮다면 left 포인터를 오른쪽으로 옮기도록 구현하였다.

이런 것을 구현하면서 느낌이 투 포인터와 이분 탐색을 합친 느낌이었다.

오답제출코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[2000];
int N;

bool IsGood(int target, int index)
{
    int left = 0, right = index-1;

    while(left < right)
    {
        if (arr[left] + arr[right] == target)
            return true;
        else if (arr[left] + arr[right] > target)
            right--;
        else if (arr[left] + arr[right] < target)
            left++;
    }
    return false;
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    // 예외처리 : N이 2 이하라면 2개의 수를 합할 수 없으므로 좋은 수는 없다.
    if (N <= 2)
    {
        cout << 0;
        return 0;
    }

    sort(arr, arr + N);

    int ans = 0;

    for (int i = 2; i < N; ++i)
    {
        if (IsGood(arr[i], i))
            ans++;
    }

    cout << ans;

    return 0;
}

두 가지를 간과했다.

• 음수가 들어갈 수 있다는 것
• 같은 수가 여러개 들어갈 수 있다는 것

그래서 포인터의 값이 index 값과 같다면 생략을 하도록 조치하였다.

그리고 위의 코드에서 보듯이 원래는 right 포인터는 index-1에서 시작하도록 했는데

음수가 들어갔다면 어쩔 수 없이 전체를 탐색해야 하므로 N-1에서 시작하도록 하였다.