반응형
4. 연속 부분수열
연속 부분수열 N개에서 합이 자연수 M이 되는 경우 횟수 구하기
입력값
8 6
1 2 1 3 1 1 1 2
출력값
3
(1)
1. while (p1 < n)
합계에 p1이 가리키는 값을 더한다.
2. while (p2 < n&&sum<=m)
p2가 n보다 작고, 합계가 m보다 작거나 같을 경우 계속 반복해 p2가 가리키는 값을 합계에 넣는다.
3. if (sum == m)
합계가 m이 되는 경우 결과값에 +1한다.
package twopointer.ch03;
import java.util.Scanner;
//연속 부분수열
class Twopointer04_1 {
static int[] arr;
public int solution(int n, int m) {
int p1 = 0;
int p2 = 1;
int sum = 0;
int answer = 0;
while (p1 < n) {
sum += arr[p1];
while (p2 < n&&sum<=m) {
sum += arr[p2];
p2++;
if (sum == m) {
answer++;
}
// if (sum > m) {
// break;
// }
// sum<=m조건 대신 사용 가능
}
sum = 0;
p1++;
p2 = p1 + 1;
}
return answer;
}
public static void main(String[] args) {
Twopointer04_1 T = new Twopointer04_1();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = kb.nextInt();
}
System.out.println(T.solution(n, m));
}
}
(2)
1. while문 사용하지 않고, for문 한번으로 구현
2. m보다 크면 초기화 시키고, 시작점을 +1
3. m이 되면, 시작점을 빼고 다음 값부터 추가
//특정 연속 부분수열의 합
import java.util.Scanner;
public class Main {
public int solution(int[] arr , int m) {
int answer=0;
int tmp=0;
int p1=0;
for(int i=0;i<arr.length;i++) {
tmp+=arr[i];
if(tmp==m) {
answer++;
tmp-=arr[p1];
p1++;
}else if(tmp>m) {
tmp=0;
i=p1++;
}
}
return answer;
}
public static void main(String[] args) {
Main T =new Main();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int m=kb.nextInt();
int [] arr =new int [n];
for(int i=0;i<n;i++) {
arr[i]=kb.nextInt();
}
System.out.println(T.solution(arr,m));
}
}
+) 세련된 풀이
1. for (int rt = 0; rt < n; rt++) {
포인터2가 n까지 반복하면서 포인터2의 값을 합계에 저장
2. if (sum == m)
//합계에 저장하는데 포인터가 1증가할때마다, 합계와 원하는 값의 크기를 비교한다.
(1) 원하는 값일 경우 -> 결과에 +1
(2)아닌 경우 -> 맨 앞의 값부터 빼고, 포인터를 증가시키면서 추가
3.while (sum > m)
합계가 m보다 크면 계속 반복하면서, 합계에서 포인터1의 값을 빼고, 포인터1에 +1
포인터1은 항상 +1씩 커지고, 포인터2는 합계가 m보다 커지면 포인터1이 가리킨 순서대로, 하나씩 빼서 다음값을 더한다.
4. if (sum == m)
원하는 값이 되면, 결과에 +1
package twopointer.ch03;
import java.util.Scanner;
public class Twopointer04 {
// 연속부분수열
// 연속 부분수열 N개에서 합이 M이 되는 경우 횟수 구하기
public static void main(String[] args) {
Twopointer04 T = new Twopointer04();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
int[] arr = new int[8];
for (int i = 0; i < n; i++) {
arr[i] = kb.nextInt();
}
System.out.println(T.solution(n, m, arr));
kb.close();
}
public int solution(int n, int m, int[] arr) {
// 1.ds
int answer = 0, sum = 0, lt = 0;
// 결과, 합계, 포인터1
// 2.for, while
for (int rt = 0; rt < n; rt++) {
// 포인터2가 n까지 반복
sum += arr[rt];
// 포인터2의 값을 합계에 저장
//합계에 저장하는데 포인터가 1증가할때마다, 합계와 원하는 값의 크기를 비교한다.
//(1) 원하는 값일 경우 (2)아닌경우 -> 맨 앞의 값부터 빼고, 포인터를 증가시키면서 추가
if (sum == m)
answer++;
// 원하는 값이 되면, 결과에 +1
while (sum > m) {
// 합계가 m보다 크면 반복
sum -= arr[lt++];
// 합계에서 포인터1의 값을 빼고, 포인터1 +1
if (sum == m)
answer++;
// 원하는 값이 되면, 결과에 +1
}
}
return answer;
}
}
더보기
package twopointer.ch03;
import java.util.Scanner;
public class Twopointer04_4 {
public int solution(int n, int m, int[]arr) {
int answer=0, sum=0, lt=0;
//lt기준이 아니라 rt기준으로 for문 -> rt는 항상 증가하지만, lt는 특정 조건에서 뺴야하므로
for(int rt=0;rt<n;rt++) {
sum+=arr[rt];
if(sum==m) {
answer++;
}
//rt를 추가하면, m과 같은지 항상 확인 -> sum: lt부터 rt까지의 합
//sum>m인 경우
while(sum>m) {
sum-=arr[lt++];
//lt++ : 뺀 다음에 증가, ++lt : 증가한 후에 뺀다.
//뺀 다음에 같은지 확인
if(sum==m) {
answer++;
}
}
//1 1 1 1 5 같은 경우처럼, lt를 여러번 빼야되는 경우도 존재하므로, while문 사용
}
return answer;
}
public static void main(String[] args) {
Twopointer04_4 T = new Twopointer04_4();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int m=kb.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++) {
arr[i]=kb.nextInt();
}
System.out.println(T.solution(n,m,arr));
}
}
1. 하나씩 추가하면서 원하는 수와 같은지 체크한다.
2. 원하는 수보다 크면, 작아질때까지 앞에서부터 자른다. [자를때마다 원하는 수와 같은지 확인]
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
System.out.println(solution(n,m,arr));
}
static int solution(int n, int m, int[]arr){
int answer=0;
int sum=0;
int lt=0;
for(int i=0;i<n;i++){
sum+=arr[i];
if(sum==m) answer++;
while(sum>m){
sum-=arr[lt];
lt++;
if(sum==m) answer++;
}
}
return answer;
}
}1. for-while문 이용
(1) 총합이 작으면 반복해서 추가
import java.util.Scanner;
public class Main {
public static void main(String[] args){
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();
}
//target값보다 크지 않으면 계속 반복
int answer=0;
for(int i=0;i<n;i++){
int tmp=arr[i];
int rt=i+1;
while(tmp<k && rt<n){
tmp+=arr[rt];
if(tmp==k) answer++;
rt++;
}
}
System.out.println(answer);
}
}
(2) 총합이 크면 반복해서 빼기
import java.util.Scanner;
public class Main {
public static void main(String[] args){
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();
}
//target값보다 크면 계속 반복
int answer=0;
int sum=0;
int 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++;
}
}
System.out.println(answer);
}
}
+) 03.02
import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[]arr =new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
Main main = new Main();
System.out.println(main.solution(arr, m));
}
public int solution(int[] arr, int m){
//m보다 작으면 더하고, 같으면 추가하고, 크면 맨앞 뺀다.
int p=0;
int result=0;
int answer=0;
for(int i=0;i<arr.length;i++){
result+=arr[i];
if(result==m) answer++;
while(result>m){
result-=arr[p++];
if(result==m) answer++;
}
}
return answer;
}
}반응형
'Java > Java 알고리즘 인프런' 카테고리의 다른 글
| [Ch.01 - String] 01. 문자 찾기 (+ toCharArray) (0) | 2022.05.12 |
|---|---|
| [Ch.03 - 투 포인터] 6. 최대 길이 연속부분수열 ### (0) | 2022.05.09 |
| [Ch.03 - 투 포인터] 5. 연속된 자연수의 합 # (+ for-while) (0) | 2022.05.09 |
| [Ch.03 - 투 포인터] 3. 최대 매출 (+ 슬라이딩 윈도우) (0) | 2022.05.09 |
| [Ch.03 - 투 포인터] 2. 공통원소 구하기 (+하나씩 확인하는 방법) (0) | 2022.05.09 |