반응형

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

 

 

문제


코드

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

public class bj_3273 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int x = Integer.parseInt(br.readLine());

        int result = 0;

        Arrays.sort(arr);
        int start = 0;
        int end = n - 1;

        while (start < end) {
            int sum = arr[start] + arr[end];

            if (sum == x) {
                result++;
                start++;
                end--;
            } else if (sum > x) {
                end--;
            } else {
                start++;
            }
        }

        bw.write(result + "\n");
        bw.close();
        br.close();
    }
}

풀이

 

1.  수열을 정렬한다.

Arrays.sort(arr);

 

 

2.  두 개의 포인터(startend)를 사용하여 두 수의 합을 확인하면서 적절히 이동시킨다.

  • 두 수의 합 == x인 경우에는 resultstart를 1 증가시키며, end에 1 감소시킨다.
    • 서로 다른 양의 정수로 이루어진 수열이기 때문에 startend의 값을 유지할 필요가 없다.
  • 두 수의 합 > x인 경우에는 end를 1 감소시킨다. 
    • 정렬시킨 상황이기 때문에 큰 값인 end를 감소시킨다.
  • 두 수의 합 < x인 경우에는 start를 1 증가시킨다.
    • 정렬시킨 상황이기 때문에 작은 값인 start를 증가시킨다.
int start = 0;
int end = n - 1;

while (start < end) {
    int sum = arr[start] + arr[end];

    if (sum == x) {
        result++;
        start++;
        end--;
    } else if (sum > x) {
        end--;
    } else {
        start++;
    }
}

 

 

 

 

 

반응형

'백준' 카테고리의 다른 글

[백준] 2630 : 색종이 만들기  (0) 2025.03.05
[백준] 2805 : 나무 자르기  (0) 2025.02.24
[백준] 18870 : 좌표 압축  (0) 2025.02.20
[백준] 11726번 : 2×n 타일링  (0) 2025.02.19
[백준] 15686번 : 치킨 배달  (0) 2025.02.18