코딩 테스트 공부 - C++/좋은 수 구하기(백준 1253번)

시간 제한 : 2초

메모리 제한 : 256MB

 

문제 

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

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

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

 

입력

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

 

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

문제 해설

두 개의 합 혹은 다른 두 수라는 내용이 문제에서 나올 경우 2 포인터 알고리즘이라고 생각하는 것이 중요!

해당 문제에서 시간 복잡도의 경우 최소 $O(n\log(n))$ 이어야 하기 때문에 정렬($O(n\log(n))$) 및 2 포인터 알고리즘($O(n)$)을 사용

 

먼저 주어진 N 개의 수를 정렬 시킨 후 2 포인터 알고리즘으로 양 끝에서부터 하나씩 이동하면서 좋은 수를 찾는 것이 핵심이다.

 

답안 코드

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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N, 0);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  sort(A.begin(), A.end());

  int count = 0;
  for (int k = 0; k < N; k++) {
    long find = A.at(k);
    int i = 0;     // start
    int j = N - 1; // end

    while (i < j) {
      if (A.at(i) + A.at(j) == find) {
        if (i != k && j != k) {
          count++;
          break;
        } else if (i == k) {
          i++;
        } else if (j == k) {
          j--;
        }
      } else if (A.at(i) + A.at(j) < find) {
        i++;
      } else if (A.at(i) + A.at(j) > find) {
        j--;
      }
    }
  }
  cout << count << endl;

  return 0;
}

 

여기서 중요한 점은 두 가지로 볼 수 있다.

첫 째, 시간 복잡도에 알맞은 알고리즘 선택하기.

둘 째, 두 수 혹은 서로 다른 두 개의 수 가 나올 경우 2 포인터 알고리즘을 사용할 수도 있겠구나라고 생각하기.