강의 듣기 전에 문제 풀어서 정답은 나왔는데....
273
9 câu hỏi đã được viết
강의 듣기 전에 먼저 풀어서 정답은 나왔는데,
제 풀이가 이중for문과 뭐가 달라서 시간복잡도가 줄어든 건지 모르겠습니다(왜 정답이 나왔는지가 궁금합니다).
for 문 안에 while문을 넣으면서 반복문(반복문) 형태니까 n^2이어야 할 것 같은데 이중 for문 대비 시간이 줄어든 이유가 무엇일까요?
import java.util.*;
class Main{
public int solution(int n, int m, int[] numArray) {
int answer = 0;
int sum = 0;
int lt = 0;
for(int i=0; i<n; i++) {
sum = numArray[i];
lt = i;
if(sum > m) {
continue;
} else {
sum -= numArray[i];
while(sum<=m && lt<n) {
sum += numArray[lt++];
if(sum==m) {
answer++;
break;
}
}
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] numArray = new int[n];
for(int i=0; i<n; i++) {
numArray[i] = in.nextInt();
}
in.close();
System.out.print(T.solution(n, m, numArray));
}
}
Câu trả lời 3
0
댓글로 질문드린 이후로 제가 생각한 답은 이렇습니다.
이렇게 이해해도 괜찮을까요?
--> for문의 경우 항상 n번을 돌아야 하지만,
while문의 경우 조건에 따라 n번 미만으로 돌 수 있고
결국 n * (n 미만의 어떤 수) 가 되므로 O(n^2)이 아니라 O(n)이 된다.
풀이에서 보면 while문을 썼을 때는 연속부분수열의 합이 M이 되는 순간 멈추기 때문에 n번을 다 돌지 않고 중간에 멈추게 되고, 그래서 이중 for문 대비 시간이 줄어든 것이다.
답변 부탁드립니다! 감사합니다.
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
34
2
갑자기 채점 사이트가 바뀌었어요
0
35
1
문제 리스트 페이지
0
30
1
채점 사이트 관련 질문드립니다
0
24
1
봉우리 문제 질문입니다
0
85
2
씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?
0
66
0
이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?
0
72
0
가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법
0
68
1
좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ
0
85
2
6-7 강의에서
0
48
1
6-6. 장난꾸러기 질문 있습니다.
0
46
1
강의 수강후 코딩테스트
0
111
1
answer 변수 사용 여부
0
47
1
2중 for문
1
85
2
2-11. 임시반장정하기 (Runtime Error)
0
63
1
혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?
0
70
1
이런 풀이는 어떨까요
0
44
1
자바 스트림 방식의 효율성 질문 드립니다.
0
58
1
알고리즘 자료 구조들..
0
63
1
StringBuilder vs BufferdWriter
0
48
1
원더랜드(프림)
0
50
1
이런 코드는 어떤가요?
0
62
1
bfs 풀이
0
57
1
병합정렬
0
58
1

