출처
https://www.acmicpc.net/problem/1253
문제
N개의 수가 주어질 때, 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 그것을 좋은수라고 하는데, 그 갯수를 구하는 문제이다.
풀이
먼저, 당연한 말이지만 주어진 N개의 수가 3개 미만이라면, 다른 두 수가 없기때문에 좋은수가 될 수 없다.
다른 두 수를 이용해 합으로 나타낼 수 있는지 알아보려면, 투 포인터 개념을 활용하여 직접 비교해보는 방법 밖에 없다.
하지만 모든 경우를 다 무작정 비교하게 되면, 기준이 되는 원소를 고르는 for문 하나, i j 인덱스를 통해 합이 성립하는지 확인하기 위한 for문이 2개, 총 3개의 반복문을 가진다. N^3 복잡도를 가진 코드는 매우 비효율적인 알고리즘이며 사용하지 않아야 한다.
그렇기 때문에 우리는 이것을 단순 무식하게 모두 돌지 않고 중간에 조건을 추가해주어 효율적으로 비교할 수 있도록 해야한다.
투 포인터를 활용하기 위해서는 먼저, 정렬이 선행되어야 한다. 그래야 효율적으로 투 포인터 활용 로직을 구성할 수 있기 때문이다.
정렬이 되었다면 주어진 수 중 제일 작은 수를 i로, 제일 큰 수를 j로 두어 탐색을 시작한다. 왜 기준원소의 앞인 k-1을 j로 하지 않는가? 만약 기준원소 k가 7이고 j가 8이라면 더해서 작아질일이 없지 않은가? 라고 생각했다면 문제를 다시 한번 살펴야 한다. 위 질문에 대한 답은 바로 양수만 주어지는 것이 아닌, 음수 또한 주어지기 때문이다. k가 7이고 j가 8이라면, i가 -1인 경우에는 좋은수가 될 수 있다. 아래 예시를 생각해서 풀어보면 좋을 것이다.
8
-1 0 2 3 5 6 7 9
만약 i번째와 j번째 원소의 합이 기준원소인 K보다 크다면? K보다 오른쪽에 위치한(큰 쪽에 위치한) j를 줄여가며 탐색을 진행하고, 만약 반대로 K보다 작다면 i를 올려가며 탐색을 진행하면 K와 가까워질 수 있다.
이제 코드를 보며 이해하면 훨씬 쉬울 것이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
arr = new int [N];
int answer = 0;
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
for (int x = 0; x < N; x++) {
int i = 0;
int j = N-1;
while (i < j) {
if (arr[i] + arr[j] == arr[x]) {
if (i != x && j != x) {
answer++;
break;
} else if (i == x) {
i++;
} else {
j--;
}
} else if (arr[i] + arr[j] > arr[x]) {
j--;
} else {
i++;
}
}
}
bw.write(answer + "\n");
br.close();
bw.flush();
bw.close();
}
}
'Algorithm' 카테고리의 다른 글
Java - [프로그래머스]42627 - 디스크 컨트롤러 (1) | 2024.07.10 |
---|---|
Java - [프로그래머스]60057 - 문자열 압축 (0) | 2024.07.02 |
Java - [프로그래머스]42579 - 베스트앨범 (0) | 2024.07.02 |
Java - [BOJ]2565 - 전깃줄 (0) | 2024.06.20 |
Java - [프로그래머스 Lv.2]72411 - 메뉴 리뉴얼 (2) | 2024.04.18 |