카테고리

질문 & 답변
세부 분야

알고리즘 · 자료구조
해결 여부

미해결

강의 듣기 전에 문제 풀어서 정답은 나왔는데....

21.07.17 22:56 작성 조회수 158

강의 듣기 전에 먼저 풀어서 정답은 나왔는데,

제 풀이가 이중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));
	}
}