백준 1253 : 좋다

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

---

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

---

생각

1. 이중 for문으로 가능할거 같다 -> 시간초가 날 확률이 높음
2. 2개의 합이라고 했으니까 투포인터로 양 끝에서 확인하는 방식으로 하자
3.  

---

코드

// 4:40분에 시작함함
// 일단 한눈에 안들어옴
// 서로 다른 2개를 골라서 존재하는 수를 만들 수 있으면 된다

// 이중 for문으로 확인하면 되는거 아닐까
// 시간 초과 날거 같긴함
// 일단 입력 받아서 있는지 확인하는 것을 먼저 만들어야 겠는데
// 입력 범위가 -10억~10억이니까 unordermap으로 하면 편하겠네
// 숫자 압축이 필요한가 고민을 해봅시다, 걍 배열 크기 20얼짜리로 하고
// 다 패기하고 정렬을 하고 왼쪽, 오른쪽 하나씩 하고 오른쪽이든 왼쪽이드 넘어가면 없는걸로 하고
// 있으면 그거 저장해 놓음, 있는건 또할 필요 없으니까

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

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n, 0);

    for(int ix = 0; ix < n; ++ix)
    {
        cin >> nums[ix];
    }

    // 정렬렬
    sort(nums.begin(), nums.end());
    
    // 결과과
    int result = 0;

    // 중복 된거 빠르게 걸러내기용
    unordered_set<int> visited;

    for(int ix = 0; ix < n; ++ix)
    {
        // 투포인터
        int right = n-1;
        int left = 0;

        // 이미 확인한거 거르기기
        if(visited.count(nums[ix]))
        {
            result += 1;
            continue;
        }

        // 오른쪽이 왼쪽보다 작거나 같으면 중단단
        while(right > left)
        {
            if(nums[right] + nums[left] == nums[ix])
            {
                result += 1;
                
                visited.insert(nums[ix]);
                break;
            }

            if(nums[ix] < nums[right] + nums[left])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
    }

    cout << result;
}

---

틀린 이유

• 자기 자신을 확인하는 것을 하지 않음

---

수정 코드

 

// 4:40분에 시작함함
// 일단 한눈에 안들어옴
// 서로 다른 2개를 골라서 존재하는 수를 만들 수 있으면 된다

// 이중 for문으로 확인하면 되는거 아닐까
// 시간 초과 날거 같긴함
// 일단 입력 받아서 있는지 확인하는 것을 먼저 만들어야 겠는데
// 입력 범위가 -10억~10억이니까 unordermap으로 하면 편하겠네
// 숫자 압축이 필요한가 고민을 해봅시다, 걍 배열 크기 20얼짜리로 하고
// 다 패기하고 정렬을 하고 왼쪽, 오른쪽 하나씩 하고 오른쪽이든 왼쪽이드 넘어가면 없는걸로 하고
// 있으면 그거 저장해 놓음, 있는건 또할 필요 없으니까

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

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n, 0);

    for(int ix = 0; ix < n; ++ix)
    {
        cin >> nums[ix];
    }

    // 정렬렬
    sort(nums.begin(), nums.end());
    
    // 결과과
    int result = 0;

    // 중복 된거 빠르게 걸러내기용
    unordered_set<int> visited;

    for(int ix = 0; ix < n; ++ix)
    {
        // 이미 확인한거 거르기기
        if(visited.count(nums[ix]))
        {
            result += 1;
            continue;
        }

        // 투포인터
        int right = n-1;
        int left = 0;

        // 오른쪽이 왼쪽보다 작거나 같으면 중단단
        while(right > left)
        {
            // 본인은 피해야함함
            if(left == ix)
            {
                left++;
                continue;
            }
            if(right == ix)
            {
                right--;
                continue;
            }

            if(nums[right] + nums[left] == nums[ix])
            {
                result += 1;
                
                visited.insert(nums[ix]);
                break;
            }

            if(nums[ix] < nums[right] + nums[left])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
    }

    cout << result;
}

---

결과

• 문제 풀이 시간 : 60분
• 메모리 :  2028KB
• 시간 :  20ms

  ---

배운점 및 고칠점

• 예외 처리를 하는것을 고려하도록
• unordered_set으로 중복을 확인한것은 좋은거 같음