[백준] 주몽(1940)

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

투 포인터를 사용하여 문제를 해결하는 문제이다. 갑옷은 2개의 재료로 만들어진다고 나와있으므로 2개의 수를 더해서 M을 만족할 수 있는 개수를 찾으면 된다.

또한 시간 제한이 2초이고 N의 최댓값은 15,000이므로 대략 1초에 100만번 연산이 가능한 $O(nlogn)$ 알고리즘까지 사용할 수 있다.

※ $O(n^2)$은 1초에 3000번 연산 가능
=> 2초에 6000번 연산 가능함
=> 데이터 크기의 최댓값 15,000 만족 불가

정렬 알고리즘은 보통 $O(nlogn)$ 이므로 입력값을 정렬할 수 있다.

따라서 문제풀이 방법은 다음과 같다.

1. 주어진 입력값 오름차순 정렬
2. 시작 인덱스, 마지막 인덱스 설정
3. 두 수의 합이 M보다 작으면 i += 1
4. 두 수의 합이 M보다 크면 j -= 1
5. 두 수의 합이 M이면 count += 1, i += 1, j -= 1

Python

N = int(input())
M = int(input())
arr = list(map(int, input().split()))

# 배열 오름차순 정렬
arr.sort()

count = 0
i = 0 # 시작 인덱스
j = N - 1 # 마지막 인덱스

# 시작과 마지막 인덱스가 만나기 전까지
# 모든 원소에 탐색할때까지
while i < j:
    # 두 수의 합이 M보다 작을 경우
    if arr[i] + arr[j] < M:
        # 시작 인덱스 증가
        # 가장 최근에 가리킨 가장 작은 수를 고려 안한다는 말
        i += 1
    
    # 두 수의 합이 M보다 클 경우
    elif arr[i] + arr[j] > M:
        # 마지막 인덱스 감소
        # 가장 최근에 가리킨 가장 큰 수를 고려 안한다는 말
        j -= 1
    
    # 두 수의 합이 M인 경우
    else:
        count += 1
        i += 1
        j -= 1

print(count)

Java

자바의 경우 배열 오름차순은 java.util.Arrays에 있는 sort() 함수를 사용하면 된다는 점을 기억하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P_1940 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

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

        // 배열 오름차순 정렬
        Arrays.sort(arr);

        int count = 0;
        int i = 0;
        int j = N - 1;

        // 투 포인터 이동 원칙
        while (i < j) {
            if (arr[i] + arr[j] < M) { // 두 재료의 합이 M보다 작으면
                i++; // start 증가
            } else if (arr[i] + arr[j] > M) { // 두 재료의 합이 M보다 크면
                j--; // end 감소
            } else {
                count++; // 정답 증가
                i++; j--; // start 증가, end 감소
            }
        }
        System.out.println(count);
        br.close();
    }
}