인프런 커뮤니티 질문&답변
작성한 질문수
두가지 질문이 있습니다.
작성
·
217
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
1. 선생님이 설명해주신 코드상에서는 , 부분합이 M보다 큰 경우
lt를 한칸 이동하고 - 부분합 수정 - 그럼에도 부분합이 계속 M보다 크면 -> lt를 계속 앞으로 이동시키셨는데요
그러면 lt가 rt보다 앞서서 lt와 rt 위치가 역전되는 경우가 발생하지 않는지 질문 드립니다.
예를 들어 M이 6인데 1 1 7 ... 인 경우
lt가 1 rt가 7을 가리키다가 lt가 결국 rt위치인 7까지 이동하는데,
그래도 7은 6보다 크니까 lt는 한칸 뒤로 이동할 텐데,
그러면 sum += arr[rt] 를 할때 lt가 rt보다 앞서서 잘못된 부분합이 계산되지는 않을지 질문 드립니다.
2. 이 문제는 결국 각 원소를 부분합의 시작 지점으로 했을 때,
부분합이 M이 되면 무조건 count하는데요,
만약 1, 2, 3, 1, 2, 3 이고 M이 6이면 {1,2,3}이 2번 count 될 텐데,
"수열" 이니깐 {1,2,3}이 2번 count되면 안되는 것은 아닌지 잘 모르겠습니다.
=> 이부분은 제가 너무 과하게 생각한 거 같기도 합니다...ㅎㅎ
답변 1
1
김태원
지식공유자
안녕하세요^^
네. lt가 rt보다 더 커지는 순간이 생길 수 있지만 그런 경우도 딱 lt가 1 더 커지지만 바로 rt가 증가해서 같아집니다. 그리고 부분수열은 집합이 아니기 때문에 위치에 의해서 구분됩니다.
아래 코드처럼 하시면 더 좋을 것 같습니다.
import java.util.*;
class Main {
public int solution(int[] nums, int m){
int answer=0;
int sum=0;
int lt=0;
for(int rt=0; rt<nums.length; rt++){
sum+=nums[rt];
while(sum>m){
sum-=nums[lt];
lt++;
}
if(sum==m) answer++;
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
int[] arr = new int[]{1, 2, 1, 2, 1, 2, 1};
System.out.println(T.solution(arr, 3));
}
}