[JAVA50] 1253. 좋다

1253. 좋다 (G4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	56643	14480	10409	24.308 %

 

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

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

출력

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

.

---

summary

좋은 수 찾기

• 다른 두 수의 합으로 구해지는 수
• 동일한 값의 좋은 수는 따로 카운트 함
• 으

strategy

투 포인터 활용 

• N 은 2000 으로 이중 for 문 허용 (3중 for문은 시간초과 나기 때문에 브루트 포스 X)
• 배열의 수를 정렬
• 하나는 왼쪽부터 체크 (left)
• 하나는 오른쪽부터 체크 (right)
• 두 수가 자신인지 확인
• 두 수의 합이 비교하는 수보다 크면 오른쪽 포인터 왼쪽으로 이동 (sum > current : right--)
• 두 수의 합이 비교하는 수보다 작으면 왼쪽 포인터 오른쪽으로 이동 (sum < current : left++)
• 두 포인터가 만나면 종료 (while(left < right)
• 각 수마다 반복

note

• 1 ≤ N ≤ 2,000 
• |Ai| ≤ 1,000,000,000, Ai는 정수 (두 수의 합 int 범위 안 벗어남)

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

public class Main {

    static int N;
    static int answer = 0;
    static int board[];
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        board = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int n = 0; n < N; n++) {
            board[n] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(board); // 정렬

        // 투 포인터
        for(int n = 0; n < N; n++) {
            int current = board[n];

            int left = 0;
            int right = N-1;

            while(left < right) {
                if(left == n) { left++; continue; } // 왼쪽 포인터가 자신일 때
                if(right == n) { right--; continue; } // 오른쪽 포인터가 자신일 때
                
                int sum = board[left] + board[right];
                
                if(sum == current) { // 좋은 수
                    answer++;
                    break;
                } 
                else if(sum > current) right--; // 합이 더 큰 경우 오른쪽 포인터 좌측 이동
                else left++; 
            }
        }
        
        System.out.println(answer);
    }
}

 

문제	결과	메모리	시간	언어코드	길이
1253	맞았습니다!!	14860 KB	152 ms	Java 11 / 수정	1373

 

memo

• map 을 활용해서 반복 비교를 줄여볼까 했는데, 복잡해지는 거 같아서 일단 패스함
• '수의 위치가 다르면 값이 같아도 다른 수' 라는 뜻이 무슨 소리인가 잠시 고민함 
• 이분 탐색으로 푸는 방법도 있다고 함 O(N^2logN)