[99클럽/코딩테스트 챌린지/C++] 투 포인터를 활용한 [1253번 좋다] 문제 해결

문제 링크

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

 

문제 상황

"좋은 수"를 찾는 문제는 주어진 N개의 수 중에서 어떤 수가 다른 두 수의 합으로 나타낼 수 있는지를 판별하는 것입니다. 초기 구현에서는 두 포인터(Two Pointers) 알고리즘을 활용했지만, 몇 가지 문제로 인해 예상한 대로 동작하지 않았습니다

문제 원인

1. 현재 값을 포함한 계산 문제: 검증 대상 숫자 val 자체를 두 포인터 탐색에서 포함하여 계산한 경우가 있었습니다. 같은 숫자라도 인덱스가 다른 경우만 유효하므로, 이를 제외할 처리가 필요했습니다.
2. 벡터 초기화 문제: 고정 크기 배열을 사용하여 불필요한 메모리를 할당했으며, 입력 크기에 맞게 동적으로 초기화하지 않았습니다.
3. Search 함수의 비효율적 구조: 두 포인터 탐색 중 반환값 처리가 명확하지 않았고, 계산 과정에서 중복 처리가 발생할 가능성이 있었습니다.

---

해결 방법

1. 인덱스 제외 처리: 두 포인터 탐색 시 현재 검증 중인 숫자의 인덱스를 제외하여 중복 계산을 방지했습니다.
2. 동적 벡터 초기화: 입력 크기 N에 맞게 벡터를 동적으로 초기화하여 불필요한 메모리 사용을 줄였습니다.
3. Search 함수 구조 개선: 두 포인터 탐색 중 excludeIdx를 활용하여 효율적으로 동작하도록 함수 구조를 명확히 했습니다

---

최종 코드

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<long long> datas;

int Search(int left, int right, long long val, int excluedeIdx) // 제외할 Index
{
	while (left < right)
	{
        if (left == excluedeIdx)
        {
            left++;// 검사 대상 제외
            continue;
        }
        if (right == excluedeIdx)
        {
            right--;
            continue;
        }
        long long sum = datas[left] + datas[right];
        if (sum == val) return 1;
        if (sum < val)
        {
            left++;
        }
        else if (sum > val)
        {
            right--;
        }
	}
    return 0;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    int count = 0;
    datas = vector<long long>(N);
    for (int i = 0; i <N; i++)
    {
        cin >> datas[i];
    }

    sort(datas.begin(), datas.end());


    for (int i = 0; i < N; i++)
    {
        int left = 0; // 왼쪽
        int right = N - 1; // 오른쪽
        count += Search(left, right, datas[i],i);
    }

    std::cout << count << '\n';

    return 0;
}

---

배운 점

1. 두 포인터 알고리즘의 유용성: 정렬된 배열에서 특정 조건을 만족하는 쌍을 찾는 데 매우 효율적임을 다시금 깨달았습니다.
2. 코드의 가독성과 구조 개선: 복잡한 알고리즘이라도 구조적으로 설계하면 디버깅과 성능 개선이 용이하다는 점을 배웠습니다.
3. 인덱스 관리의 중요성: 특정 값을 탐색에서 제외하기 위해 인덱스를 철저히 관리해야 한다는 점을 다시 확인했습니다.

---

결론

이번 문제를 통해 알고리즘 설계에서 발생할 수 있는 다양한 실수를 발견하고 개선하는 과정을 경험할 수 있었습니다. 특히, 두 포인터 알고리즘의 강력함과 효율성을 다시 확인했으며, 앞으로 유사한 문제를 해결할 때 중요한 참고자료가 될 것입니다. 효율성을 높이고 문제를 구조적으로 해결하는 데 집중할 것입니다.