[백준] 1940_주몽 - JAVA
백준_1940
1940번: 주몽
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고
www.acmicpc.net
투 포인터
투 포인터에 대한 설명은 아래 링크를 참고
[백준] 2018_수들의 합5 - JAVA
백준_2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타
devhan.tistory.com
이 문제는 두 재료의 번호의 합을 구하고 크기를 비교하는 문제라 받을 배열을 정렬하여 풀면 굳이 이중 반복문을 사용하지 않을 수 있는 문제다. 이 문제도 투 포인터를 사용하여 풀이하는 문제인데, 먼저 투 포인터의 이동 원칙에 대해 알아보자.
투 포인터 이동 원칙
arr[i] + arr[j] > n 이면 j--;
arr[i] + arr[j] < n 이면 i++;
arr[i] + arr[j] == n이면 i++; j--; count++;위 원칙을 생각하면서 아래 과정을 살펴보자.
이 전에 풀었던 투 포인터는 두 개의 투 포인터 모두 배열 앞쪽에서 시작했다. 이번 문제의 투 포인터는 하나는 배열의 맨 앞, 다른 하나는 배열의 맨 뒤에서부터 시작한다.
투 포인터의 이동 원칙해 따라서 위 배열을 계산해보자. arr[i]는 1, arr[j]는 7이다. 둘이 더하면 8이된다. 8은 n인 9보다 작으므로 i++ 코드가 실행된다.
그 다음 반복문에서는 arr[i]가 2, arr[j]가 7이다. 두 개를 더하면 9이고, n과 똑같다. 그러므로 i++, j--, count를 ++ 해주면 된다.
이렇게 반복을 열심히 돌다가 i와 j가 맞닿아있는 시점에 반복문을 종료하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder(st.toString());
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int maxN = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int count = 0;
int i = 0;
int j = n - 1;
while(i < j) {
if(arr[i] + arr[j] < maxN) i++;
else if(arr[i] + arr[j] > maxN) j--;
else {
count++;
i++;
j--;
}
}
System.out.println(count);
}
}제출 결과
