-
[백준] 1806번 부분합 자바(Java)코딩 테스트 2025. 3. 25. 17:33
https://www.acmicpc.net/problem/1806
전형적인 투포인터 문제다.
투포이터는 O(N)의 시간복잡도를 갖는다. 시간제한이 0.5초인 이 문제에 사용하기 딱이다.
(사실 자바는 1초 제한.. ㅠ)import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; 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()); int N = Integer.parseInt(st.nextToken()); int S = Integer.parseInt(st.nextToken()); int[] arr = new int[N + 1]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) { arr[i] = Integer.parseInt(st.nextToken()); } int left = 0; int right = 0; int sum = 0; int ans = Integer.MAX_VALUE; while (right <= N && left >= 0) { if (sum >= S) { ans = Math.min(ans, right - left); sum -= arr[left++]; } else { sum += arr[right++]; } } if (ans == Integer.MAX_VALUE) { ans = 0; } System.out.println(ans); } }
[기억하자]
투 포인터
- O(n) 의 시간복잡도를 가진다.
- 구간합, 부분합 연산에 사용하기 적합하다.
- 이름이 비슷한(?) 이분탐색과는 차이가 크다. 투 포인터는 보통 연속된 구간의 특성을 활용하여 조건을 만족하는 구간을 찾고, 이분탐색은 특정 값을 찾기 위해 많이 사용되는 알고리즘이다.
'코딩 테스트' 카테고리의 다른 글
[프로그래머스] 징검다리 건너기 (자바) (0) 2025.03.28 [프로그래머스] 이모티콘 할인행사 (0) 2025.03.24 [프로그래머스] 표현 가능한 이진 트리 자바 (0) 2025.03.19 [백준] 우주신과의 교감 1774번 자바 (0) 2025.03.19 [백준] 26093 고양이 목에 리본 달기 (DP) (0) 2024.06.26