[백준 / 배열] 3273번 : 두 수의 합 - (JAVA/자바)

📝 문제

백준 3273번 : 두 수의 합

 

💭 풀이 방법

for 문을 2번 돌려서 푸는 문제구나 ! 라고 하고 풀었지만 시간 초과가 발생했습니다 ..

찾아보니 이 문제는 투 포인터 를 이용해서 푸는 문제더라구요 !

 

투 포인터란 ? 선형 시간 O(n) 으로 알고리즘을 풀 수 있게 해주는 알고리즘입니다. 

배열이나 리스트에서 두 개의 포인터를 이용해서 특정 조건을 만족하는 부분 구간을 효율적으로 탐색할 수 있습니다. 

일반적으로 배열이나 리스트가 정렬되어 있을 때 사용됩니다. 

 

간략한 알고리즘은 이렇습니다. 

1. 배열을 먼저 정렬해준다. 
2.  start 는 배열의 맨 앞을, end 는 배열의 맨 뒤를 가리킨다.
3. arr[start] + arr[end] 를 해서 원하는 값이 나오면 최종 count 할 수 있는 변수를 증가시킨다. 
4. arr[start] + arr[end] 가 원하는 값과 같거나 원하는 값보다 크다면 end 를 한 칸 앞으로 이동한다. 
5. arr[start] + arr[end] 를 해서 원하는 값보다 작은 값이 나올 경우에는 start 를 뒤로 한 칸 이동한다.  

 

백준 예제 입력1 을 기반으로 문제 풀이 시작하겠습니다. 

 

우선 배열로 입력받은 값을 먼저 정렬해줍니다. (Arrays.sort() 사용)

 

 

맨 처음 0번 인덱스를 start 가 가리키고, 맨 마지막 8번 인덱스를 end 가 가리키게 설정해줍니다. 

 

 

문제에서 조건이 ai + aj = x 를 만족하는데 (1 <= i < j <= n) 이므로 while 반복문을 돌릴 때 end 가 start 보다 크다는 조건을 걸어줘야합니다. 

 

arr[start] + arr[end] = 13이므로 원하는 값이 되었습니다. 따라서 count 해주는 변수를 증가시킵니다. 

arr[start] + arr[end] 의 값이 원하는 값과 같으므로 end 의 위치를 한 칸 앞인 7번 인덱스로 이동시킵니다. 

 

여기서 end 를 한 칸 앞으로 이동시키는 이유는 배열이 정렬되어있기 때문에 원하는 값과 같거나 큰 경우 start 를 뒤로 이동시키면 무조건 더 큰 값밖에 얻지 못하기에 원하는 값은 절대 얻을 수 없습니다. 

따라서 end 를 한 칸 앞으로 이동시켜 arr[end] 의 값을 더 작게 만들어줘야 합니다. 

 

arr[start] + arr[end] 를 하면 이제 12 값이 됩니다. 12 는 원하는 값인 13보다 작은 값이므로 start 를 한 칸 뒤로 이동시켜야 합니다.  

 

 

arr[start] + arr[end] 의 값이 원하는 값보다 작을 경우 start 를 뒤로 이동시키는 이유는 배열은 정렬되어있으므로

이미 원하는 값보다 작은데 end 를 이동시켜봤자 더 작은 값만 얻게됩니다. 따라서 원하는 값을 절대 얻을 수 없습니다. 

따라서 start 를 뒤로 이동시켜 arr[start] 의 값을 더 크게 만들어줘야 합니다. 

 

이런 방식으로 원하는 값과 같거나 크다면 end 를 앞으로, 원하는 값보다 작을 경우 start 를 뒤로 이동시키며 문제를 해결하시면 됩니다.  

😊소스코드

package 백준.Array;

import java.util.Arrays;
import java.util.Scanner;

//백준 3273번 (투 포인터를 사용하는 문제)
public class 두_수의_합 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int capacity = scanner.nextInt();
        int [] arr = new int[capacity];
        int totalCount = 0;
        for (int i = 0; i < capacity; i++) {
            arr[i] = scanner.nextInt();
        }

        int sum = scanner.nextInt();

        Arrays.sort(arr);
        int start = 0; //제일 첫 번째 인덱스
        int end = arr.length-1; //제일 마지막 인덱스

        while (start < end) {
            int target = arr[start] + arr[end];
            if (target == sum) {
                totalCount++;
            }
            if (target >= sum) {
                end--;
            } else if (target < sum) {
                start++;
            }
        }
        System.out.println(totalCount);
    }
}

 

---