1940번: 주몽
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고
www.acmicpc.net
접근법
투 포인터는 값이 정렬되어 있을 때 규칙을 찾기 편하다. 이 문제는 입력 값이 순차적으로 증가하지 않아 정렬을 해주고나서 투 포인터 방향에 대한 규칙을 세웠다. 맨 앞과 뒤 인덱스를 포인터 삼아 sum을 계산했다.
주의
처음 이 문제 0번째 인덱스를 비우고 1번부터 시작했는데 start = 0 end= N-1로 잡아 값이 잘못 나왔다. 0번째 인덱스를 비우고 1번 인덱스부터 시작했으려면 start=1로 end=N으로 잡아야지 올바르게 계산된다. 정렬이나 이런 인덱스를 활용하는 문제에서 0번째 인덱스를 포함시킬건지, 뺄건지에 따라 인덱스 설정을 잘해주자.
성능 요약
메모리: 15084 KB, 시간: 144 ms
분류 : 정렬(sorting), 두 포인터(two_pointer)
전체코드 (JAVA)
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int num = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
// 배열 초기화
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 순차 정렬 할 때 0인덱스 확인 잘하기 (배열크기랑), 배열크기 1크게 잡으면 인덱스 변화시켜야함
Arrays.sort(arr);
// start, end 투 포인터가 양 끝에서 시작
int start = 0;
int end = N-1;
int count = 0;
int sum = arr[start] + arr[end];
// 재료는 고유한 번호이기 때문에 똑같은 번호 불가
while( start < end) {
if(sum == num) { // start , end 둘 다 변화
end--;
start++;
count++;
}else if (sum < num) { // 값이 더 커져야 되는 상황 -> start 인덱스 증가
start++;
}else { // sum > num 값 더 줄여야 되는 상황 -> end 인덱스 감소
end--;
}
sum = arr[start] + arr[end]; // sum 갱신
}
System.out.println(count);
br.close();
}
}
공부자료 https://m.blog.naver.com/kks227/220795165570
투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)
조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다. 첫 번째로 소개해드릴 기법은 투 포인터(t...
blog.naver.com