문제

크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

백준 17198

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), …, NGE(N)을 공백으로 구분해 출력한다.

풀이 - (블로그 답지)

출처 : 백준17298번 오큰수

핵심 원리 : a < b , b < c -> a < c

최대한 내가 풀려고 했는데 맞게 가다가 중간에 아예 헛발질하면서 막힌 것 같다 😓

우선 브루트 포스 방식으로 접근하면 7 / 6 / 5 / 4 / 3 / 9 라는 수열의 오큰수를 구한다고 하였을 때,

i 번째 오큰수를 구한다고 하면 i + 1 번째에 바로 i 번째 수보다 큰 수가 오지 않고 한참을 더 가서 i + n 번째에 가서야 i 번째 숫자보다 큰 숫자가 등장할 때 문제가 된다. i 번째 오큰수를 구하기 위해서 n번 연산을 수행한 것이다. 그리고 총 1번째 부터 n번째 까지 숫자가 있다고 하면 시간복잡도는 O(n^2) 이 된다. 브루트포스로 제출했을 때 그래도 한 36% 에서 시간초과가 된 것 보면 앞에 운 좋은 테스트 케이스들이 많이 들어간 것 같긴 하다 ..

따라서 7의 오큰수를 구하기 위해서 7 vs 6 -> 7 vs 5 -> 7 vs 4 -> 7 vs 3 -> 7 vs 9 -> 7의 오큰수 9 6의 오큰수를 구하기 위해서 6 vs 5 -> 6 vs 4 -> 6 vs 3 -> 6 vs 9 -> 6의 오큰수 9 5의 오큰수를 구하기 위해서 5 vs 4 -> 5 vs 3 -> 5 vs 9 -> 5의 오큰수 9 4의 오큰수를 구하기 위해서 4 vs 3 -> 4 vs 9 -> 4의 오큰수 9 3의 오큰수를 구하기 위해서 3 vs 9 -> 3의 오큰수 9

이렇게 불필요한 연산 과정을 많이 거쳐야한다.

그런데 7 > 6 이고 6 > 5 라는 결과가 나왔다면 사실 7 vs 5 연산은 해보나마나이다. 마침 스택 자료구조를 사용하면 이전 연산한 숫자들이 다 누적되기 때문에 a < b , b < c -> a < c 원리를 적용하여서 연산과정을 훨씬 줄일 수 있다.

스택을 이용한 풀이 (cf. 브루트 포스)

블로그에 상세하게 알려주신 덕분에 이해를 할 수 있었다. 핵심 원리는 이러하다.

  • 우선 모든 숫자의 오큰수를 -1 로 초기화시켜놓는다. (Step 1)
  • 스택이 현재 비어있으므로 수열의 제일 첫 번째 숫자를 우선 push 한다. (Step 2)
      1. 만약 수열의 다음 번째 숫자가 현재 스택의 제일 위 숫자보다 작다면 수열의 다음 번째 숫자를 스택에 push 한다. (Step 3-1)
      1. 만약 수열의 다음 번째 숫자가 현재 스택의 제일 위 숫자보다 크다면 스택의 제일 위 숫자를 빼내고 스택의 제일 위 숫자의 오큰수를 수열의 다음 번째 숫자로 바꾼다. (Step 3-2)
  • Step 3-1 , Step 3-2 과정을 스택에 수열의 맨 마지막 번째 숫자가 들어가기 전까지 반복한다. ; 수열의 맨 마지막 번째 숫자는 어차피 -1 이므로 업데이트시킬 필요가 없다.

해당 알고리즘을 사용할 경우, { 7 , 6 , 5 , 4 ,3 , 9 } 수열에서 7 을 우선 스택에 넣고 , 현재 스택 : 7 7 vs 6 연산을 한 후 6을 스택에 넣는다 현재 스택 : 6 7 6 vs 5 연산을 한 후 5를 스택에 넣는다 현재 스택 : 5 6 7 5 vs 4 연산을 한 후 4 를 스택에 넣는다. 현재 스택 : 4 5 6 7 4 vs 3 연산을 한 후 3을 스택에 넣는다. 현재 스택 : 3 4 5 6 7 9 vs 3 연산을 하여서 3을 빼낸다. 3의 오큰수 9 9 vs 4 연산을 하여서 4를 빼낸다. 4의 오큰수 9 … 9 vs 7 연산을 하여서 7을 빼낸다. 7의 오큰수 9 🧐 각 숫자의 오큰수를 구하기 위해서 거쳐간 연산은 7 vs 6 , 6 vs 5 , 5 vs 4 , 4 vs 3 , 3 vs 9 , 9 vs 4, 9 vs 5 , 9 vs 6, 9 vs 7 이다.

Cf. 브루트포스 7 vs 6, 7 vs 5, 7 vs 4 , 7 vs 3, 7 vs 9 6 vs 5, 6 vs 4, 6 vs 3, 6 vs 9 5 vs 4, 5 vs 3, 5 vs 9 4 vs 3, 4 vs 9 3 vs 9

이전 연산 결과가 누적되는 스택을 사용함으로써, 불필요된 연산이 없어졌음을 알 수 있다. 7 vs 6, 7 vs 5, 7 vs 4 , 7 vs 3, 7 vs 9 6 vs 5, 6 vs 4, 6 vs 3, 6 vs 9, 5 vs 4, 5 vs 3, 5 vs 9, 4 vs 3, 4 vs 9, 3 vs 9

7 vs 6 , 6 vs 5 , 5 vs 4, 4 vs 3 , 3 vs 9 ; 시간 복잡도 O(N)

7 vs 9, 6 vs 9 , 5 vs 9 , 4 vs 9 ; 시간 복잡도 +a

최종 시간 복잡도 : O(N) + a

해당 블로그에서 올려주신 코드이다 ! 7517D5CE-B9E4-42D6-9226-30792AB83C83

확실히 골드 문제들은 아직 쪼금 아둥바둥하는 것 같다.. 코테를 안 보게 되는게 베스트이겠지만 그래도 조금씩 시간 날 때 계속 연습은 해두어야할 것 같다 !