1. 학습한 내용
백준 자료구조(스택) 17298번 문제
원래 6/19에 학습한 내용이지만 지금 정리합니다..
2. 알게 된 내용
이 문제를 처음 봤을 때 굉장히 간단할 것이라 생각했지만, 내 머릿속에서 나온 코드는 시간복잡도가 굉장히 큰 코드였고... 시간 초과가 나지 않게 만들 방법이 생각나지 않았다..
그래서 다른 분의 설명을 참고하면서 원리를 바탕으로 코드를 구현해보고, 맞게 구현했는지 확인하는 식으로 공부를 진행했다.
출처 : https://st-lab.tistory.com/196
이 문제는 실은 스택을 활용해야 한다고 한다. 문제만 봤을 때 스택과 전혀 관련이 없어보였는데... 충격이었다. 아래 댓글을 보니 많이 풀다보면 자주 쓰이는 알고리즘들을 파악하게 될 날이 올 것이라고 하셔서.. 지금 몰랐더라도 다음에 이를 응용해보려고 하면 될 것이라 생각해본다..!
이 문제에서 스택이라는 개념을 어떻게 끄집어내는지를 생각해보자.(원리는 위의 출처 글을 바탕으로 작성함)
왼쪽에 있는 수를 a라고 해보고, 오른쪽에 있는 수를 b라고 해보겠다. a보다 b가 크면 바로 그 순간, b 이전에 있는 'b보다 작은 a같은 수'들은 모조리 오큰수가 b로 확정된다. 이때 a보다 왼쪽에 있고 a보다 큰 수는 이 과정과 상관없고, b보다 작은 이 'a들'만 b의 영향을 받게 된다. 이를 정리해보자면, 오른쪽에 자신보다 작은 수가 나오면 그 수들을 따로 저장해두어서 앞으로 이들보다 더 큰 수가 나오는지를 지켜보아야 하고, 오른쪽에 이들보다 큰 수가 나오면 그 수가 오큰수로 확정이 되는 것이다. 따라서 이는 후입선출을 이용하는 스택을 이용하면, 쉽게 구현할 수 있다.
수열을 탐색하면서 현재 원소가 이전의 원소보다 작을 때까지 스택에 수열의 인덱스를 추가하고,
만약 현재 원소가 스택의 top 원소 값보다 큰 경우, 스택의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 (오큰수) 바꿔주는 것이다.
실은 그림으로 봐야 제대로 이해가 되는데, 그림은 이 위의 출처 글에서 정말 잘 설명해주셔서 생략하겠다! 그림 설명까지 정말 감사합니다... 나중에 다시 헷갈려할 것을 대비해 어떻게 스택을 이용하는 걸 생각해내는지에 초점을 맞춰서 TIL을 작성하였다..
+) 왜 스택에 인덱스를 넣을까
원리를 이해하고 직접 코드로 짜보면서 든 생각인데, 스택에 왜 인덱스를 넣는지에 대해 조금 궁금했다. 많은 분들이 당연한 것이라 생각할 수도 있어서 조심스럽긴 하지만 잠깐 그런 생각이 들어서 여기에 남긴다..
스택에 원소의 값을 넣는 것보다 인덱스를 넣는 것이 더 정확한 위치를 담는 것이기 때문이다. 원소의 값은 중복될 수도 있고!
별 것 아니지만.. 앞으로도 잘 생각하고 풀길 바라며 남겨본다.
머리로 풀면 정말 간단한 문제인데 이렇게 코딩으로 푸니까 꽤 생각할 점이 많아서 신선하고 재미있는 문제였다. 그리고 스택을 당연히 잘 알고 있다고 생각했는데 이렇게 응용된 문제에서 생각해내지 못한 점이 조금 아쉬웠다. 이 문제의 해법은 내 머리 속에서 생각해낸 원리는 아니지만, 이렇게 새로 배워간 것을 토대로 앞으로 더 다양하게 생각해보면 좋겠다!
0개의 댓글
