Java 백준 문제풀이 (41) 1940번 : 주몽

 

 

투 포인터를 사용하는 문제 자체가 처음이라면 이전 글을 먼저 읽어보자.

보다 친절하게 설명해놨다.

사실 쉬운 문제라서 딱히 이론적인 부분을 이해해야 하는 건 아니긴 하다.

 

 

 

https://7357.tistory.com/235?category=1066252 

Java 백준 문제풀이 (40) 2018번: 수들의 합5

 

 

 

 

 

 

 

1 <= N <= 15,000개의 자연수와 두 개의 합으로 구해야 하는 값 M이 주어진다.

 

어? 이거 투포인트 알고리즘 쓰면 O(N)으로 해결할 수 있겠네!

아니다. 예제를 보면 주어지는 값의 배열 N이 전혀 정렬되어 있지 않은 것을 확인할 수 있다.

 

따라서 우선 퀵 정렬 혹은 병합 정렬을 이용해서 정렬해야 한다.

직접 정렬을 구현할 것이 아닌 이상 Arrays.sort()를 사용하면 퀵 정렬, Collections.sort()를 사용하면 병합 정렬을 적용할 수 있다.

Arrays.sort()를 사용해서 문제를 풀었고 분명히 투 포인터 문제가 맞는데도 시간 초과가 나왔다면 Collections.sort()를 시도해보자.

(Arrays.sort()는 퀵 정렬 알고리즘 기반으로 최악의 경우 시간 복잡도가 O(n^2)지만 Collections.sort()는 timsort 알고리즘으로 구현되어 최악의 경우에도 O(nlogn)을 보장한다.)

 

잠시 정렬로 이야기가 벗어났는데, 정렬한 뒤에 어떻게 풀어야 할지 생각해 보자.

 

이전 문제는 연속된 수의 합을 구하는 문제였기 때문에 0번 인덱스부터 차례대로 포인터를 옮기며 순서대로 더하면 됐지만, 이번에는 두 개의 수만 뽑아서 원하는 값을 구해야 한다.

 

예제 입력값인 2 7 4 1 5 3을 정렬하면 1 2 3 4 5 7이 되는데, 만약 앞에서부터 포인터를 움직여서 합이 9가 되는 수를 고른다면 2번째 포인터가 7까지 이동하고, 1번째 포인터가 2로 이동한 단 한 가지의 경우 밖에 구할 수 없다.

 

따라서 이번에는 서로 최소값과 최대값에서 서로 마주보고 출발한다.

 

1번 포인터가 1, 2번 포인터가 7에 있는 경우를 (1, 7)이라고 표기하겠다.

(1, 7)은 우리가 구하려는 9보다 작다. 따라서 작은 쪽에 위치한 포인터를 움직인다. 그러면 (2, 7)로 원하던 값인 9가 나온다.

값이 같은 경우 어떤 값을 움직이던지 그것은 본인 마음대로 하면 된다.

 

만약 좌측 포인터를 움직일 경우 (3, 7)로 우리가 구하려는 9보다 크다. 따라서 큰 쪽에 위치한 우측 포인터를 움직인다.

이렇게 반복할 경우 (3, 5) = 8, (3, 4) =7, (3 , 4 혹은 4, 4) == 값이 같아졌으므로 종료.

..라는 식으로 코드를 작성하면 손쉽게 해결할 수 있다.

 

쉬운 문제니까 답을 보지 말고 직접 풀자.

답은 아래에 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        long M = Long.parseLong(br.readLine());
 
        long[] arr = new long[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
 
        int start_index = 0;
        int end_index = N-1;
        long sum = 0;
        int answer = 0;
 
        while (start_index<end_index) {
            sum = arr[start_index] + arr[end_index];
            if (sum==M) {
                answer++;
                end_index--;
            }
            if (sum>M) {
                end_index--;
            }
            if (sum<M) {
                start_index++;
            }
        }
 
        System.out.print(answer);
    }
}