1940번: 주몽

문제

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있습니다. 갑옷은 두 개의 재료로 만드는데, 두 재료의 고유한 번호를 합쳐서 M이 되면 갑옷이 만들어집니다. 주어진 N개의 재료 번호들 중 합이 M이 되는 두 재료의 쌍의 개수를 구하는 문제입니다.

• 입력: 첫째 줄에 재료의 개수 N (1 ≤ N ≤ 15,000), 둘째 줄에 갑옷을 만드는데 필요한 수 M (1 ≤ M ≤ 10,000,000), 셋째 줄에 N개의 재료 번호가 주어집니다.
• 출력: 갑옷을 만들 수 있는 쌍의 개수를 출력합니다.

링크: https://www.acmicpc.net/problem/1940

풀이 1: 이중 반복문을 활용한 완전탐색 (Brute Force)

가장 직관적인 방법으로, 이중 반복문을 사용하여 2개의 재료를 고르는 모든 경우의 수를 확인합니다.

1. 배열에 N개의 재료 번호를 입력받습니다.
2. 바깥쪽 반복문은 i를 0부터 n-2까지, 안쪽 반복문은 j를 i+1부터 n-1까지 순회하며 중복 없이 두 개의 쌍을 고릅니다.
3. 고른 두 재료의 합(a[i] + a[j])이 M과 같다면 정답 카운트를 1 증가시킵니다.

N이 최대 15,000이므로 연산 횟수는 약 1.1억 번(O(N^2)) 정도이며, 시간 제한(2초) 내에 통과할 수 있습니다.

코드 1

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int m = Integer.parseInt(br.readLine());
       int[] a = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }

       int ans = 0;
       for (int i = 0; i < n - 1; i++) {
          for (int j = i + 1; j < n; j++) {
             if (a[i] + a[j] == m) {
                ans++;
             }
          }
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

풀이 2: 정렬 및 투 포인터 (Two Pointers) 활용

탐색 범위를 양 끝에서부터 좁혀나가는 투 포인터 알고리즘을 사용하면 O(Nlog N)의 시간 복잡도로 훨씬 빠르게 해결할 수 있습니다.

1. 배열 정렬: 입력받은 배열을 오름차순으로 정렬합니다. (O(Nlog N))
2. 투 포인터 탐색: 시작 인덱스(s)를 배열의 맨 처음(최솟값), 끝 인덱스(e)를 배열의 맨 끝(최댓값)으로 설정합니다.
3. 두 수의 합(sum = a[s] + a[e])을 비교합니다.
   • sum == M이면 정답을 1 증가시키고, 다음 쌍을 찾기 위해 s는 증가, e는 감소시킵니다.
   • sum < M이면 값이 더 커져야 하므로 s를 증가시킵니다.
   • sum > M이면 값이 더 작아져야 하므로 e를 감소시킵니다.
4. 두 포인터가 교차할 때까지 반복합니다. (O(N))

코드 2

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int m = Integer.parseInt(br.readLine());
       int[] a = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }

       // 1. 투 포인터를 사용하기 위해 배열 오름차순 정렬
       Arrays.sort(a);

       int ans = 0;
       int s = 0;
       int e = n - 1;

       // 2. 양 끝에서부터 좁혀오며 두 수의 합 탐색
       while (s < e) {
          int sum = a[s] + a[e];
          
          if (sum == m) {
             ans++;
             s++;
             e--;
          } else if (sum < m) {
             // 합이 M보다 작다면, 값을 키우기 위해 왼쪽 포인터 이동
             s++;
          } else {
             // 합이 M보다 크다면, 값을 줄이기 위해 오른쪽 포인터 이동
             e--;
          }
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

정렬 (Sorting), 투 포인터 (Two Pointers), 브루트포스 (Brute Force)