백준 1253번 : 좋다 (골드 4)

문제

N개의 수를 입력받아 i번째 수가 다른 j, k번째 수의 합으로 나타나지면 그 수를 "좋다"고 말한다

N개의 수 중 "좋다"라고 말 할 수 있는 수의 개수는 몇 개인지를 물어보는 문제이다

인덱스가 다르면 숫자가 같아도 다른 수임!

풀이

N개의 최대는 2000이다. 즉 O(N^2)로 풀 수 있는 문제임

어떤 수의 입력 범위는 -10억부터 10억까지이다. 두 수의 합으로만 계산하니 INT의 범위 안이겠지만 나는 그냥 long long으로 했다

내가 선택한 알고리즘은 투 포인터 알고리즘이다

투 포인터 알고리즘

코테에서도 간간히 등장하는 문제이다

간단하게 설명하자면 리스트가 있을 때 좌측과 우측 포인터를 만들어(진짜 포인터가 아니고 그냥 인덱스를 기록) 양 측의 포인터로 연산하면서 값을 구해나가는 식

그리고 연산 결과에 따라 좌측과 우측을 변경시키면서 좌측이 우측보다 커질때같은 종료 조건을 두어 하는 방식

구현 방식은 개발자 맘대로다

시간 복잡도는 어차피 리스트를 순차적으로 도는거니까 O(N)이다

---

그래서 이 문제에 어떻게 적용하느냐

N개의 수를 입력받은 배열을 일단 투 포인터로 쓸건데 투 포인터를 하면서 언제 좌측 포인터를 증가시키고 언제 우측 포인터를 감소시킬지를 알아야 한다

그러기 위해서 정렬을 해준다. 오름차순 정렬을 해주고 좌측 포인터를 배열의 시작, 우측 포인터를 배열의 끝으로 잡은 다음 좌측 + 우측이 특정 값보다 작으면 좌측 포인터를 증가시켜 더 큰 값으로 계산시키게 하고 특정 값보다 크면 우측 포인터를 감소시켜 더 작은 값이 계산되도록 한다

처음 배열의 0번째부터 N - 1번째 인덱스까지 계산해야 할 값으로 정해두고

반복문 안에서 투 포인터 알고리즘을 실행한다. 이때 중요한건 자기 자신은 제외한 다른 두 값을 더하는것임

그래서 나는 left나 right가 i와 같아지면 포인터를 변경시켰다

그리고 종료 조건은 left <= right로 했다가 left == right일 때 같은 값을 더하는 경우가 생겨서 left < right로 설정했다

코드

#include <bits/stdc++.h>
using namespace std;

int N;
long long arr[2004];
int answer;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

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

    sort(arr, arr + N);

    for (int i = 0; i < N; i++)
    {
        int left = 0;
        int right = N - 1;

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

            if (arr[left] + arr[right] == arr[i])
            {
                answer++;
                break;
            }
            else if (arr[left] + arr[right] < arr[i])
            {
                left++;
            }
            else if (arr[left] + arr[right] > arr[i])
            {
                right--;
            }
        }
    }

    cout << answer;

    return 0;
}

회고

정답률이 24%인 문제이지만 투 포인터만 잘 알고 있으면 쉽게 해결되는 문제였다

투 포인터를 쓸 때는 시간 복잡도가 O(N)이 걸리는 것과 종료 조건, 포인터 변경 조건을 잘 알아야 할 것 같다