• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

2-T. 번 강의 질문 스택 풀이시 시간복잡도

24.02.07 00:15 작성 조회수 212

0

안녕하세요.

강의 잘듣고잇습니다.

 

단순하게 풀엇을떄 2중 forloop 시간복잡도 O(N^2) . 시간초과 발생하였습니다.

 

스택 풀이로 하면 통과는 하게되는데,

시간복잡도는 여전히 O(N^2). 인 것 아닌가요?

답변 3

·

답변을 작성해보세요.

0

안녕하세요 ㅎㅎ

그게 아니고, N+N 이 되는걸까요?

>> 네 맞습니다. 예를 들어 최악의 경우를 생각해봤을 때 저 while문이 최대치로 도는 경우는... 계속해서 pop이 안되는 경우겠죠.

그렇다면 for문으로 N번 돌았을 때 그대로 stack에는 N개가 쌓이다가 마지막 N개에서 POP을 하게 됩니다.

이경우 FOR문 N번, STACK에 쌓인 N개의 요소들을 POP하게 되어 총시간복잡도 2N = O(N)이 되게 됩니다.

 

감사합니다.

감사합니다. 큰 도움 되었습니다.

0

안녕하세요!!

만약 4,3,2,5 라는 입력이 주어지면

스택에 3개가 쌓이고, 쌓인 스택에서 while 문을 통해 순서대로 ret 배열에 값을 넣어주게 되니까 N^2 이라 생각했는데

 

그게 아니고, N+N 이 되는걸까요?

감사합니다.^^

0

안녕하세요 성욱님ㅎㅎ

 

시간복잡도는 여전히 O(N^2). 인 것 아닌가요?

>>

	for(int i = 0; i < n; i++){
		cin >> a[i];  
		while(s.size() && a[s.top()] < a[i]){
			ret[s.top()] = a[i]; s.pop();
		}
		s.push(i);
	}

음.. 혹시 이게 N^2라고 생각하시는 이유가 있으실까요?

 

감사합니다.

채널톡 아이콘