dearsanta   9달 전

현재 시간초과 뜨네요.

스택으로 O(n) 을 만들 수 있다고 하던데 저는 스택을 사용해도 O(n^2) 가 최대인 것 같습니다.

어디서 줄여야 할지 잘모르겠습니다.

도와주세요!

indioindio   9달 전

접근방법은 맞는 것 같은데

for (int temp = stack[top--]; temp > stack[top]&&top != -1;top--);

에서 무한루프를 도는 것 같네요.

dearsanta   9달 전

for (int temp = stack[top--]; temp > stack[top]&&top != -1;top--);

top 변수가  -1이 되지 않아서 무한루프를 돌게된다는건가요?

어떤 테스트 케이스일때 무한 루프를 도는지 잘모르겠습니다 ㅜㅜ 

그리고 답변감사드려요.


indioindio   9달 전

음 게시판에 코드를 복사하실 때 잘못 복사하신게 아니라면 예제 입력에서도 무한루프가 나옵니다.

dearsanta   9달 전

이상하네요... 

xcode가 이상한가 해서 웹 컴파일러에 컴파일 했는데 결과가 잘나오네요.  

어떤 문제 인지 잘모르겠습니다.

http://ideone.com/IuCpfi



indioindio   9달 전

아하 scanf("%d ") 때문에 손으로 입력했을 때는 무한루프를 도는 것 처럼 보였네요.

indioindio   9달 전

안에 있는 한 줄 짜리 포문이 스택의 맨 위의 입력이 방금 들어온 숫자보다 작아질 때까지 pop하는 것 맞나요?

dearsanta   9달 전

for (int temp = stack[top--]; temp > stack[top]&&top != -1;top--);


네 맞습니다.

방금 들어온 수는 스택에 push 되고 

int temp = stack[top—]; 에서 방금 들어온 수를 다시 pop하여 temp안에 넣고

temp가 스택 맨위의 수보다 작을 때까지  pop을 합니다.


indioindio   9달 전

음 그렇게 되면 top = i; 에 의해 stack의 유효 크기가 너무 커질 것 같습니다.

499999번째 수를 본다면, stack의 499999위치에 현재의 숫자가 들어가게 되고, 499999번 아래로 내려가야 합니다.

그런데 사실 스택에 실제로 있는 수는 그보다 훨씬 작겠죠.

스택의 크기와 현재 입력의 위치를 개별적으로 사용하시면 될 것 같네요.

댓글을 작성하려면 로그인해야 합니다.