[BOJ_17298] 오큰수

 

📌 문제 링크: https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

❌ 내 풀이(Failure) 1번 : 시간초과

 

❌ 내 풀이(Failure) 2번 : 시간초과

시간 초과로 통과하지 못한 풀이

 

✅ 참고용 풀이(Success) :

시간 초과로 통과하지 못한 풀이

 

🧐 Review:

 문제 해결의 아이디어는 정말 간단했고, n의 크기가 작았다면 O(n^2) 풀이로도 충분히 해결할 수 있겠지만, 주어진 n의 값이 매우 커서 시간복잡도를 O(n)으로 줄이지 못하면 시간초과가 발생할 것이라고 충분히 예상되는 문제였다. 하지만 이 부분을 알고 있었지만 어떻게 for 반복문 하나로 문제를 해결할 수 있을지 아이디어가 떠오르지 않아서 하루종일 고민하다가 구글링을 통해 정답 코드를 참고했다. 스택에 배열의 인덱스를 넣는다는 생각은 전혀 예상도 못한 아이디어라서 좀 더 빨리 코드를 참고했다면 내 시간을 좀 더 아꼈을 것이란 아쉬움이 남는다. 

 문제의 난이도를 올리면 당장 해결하지 못하는 문제가 많을지도 모르지만 적정한 시간을 정해서 그 안에 해결하지 못한다면 빠르게 풀이를 참고해서 내 것으로 만들려고 하자. 항상 다짐하는 부분이지만 내려놓는다는 것이 정말 쉽지 않다. 내 손으로 해결하고 싶은 생각에... 그래도 이제는 어느정도 효율을 고려해야될 시기인 것 같다.

 

🚩 Idea:

 - 스택과 배열의 인덱싱을 이용한다.