[알고리즘] 1253번

오늘 풀어볼 문제는 백준 1253번 문제 "좋다" 이다.

이 문제는 골드4 문제이고 투 포인트 문제이다.

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. 
(|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

📌첫 번째 도전📌
앞 전에 투 포인트 문제를 어느 정도 풀어봐서 같은 방식으로 while 돌리고 조건문을 나눠서 코드를 짜면 된다고 생각했다.
첫 코드를 완성하면서 시간이 걸렸던 부분은 앞 전에 풀었던 문제들은 모두 while문 하나로 해결이 돼서 이 문제 또한 while문 하나로 최대한 해보려 했지만 불가능이었다.
그래서 for문을 하나 만들고 그 안에 while문을 넣었다.

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());

        int N = Integer.parseInt(st.nextToken());

        long[] arr = new long[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;

        for (int i=0; i<N; i++) {
            int start_index = 0;
            int end_index = N-1;
            while(start_index < end_index) {
                if(arr[start_index] + arr[end_index] == arr[i]) {
                    count++;
                    break;
                }
                else if(arr[start_index] + arr[end_index] < arr[i]) {
                    start_index++;
                }
                else if(arr[start_index] + arr[end_index] > arr[i]) {
                    end_index--;
                }
            }
        }

        System.out.println(count);
    }
}

잘 되나 싶었는데... 틀렸다...
어디서 틀렸는 지 알아보니깐 문제에서 "서로 다른 숫자의 합" 을 놓쳤다. 그렇기 때문에 만약 지금 구해야 하는 합이 i번째 값이라면 start와 end 인덱스는 모두 i와 달라야 한다. 그래서 안에 조건문을 더 추가로 넣어줬다.

📌두 번째 도전📌

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());

        int N = Integer.parseInt(st.nextToken());

        long[] arr = new long[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;

        for (int i=0; i<N; i++) {
            int start_index = 0;
            int end_index = N-1;
            while(start_index < end_index) {
                if(arr[start_index] + arr[end_index] == arr[i]) {
                    if(start_index != i && end_index != i) {
                        count++;
                        break;
                    }
                    else if(start_index == i) {
                        start_index++;
                    }
                    else if(end_index == i) {
                        end_index--;
                    }
                }
                else if(arr[start_index] + arr[end_index] < arr[i]) {
                    start_index++;
                }
                else if(arr[start_index] + arr[end_index] > arr[i]) {
                    end_index--;
                }
            }
        }

        System.out.println(count);
    }
}

성공했다 ㅎㅎ

[문제 출처] https://www.acmicpc.net/problem/1253