[백준] 1253번: 좋다 (Java)

문제 (Gold 4)

 

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

1253번: 좋다

---

풀이

배열의 값들을 하나씩 돌며, 투 포인터를 사용하여 해당 수가 좋은지 판별하였다.

문제에 나와있는 예시가 너무 자명하기 때문에 아래 예시로 생각하고 문제를 풀었다.

5
-2 0 1 2 3

1. 기본적으로 정렬을 진행해야 한다. 그렇지 않으면, 투포인터의 움직임에 따른 로직을 작성할 수 없다!
2. left, right 값을 설정해주는데, 정렬을 해주었다고 right값을 i-1로 해서는 안된다!
   -> 음수가 있어서 나보다 큰 수와 더해도 내가 나올 수 있는 상황이 있기 때문에
3. 각 포인터 값의 합이 나(numbers[i])보다 크다면, 더 작은 수와 더해야하므로 right값을 움직인다
   반대로 나보다 작다면, 더 큰 수와 더해야 하므로 left값을 움직인다.

 

코드

package implement;

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

public class BOJ_1253_좋다 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0 ; i < N ; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numbers);
        int result = 0;
        for(int i = 0 ; i < N ; i++){
            int left = 0;
            int right = N-1;    // 음수값이 있음에 유의!
            while(true){
                // 현재 나(i)의 위치에 있는 경우
                if(left == i) left++;
                else if(right == i) right--;

                // 결과를 찾을 수 없다.
                if(left >= right) break;

                // 정렬이 되어 있으므로, 합이 더 크다면 더 작은 수와 더해주어야 하니까 왼쪽으로 움직이는 right 값을 변경
                if(numbers[left] + numbers[right] > numbers[i]) right--;
                else if(numbers[left] + numbers[right] < numbers[i]) left++;
                else{      // 좋다!
                    result++;
                    break;
                }
            }
        }
        System.out.println(result);
    }

}

제출

처음에 완탐으로 계속 시도를 했는데, 몇일이 지나고 보니까 바로 풀이법이 생각낫다.