[BOJ] 백준 1253 좋다 - Python/Java

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

1253번: 좋다

 

해설

주어진 N개의 수 중에서 임의의 숫자 K가 서로 다른 두 숫자 P, Q의 합으로 표현이 되면 K를 "좋다(Good)"이라고 하며, 좋은 수의 개수를 구하는 것이 문제의 목표인데요.

 

저는 이분 탐색을 이용해서 문제를 풀었습니다. 파이썬은 bisect 라이브러리를 이용했고, 자바같은 경우 직접 리스트에서 찾고자 하는 숫자가 들어갈 수 있는 lowerBound, upperBound를 구하는 함수를 짰습니다.

 

그렇다면 보다 구체적으로 i번째 숫자가 "좋다"인지 확인하려면 어떻게 해야할까요?

 

우선 i번째 수를 제외한 모든 j번째 수에 대해 타겟값을 numbers[i] - numbers[j]로 설정합니다. 그러면 우선 i번째 수를 만드는 다른 수 하나는 numbers[j]로 고정한 것이죠. 그리고 전체 숫자 리스트에서 target값이 들어가는 left, right 인덱스를 찾는데요. 이 때, 해당 구간 안에 i와 j를 포함하지 않는 숫자들만 찾아서 리턴했을 때 해당 리스트의 길이가 1보다 크거나 같으면 임의의 다른 수 하나를 더 찾을 수 있다는 뜻이기 때문에 numbers[i]는 "좋다"임을 알 수 있습니다.

 

말로 설명하는 것보다 코드와 주석을 보는 게 더 좋을 것 같습니다.

 

[풀이 - 파이썬]

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def findTargetRange(numbers, target, i, j):
    left = bisect_left(numbers, target)
    right = bisect_right(numbers, target)
    return [idx for idx in range(left, right) if idx != i and idx != j]
    
answer = 0
n = int(input())
numbers = list(map(int, input().split()))
numbers.sort() # 오름차순 정렬

for i in range(n):
    for j in range(n):
        # 다른 두 수의 합으로 나타낸다 -> i, j는 달라야함
        if i == j: continue
        target = numbers[i] - numbers[j]
        # 주어진 배열에서 i, j를 제외하고 target값이 존재하는지 확인
        result = findTargetRange(numbers, target, i, j)
        if len(result) >= 1:
            answer += 1
            break
print(answer)

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class B_1253 {
    static ArrayList<Integer> numbers;
    static int answer;

    private static int lowerBound(ArrayList<Integer> data, int target) {
        int left = 0; int right = data.size();
        while(left < right) {
            int mid = (left + right) / 2;
            if(data.get(mid) >= target) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return right;
    }

    private static int upperBound(ArrayList<Integer> data, int target) {
        int left = 0; int right = data.size();
        while(left < right) {
            int mid = (left + right) / 2;
            if(data.get(mid) <= target) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return right;
    }

    public static ArrayList<Integer> findTargetRange(ArrayList<Integer> numbers, int target, int i, int j) {
        ArrayList<Integer> result = new ArrayList<>();
        int lowerBound = lowerBound(numbers, target);
        int upperBound = upperBound(numbers, target);
        for(int n = lowerBound; n < upperBound; n++){
            if(n != i && n != j) result.add(n);
        }
        return result;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 숫자 입력받기
        numbers = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            numbers.add(Integer.parseInt(st.nextToken()));
        }
        // 정렬
        Collections.sort(numbers);

        for(int i = 0; i < n ; i++){
            for(int j = 0; j < n; j++){
                // 다른 두 수의 합으로 나타내야 하므로 i != j
                if(i ==j) continue;
                int target = numbers.get(i) - numbers.get(j);
                // 주어진 배열에서 i, j를 제외하고 target이 존재하는지 확인
                ArrayList<Integer> result = findTargetRange(numbers, target, i, j);
                if(result.size() >= 1){
                    answer += 1;
                    break;
                }
            }
        }
        System.out.println(answer);

    }
}