[프로그래머스] 뒤에 있는 큰 수 찾기

 

📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

❌ 내 풀이(Failure) :

시간 초과로 실패, 20 ~23번 테스트 케이스에서만 실패했다.

 

✅ 내 풀이(Success) :

 

🧐 Review:

 반복문을 거꾸로 순회하면서 뒤에 있는 원소부터 뒷 큰 수를 찾았다. 이때, 뒷 큰 수는 리스트에 앞에 추가해야 되는데, 인덱스를 지정해서 원소를 추가하면 리스트의 순서를 재정립하는 과정에서 시간이 필요하기 때문에 데큐를 사용하는 것을 잠깐 고민했었다. 하지만, 굳이 데큐를 이용해서 appendleft()를 사용하기보단 그냥 리스트에 순서대로 넣고, 리스트 슬라이싱을 이용해서 순서를 뒤집어주면 된다고 생각했고, 이 생각대로 코드를 작성하고, 문제를 해결할 수 있었다. 나름 깔끔하게 문제를 해결한 것 같아서 기분이 좋다.

 

🚩 Idea:

  배열의 최대 크기는 1,000,000이다. 문제를 해결하는 방법으로 이중 for문을 이용한 풀이가 떠오를 수 있겠지만, 배열의 최대 크기 때문에 시작복잡도가 O(N^2)인 풀이는 시간 초과로 틀릴 수밖에 없다. 이렇게 입력 값의 크기가 큰 경우에는 이진 탐색을 떠올릴 수 도 있겠지만, 이 문제는 원본 배열을 정렬하면 안 되기 때문에 원본 배열을 변형하지 않는 상태에서 문제 풀이를 진행해야 한다. 그래서 투 포인터를 이용한 풀이를 시도해 봤고, 4개의 테스트 케이스를 제외하곤 맞을 수 있었다. 하지만, 완전히 푼 것은 아니기에 for 반복문을 거꾸로 순회하면서 스택을 이용한 풀이로 문제를 해결할 수 있었다.