백준 1940번 : 주몽 [Java]

문제 링크

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

1940번: 주몽

문제 설명

코드

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

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

        //재료의 갯수 N
        int N = Integer.parseInt(br.readLine());
        //갑옷을 만드는데 필요한 M
        int M = Integer.parseInt(br.readLine());

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

        //투포인터 사용하기 위한 정렬
        Arrays.sort(arr);

        int count = 0;
        int start = 0;
        int end = N - 1;

        while (start < end) {
            if (arr[start] + arr[end] < M) {
                start++;
            } else if (arr[start] + arr[end] > M) {
                end--;
            } else {
                count++;
                start++;
                end--;
            }
        }

        System.out.println(count);
    }
}

풀이

1. M(1 ≤ M ≤ 10,000,000) 이기 때문에 이중 for문을 사용 시에 시간복잡도 에러 -> 투포인터 사용 [시간복잡도 O(N)]

2. N과 M의 정수를 입력 받아 N의 갯수만큼 배열 생성하고, 3번째 줄의 정수를 배열에 삽입한다.

3. 투포인터를 사용하기 위해서 정렬을 진행한다.

4. 투포인터 이동원칙을 사용하여 값을 도출한다.

 

투포인터 이동 원칙

arr[start] + arr[end] > n : end--;
arr[start] + arr[end] < n : start++;
arr[start] + arr[end] == n : start++,end--; count++;