N이 최대 100만이기에 각 원소마다 각각 오큰수를 탐색하면 최악의 경우 O(N^2)이 되어 시간초과가 발생합니다
아래와 같은 입력이 주어지면 N이 10만인데도 1초를 초과합니다
그리고 stack을 지역변수로 선언하면 스택메모리가 초과되어 스택오버플로우가 발생합니다 전역변수로 선언하면 문제없을 것 같네요
17298번 - 오큰수
@luniro님 답변 감사합니다 ㅎㅎ
stack을 전역변수로 선언해봐야겠어요. 그런데 제가 배울 때는 전역변수는 최대한 지양하라고 해서 웬만하면 안 쓰려고 하는데 어떠한 경우에 보통 전역변수로 선언해주나요?
그리고 각 원소마다 오큰수를 탐색 안하면 어떤 방법으로 찾을 수 있나요..? 각각 확인해 봐야 그에 따른 오큰수가 나오는 것 아닌가요?!
감사합니다.
어떻게 스택을 사용해야겠다는 아이디어를 얻으셨는지 모르겠지만, 그 스택이 핵심입니다.
이 코드는 이름만 스택이고 실제로는 그냥 배열을 하나 만든 것에 불과합니다. 스택이 스택으로서 사용이 되려면 인덱스를 움직여서 밑의 원소를 보는 것이 아니라 오로지 꼭대기의 원소만을 참조해야 합니다.
이 문제는 전형적인 스택 문제 중에 하나입니다. 힌트를 하나 드리자면, 원소를 오른쪽부터 하나씩 볼 때, arr[i] >= arr[i + 1]이라면 i보다 왼쪽에 있는 수들의 오큰수를 찾기 위해 arr[i + 1]을 매번 봐야 하는지 생각해 보세요.
@djm03178 님 답변 감사드립니다 ㅎㅎ
말씀 듣고 나니까 전 그냥 배열을 쓴 것 같네요.. 힌트 참고해서 문제 결국 풀었어요!
근데 저는 스택 구조체 안의 배열을 동적할당을 했는데, 이렇게 배열의 메모리? 배열 요소 개수? 가 크거나 많을 때에는 스택을 아예 전역 변수로 선언하나요 아니면 힙 영역에다가 메모리를 할당 하나요?
감사합니다.
@djm03178님 답변 감사드립니다.
앞으로 이런 경우에는 전역 배열을 써야겠네요. 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
dlqudgus2587 4년 전
25%에서 시간 초과로 막혔습니다.
스택을 하나 만들어서 입력 받은 수열을 스택에 넣고, Oken이라는 함수를 만들어서 한 번만 pop을 하고 그 이후 비교대상은 스택의 인덱스 값만 움직여서 pop한 수 와 비교를 했습니다.
질문 글에 있는 반례는 다 돌아가는데 어디서 시간을 단축시켜야 할지 잘 모르겠네요ㅠㅠ
아 그리고 원래는 Stack 구조체에서 int arr[1000000]; 이렇게 바로 배열을 선언했는데 stack overflow라며 에러가 뜨던데 배열의 크기가 크면 무조건 동적할당을 해줘야 하나요??
조언 부탁드립니다. 감사합니다.