[백준] 1940_주몽 - JAVA

백준_1940

1940번: 주몽

 

투 포인터

투 포인터에 대한 설명은 아래 링크를 참고

[백준] 2018_수들의 합5 - JAVA

 

이 문제는 두 재료의 번호의 합을 구하고 크기를 비교하는 문제라 받을 배열을 정렬하여 풀면 굳이 이중 반복문을 사용하지 않을 수 있는 문제다. 이 문제도 투 포인터를 사용하여 풀이하는 문제인데, 먼저 투 포인터의 이동 원칙에 대해 알아보자.

 

투 포인터 이동 원칙

arr[i] + arr[j] > n 이면 j--;
arr[i] + arr[j] < n 이면 i++;
arr[i] + arr[j] == n이면 i++; j--; count++;

위 원칙을 생각하면서 아래 과정을 살펴보자.

 

이 전에 풀었던 투 포인터는 두 개의 투 포인터 모두 배열 앞쪽에서 시작했다. 이번 문제의 투 포인터는 하나는 배열의 맨 앞, 다른 하나는 배열의 맨 뒤에서부터 시작한다.

투 포인터의 이동 원칙해 따라서 위 배열을 계산해보자. arr[i]는 1, arr[j]는 7이다. 둘이 더하면 8이된다. 8은 n인 9보다 작으므로 i++ 코드가 실행된다.

그 다음 반복문에서는 arr[i]가 2, arr[j]가 7이다. 두 개를 더하면 9이고, n과 똑같다. 그러므로 i++, j--, count를 ++ 해주면 된다.

이렇게 반복을 열심히 돌다가 i와 j가 맞닿아있는 시점에 반복문을 종료하면 된다.

 

코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder(st.toString());

        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int maxN = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        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] < maxN)  i++;
            else if(arr[i] + arr[j] > maxN) j--;
            else {
                count++;
                i++;
                j--;
            }
        }
        System.out.println(count);
    }
}

 

제출 결과