[복합문제] 4. 연속 부분수열
설명
N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.
입력
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다.
예시 입력 1
8 6
1 2 1 3 1 1 1 2
예시 출력 1
3
<<풀이>>
-나의 풀이-
두 가지 방식으로 풀었던 우선 첫 번째,
시간 복잡도: O(N^2)
일단 나의 풀이이다.
ㅋㅋ 왜인지 모르겠지만, 현재 단원 자체가 O(N) 형식으로 도출해야 한다는 생각 + 복합적인 문제라고 했기에 sliding window , two pointers 이 두개를 써야 한다는 의무감인지 모르겠지만 머리가 굳었다 ㅋㅋ 도무지 이중 for문 밖에 생각이 안난다 ㅎㅎ..
그래서 사용했고, 정답은 맞췄다. ㅋㅋ
주요 기술은 크게 없고, 이중 for문 과 break 사용이다.
import java.util.*;
class Main {
public int solution(int N, int K, int[] arr) {
int answer = 0;
int count = 0;
for(int i = 0; i < N; i++) {
count = arr[i];
if (count == K) {
answer++;
}
for(int j = i + 1; j < N; j++) {
count += arr[j];
if(count == K) {
answer++;
break;
} else if (count > K) {
break;
}
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
int[] arr = new int[N];
for(int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
System.out.print(T.solution(N, K, arr));
}
}
두 번 째
시간 복잡도 O(N)
import java.util.*;
class Main {
public int solution(int N, int K, int[] arr) {
int lt = 0, rt = 0, count = 0, sum = 0;
while(lt < N && rt < N) {
sum += arr[rt];
if(sum == K) {
count++;
sum -= arr[lt++];
} else if (sum > K) {
sum -= arr[lt++];
}
rt++;
}
return count;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
int[] arr = new int[N];
for(int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
System.out.print(T.solution(N, K, arr));
}
}
근데, 이 방식으로 풀었을 때 답이 틀렸다. 원인은 솔직히 잘 모르겠당 ㅋㅋ 알거 같은데 오늘따라 해결이 잘 안되는거 같다.
-강사님 풀이-
일단 10만 정도까지는 괜찮지만 10만 위로 가는 경우 O(N^2)는 시간 초과 확률이 높아진다.
차근차근 흐름을 파악하게 되면 풀 수 있는 문제였다.
import java.util.*;
class Main {
public int solution(int N, int K, int[] arr) {
int answer = 0, sum = 0, lt = 0;
for(int rt = 0; rt < N; rt++) {
sum += arr[rt];
if(sum == K) answer++;
while(sum >= K) {
sum -= arr[lt++];
if(sum == K) answer++;
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
int[] arr = new int[N];
for(int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
System.out.print(T.solution(N, K, arr));
}
}
여기서 while을 if로 바꿀 수도 있지 않나?? 라는 생각을 해봤지만, 그렇게 풀 수도 있지만 아닌 경우도 있어 오답으로 된다. rt 값이 크다 보니 lt를 빼고 옮겨 가는 과정이 여러 번 있을 수도 있기 때문이다.
꾸준히 연습하자 이 문제 같은 경우는 한 번 더 풀 어 봤으면 좋겠다.!