백준 1253 문제풀이

문제 링크

https://www.acmicpc.net/problem/1253

문제 설명

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

문제 분석

문제가 짧다고 만만하게 보면 안된다. 하지만 전의 문제와 같이 투포인터 알고리즘을 이용하여 문제를 해결하면 되겠다고 생각했다. 인덱스 범위를 초반, 그리고 끝범위로 지정을 해주고, targetNumber를 탐색하면 된다. left가 right보다 작은 동안 반복된다. (두 포인터가 교차하지 않을 때까지) 그리고 현재 left 포인터가 i와 같으면, 즉 현재 타겟 숫자와 같은 인덱스를 가리키면 left를 증가시켜서 그 인덱스를 건너뛴다. 이 경우는 현재 target과 같은 숫자를 더하지 않기 위해서이다. 합이 target과 같을 경우는 좋은 수를 찾은 것이므로 goodCount를 증가시키고 내부 루프를 종료한다. 합이 target보다 작을 경우는 left를 증가시켜서 더 큰 숫자를 찾도록 한다. 합이 target보다 클 경우는 right를 감소시켜서 더 작은 숫자를 찾도록 한다. 그리고 마지막으로 찾은 goodCount를 출력하면 끝.

코드

import java.util.*;
import java.io.*;

public class P1253 {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        List<Integer> list = new ArrayList<>();

        while (st.hasMoreTokens()) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(list);
        int goodCount = 0;

        for (int i = 0; i < n; i++) {
            int target = list.get(i);
            int left = 0;
            int right = n - 1;

            while (left < right) {
                // target과 같은 인덱스가 아닌 경우에만 합 계산
                if (left == i) {
                    left++;
                    continue;
                }
                if (right == i) {
                    right--;
                    continue;
                }

                int sum = list.get(left) + list.get(right);

                if (sum == target) {
                    goodCount++;
                    break;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        System.out.println(goodCount);
    }

Easy

Reference

https://www.geeksforgeeks.org/two-pointers-technique/