바킹독 0x05 문제6 / 백준 17298번 오큰수

최근에 책상정리하며 아껴두었던 청포도 캔디 한 봉지를 찾았다.

ㅋㅋㅋㅋ유통기한이 지났지만..그냥 먹기로 했다.

음!! 맛있다. 근데 확실히 막 엄청 엄청 달진 않다.

단맛이 좀 빠졌나보다..ㅋㅋ

 

아! 오늘은 롤드컵 티원 경기가 저녁 8시에 있다.

후딱 풀고 봐야지!

 

오큰수?

오른쪽에 가장 큰 수?

오징어 토큰 수?

ㅋㅋㅋㅋ

뭔지 볼까?!?!

---

 

오큰수.. 이름은 첫 번째 말한 거랑 비슷한 거 같지만..

오른쪽에 있으면서 수열 Ai보다 큰 수 

근데 문제는 여기에 더하여

가장 왼쪽에 있는 수...(?) 란다

 

그렇다면

..이라고 치고 30분이 걸렸다..

.... 이번엔 어제처럼 처음부터 넣을 때부터 계산하면 안 될 거 같다는 생각이 들었다.

그러면 다 넣고 빼면서 해야 하나? 싶기도 하고.. 아니 그러면.. 예제 2에서 문제가 생긴다..

일단 하나 알게 된 점..

맨 마지막엔 오른쪽이 없어서 -1 출력..

 

아니네..

결국 한 시간 동안 생각하지 못했다.

그래서 힌트를 받으러 출동....

 

일반식으로 풀려면 이건 N2의 시간복잡도여서 스택을 활용해야 한다고 했다.

이 풀이의 핵심은 오른쪽에서 왼쪽으로 거꾸로 본다고 했다.

그럼 내가 생각한 게 맞은 건가.. 흠흠

오른쪽에 뭐가 있는지 스택에 저장해 두면, 오른쪽에 있는 큰 수를 금방 알 수 있다고 한다. 

 

근데! 처음부터 스택에 넣고 빼는 것이 아니라

받아온 수를 일단 배열에 넣어두고, 배열의 뒷부분부터 빼면서 큰 수를 스택에 넣는 것..!

 

그러면서 스택에 있는 오큰수를 출력하게 된다.

이번 문제에서 스택은

오른쪽에 있는 숫자들 중에서

왼쪽 숫자들이 확인하지 못했으니 큰 숫자들만 잠깐 보관하는 역할만 하게 된다.

 

배열 a = [ 3 5 2 7 ]

7 오른쪽에 아무도 없음 -1, 그리고 7 push

2 옆에 7이 있음 그러면 7 오큰수, 2 push

5 옆에 2 7 있음 2는 작으니 pop 7은 크니 7은 오큰수, 5 push

3 옆에 5 있음 5 오큰수, 3 push

 

이거 ans에 모아다가 제출하면 되겠다!

 

대충 이해했다.

문제를 이제 한번 풀어보자

 

음... 아! 다시 모아다가 배출할 때 for문 쓰는 거!

ㅋㅋㅋㅋㅋ아따...

요즘 배열 안 써서 까먹었다 그새 까먹었어....!!

 

 

아!

그리고 이제 보니까

저렇게 배열 크게 잡을 때는

main밖에서 하는 것을 추천한다고 한다.

 

오케이 확인입니다.

 

후딱 풀려했는데.. 실패했다..

얼른 보러 가야지.. 총총..