[Java] 백준 1253번 - 좋다

문제 링크 : 백준 1253번 - 좋다 자바

 

"좋은 수"라 함은, 어떤 수가 다른 두 수의 합으로 나타낼 수 있을 때 좋은 수라고 한다.

입력으로 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 들어왔을때

1은 다른 두 수의 합으로 나타낼 수 없으므로 좋은 수가 아니다.

2도 다른 두 수의 합으로 나타낼 수 없으므로 좋은 수가 아니다.

3은 1+2로 나타낼 수 있으므로 좋은 수다.

4는 1+3으로 나타낼 수 있으므로 좋은 수다.

5는 1+4 또는 2+3으로 나타낼 수 있으므로 좋은 수다.

...

3,4,5,6,7,8,9,10은 좋은 수다.

 

정렬과 투 포인터 개념을 이용하여 풀이한다.

투 포인터를 활용한 이전에 포스팅했던 백준 1940번 문제를 복습하자. 이 문제에 적용된 코드를 거의 그대로 가져다 쓸 것이다.

 

1940번과 다른점은, 좋은 수라고 판별되면 더 이상 탐색을 하지 않아도 되는 것이다.또한 자기 자신의 수(현재 좋은수인지 판별하는 수)는 start와 end에서 제외하는 것이다.

 

아래 코드를 보면서 이해해보자.

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

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());
        int[] list = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 투 포인터 개념을 적용하기 위해 입력받은 배열을 정렬해준다.
        Arrays.sort(list);
        // 좋은 수 개수를 나타내기 위한 카운트
        int count = 0;
        // 배열을 모두 탐색한다. foreach문으로 바꾸면 간략해질 수 있을 것 같다.
        for (int i = 0; i < list.length; i++) {
        	// 투 포인터 개념에서의 start와 end를 지정해준다.
            // 모든 배열에 대해 탐색하므로 start와 end는 for문 밑에 선언하여 탐색하는 수마다 초기화되어야 한다.
            // 즉, 탐색하는 수 마다 투 포인터를 각각 탐색한다.
            int start = 0;
            int end = list.length - 1;
            // 1940번 문제와 비슷한 코드.
            while (start < end) {
            	// 자기 자신의 수는 포함하면 안되므로, 위치를 가감해주고
                // if문 아래는 실행할 필요가 없으므로 continue로 처리해준다.
                if (start == i) {
                    start++;
                    continue;
                } else if (end == i) {
                    end--;
                    continue;
                }
                int sum = list[start] + list[end];
                // list[i]가 "좋은 수"라면, count를 증가시키고
                // while문을 빠져나가 다음 수를 탐색한다.
                if (sum == list[i]) {
                    count++;
                    break;
                // 아니라면 적절한 조치를 취해준다.
                } else if (sum > list[i]) {
                    end--;
                } else start++;
            }
        }

        System.out.println(count);
    }
}