운동하는 개발자/알고리즘, 코딩테스트

Beakjoon] '좋은 수' 구하기 (백준 코테) = 투포인터

우용현 2023. 11. 6. 22:14
728x90

문제주소 : https://www.acmicpc.net/problem/1253

 

1253번: 좋다

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

www.acmicpc.net


문제 :  N개의 수 중에 다른 두 수의 합으로 표현되는 수 개수 찾기

 

풀이 : 정렬시킨 뒤 투포인터 기술로 양 끝에서부터 더하며 비교한다.
추가로 '다른 두 수의 합으로' 라는 말에 주의하여 자기 자신을 더하지 않도록 예외처리한다.

 

 

코드는 아래 숨김

더보기
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n;
    std::cin >> n;
    std::vector<int> item(n, 0);
    
    for (int i = 0; i < n; ++i) {
        std::cin >> item[i];
    }

    std::sort(item.begin(), item.end());

    int result = 0;
    
    for (int k = 0; k < n; ++k) {
        int start = 0, end = n - 1;
        while (start < end) {
            if (start == k) {
                start++;
                continue;
            }else if (end == k) {
                end--;
                continue;
            }

            long long temp = item[start] + item[end];
            if (temp > item[k]) {
                end--;
            }
            else if (temp < item[k]) {
                start++;
            }
            else {
                result++;
                break;
            }
        }       
    }
    std::cout << result;
 }

 

알게 된 것 : 파이썬 알고리즘 인터뷰 책에서 했던 투포인터 문제 기억이 새록새록 나며 그땐 어떻게 적용할지 너무 어려웠다고 생각했었는데 지금은 이렇게 쉬웠나 싶은..

728x90