inflearn logo
강의

Khóa học

Chia sẻ kiến thức

Giới thiệu về giải quyết vấn đề thuật toán Java: Chuẩn bị cho các bài kiểm tra mã hóa

4. Dãy con liên tục (Bài toán phức hợp)

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

273

beSlow

9 câu hỏi đã được viết

0

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

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

 

java 코테 준비 같이 해요!

Câu trả lời 3

0

beSlow

답변 감사합니다~ ^^!!

0

codingcamp

안녕하세요^^

프로그램 전체로 봐도 for문 안의 while문은 lt가 n까지 가면 멈추기 때문에 총 반복횟수는 n번밖에 반복하지 않습니다.

0

beSlow

댓글로 질문드린 이후로 제가 생각한 답은 이렇습니다.
이렇게 이해해도 괜찮을까요?

--> 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