알고리즘/백준
[Java] 백준 수들의 합 2
문바리
2022. 8. 16. 20:55
728x90
1. 문제 분석
연속되는 수들의 합을 구하는 것이고 단순히 for문을 사용한다면 시간 초과가 나올 것이다.
이때 사용하는 것이 투포인터다. 2개의 start와 end를 통해 각 부분의 합을 구하는 것이다.
로직은 생각보다 간단하다. 만약 현재 합이 목표값 보다 작다면 end를 증가, 크거나 같다면 start를 증가를 하면 된다.
말로하는 것 보다 직접 하나씩 해보자.
테스트 케이스 1을 보자.
1 1 1 1이고 합이 2인 것을 찾아야 한다.
초기 상태다. 합인 sum이 목표값보다 작으니 end를 추가해야한다.
end를 추가한 상태다. 이제 arr[start] + arr[end]는 2가 된다. 목표값이 되었으니 start를 더해주고
sum에서 arr[start]를 빼준다(arr[start]는 더해주기 전 상태다.)
다시 합이 1인 상태로 돌아왔다. end를 더해줘야한다.
이처럼 계속 늘어나다가 end가 배열의 크기가 된다면 반복문을 종료하면 된다.
2. 구현
import java.io.*;
import java.nio.Buffer;
import java.util.*;
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());
int size = Integer.parseInt(st.nextToken());
int answer = Integer.parseInt(st.nextToken());
int[] arr = new int[size];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < size; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int result = 0;
int start = 0, end = 0, sum = 0;
//양끝에서 오는 투포인터는 정렬이 필요
//0부터 시작은 아님!
while (true) {
if(sum >= answer){
if(sum == answer){
result++;
}
sum -= arr[start++];
}
else{
if(end == size){
break;
}
sum += arr[end++];
}
}
System.out.println(result);
}
}
정말 위에서 말한대로 구현하면 끝이다. 딱히 설명할게 없다..
3. 마무리
예전에 풀었던 투포인터를 다시 풀어보니 너무 헷갈렸다.
답지를 보기보단 투포인터의 개념을 다시 잡고 풀어보니 할만했다.
반응형