Binaryseop
[백준 1940] 주몽 Java 풀이 본문
접근
n이 최대 15,000이므로 이중 for 문을 이용하여 문제를 풀 경우 시간 복잡도가 O(n^2)이 될 것으로 예상됩니다. 따라서 투 포인터를 이용한다면 시간 복잡도를 O(n)으로 줄일 수 있습니다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 처리
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 1. 배열 arr를 오름차순으로 정렬한다.
Arrays.sort(arr);
// 2. 투 포인터를 이용하여 만들 수 있는 갑옷의 개수를 구한다.
int i = 0, j = n - 1;
int cnt = 0;
while (i < j) {
if (arr[i] + arr[j] < m) {
i++;
} else if (arr[i] + arr[j] > m) {
j--;
} else {
cnt++;
i++;
j--;
}
}
// 결과 출력
System.out.println(cnt);
}
}
'알고리즘' 카테고리의 다른 글
[백준 9024] 두 수의 합 Java 풀이 (1) | 2024.04.23 |
---|---|
[백준 2559] 수열 Java 풀이 (0) | 2024.04.22 |
[백준 2467] 용액 Java 풀이 (0) | 2024.04.21 |
[백준 2470] 두 용액 Java 풀이 (1) | 2024.04.21 |
[백준 7795] 먹을 것인가 먹힐 것인가 Java 풀이 (2) | 2024.04.19 |