dlqudgus2587   4년 전

25%에서 시간 초과로 막혔습니다.

스택을 하나 만들어서 입력 받은 수열을 스택에 넣고, Oken이라는 함수를 만들어서 한 번만 pop을 하고 그 이후 비교대상은 스택의 인덱스 값만 움직여서 pop한 수 와 비교를 했습니다.

질문 글에 있는 반례는 다 돌아가는데 어디서 시간을 단축시켜야 할지 잘 모르겠네요ㅠㅠ

아 그리고 원래는 Stack 구조체에서 int arr[1000000]; 이렇게 바로 배열을 선언했는데 stack overflow라며 에러가 뜨던데 배열의 크기가 크면 무조건 동적할당을 해줘야 하나요??

조언 부탁드립니다. 감사합니다.

luniro   4년 전

N이 최대 100만이기에 각 원소마다 각각 오큰수를 탐색하면 최악의 경우 O(N^2)이 되어 시간초과가 발생합니다

아래와 같은 입력이 주어지면 N이 10만인데도 1초를 초과합니다

그리고 stack을 지역변수로 선언하면 스택메모리가 초과되어 스택오버플로우가 발생합니다 전역변수로 선언하면 문제없을 것 같네요

dlqudgus2587   4년 전

@luniro님 답변 감사합니다 ㅎㅎ

stack을 전역변수로 선언해봐야겠어요. 그런데 제가 배울 때는 전역변수는 최대한 지양하라고 해서 웬만하면 안 쓰려고 하는데 어떠한 경우에 보통 전역변수로 선언해주나요? 

그리고 각 원소마다 오큰수를 탐색 안하면 어떤 방법으로 찾을 수 있나요..?  각각 확인해 봐야 그에 따른 오큰수가 나오는 것 아닌가요?!

감사합니다.

djm03178   4년 전

어떻게 스택을 사용해야겠다는 아이디어를 얻으셨는지 모르겠지만, 그 스택이 핵심입니다.

이 코드는 이름만 스택이고 실제로는 그냥 배열을 하나 만든 것에 불과합니다. 스택이 스택으로서 사용이 되려면 인덱스를 움직여서 밑의 원소를 보는 것이 아니라 오로지 꼭대기의 원소만을 참조해야 합니다.

이 문제는 전형적인 스택 문제 중에 하나입니다. 힌트를 하나 드리자면, 원소를 오른쪽부터 하나씩 볼 때, arr[i] >= arr[i + 1]이라면 i보다 왼쪽에 있는 수들의 오큰수를 찾기 위해 arr[i + 1]을 매번 봐야 하는지 생각해 보세요.

dlqudgus2587   4년 전

@djm03178 님 답변 감사드립니다 ㅎㅎ

말씀 듣고 나니까 전 그냥 배열을 쓴 것 같네요.. 힌트 참고해서 문제 결국 풀었어요! 

근데 저는 스택 구조체 안의 배열을 동적할당을 했는데, 이렇게 배열의 메모리? 배열 요소 개수? 가 크거나 많을 때에는 스택을 아예 전역 변수로 선언하나요 아니면 힙 영역에다가 메모리를 할당 하나요?

감사합니다.

djm03178   4년 전

적어도 문제 풀이를 하는 데에 있어서는 굳이 동적 할당을 하지 않아도 됩니다. 귀찮으니까요. 입력의 최대 제한에 맞게 전역 배열을 할당하는 게 훨씬 간편하고 일반적으로 동적 할당에 비해 약간 빠릅니다.

dlqudgus2587   4년 전

@djm03178님 답변 감사드립니다.

앞으로 이런 경우에는 전역 배열을 써야겠네요. 감사합니다!!

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