17298번: 오큰수

문제 풀이 아이디어

# 시간복잡도 제한
  : 그냥 수열의 모든 수에 대해 하나하나 오큰수를 구하면 이중반복문을 사용할 수 밖에 없게 됩니다.
		: 즉 O(n**2)가 되어 n이 최대 1,000,000인 경우 무조건 시간초과가 납니다.
	: 따라서 O(n)의 시간복잡도를 가진 방법을 사용해야 합니다.

# 관점의 전환
  : 초점를 오큰수를 구하는 수 a[i]에 두고
      : 뒤에 오는 어떤 수가 NGE가 될 수 있는지 구하는 것이 아니라
  : NGE(i)에 초점을 두고 문제에 접근하는 것입니다.
      : -> 현재 a[i]가 어떤 수의 NGE가 될 수 있는지 찾는 것입니다.

# 사용해야하는 자료구조 = stack
	: 현재 a[i]가 어떤 수의 오큰수가 될 수 있는지 확인하기 위해서는
		: a[i - 1] ~ a[0]의 수 중에서 아직 오큰수를 구하지 못한 수들과 비교하여
		: 그 수보다 a[i]가 큰지 확인해야 합니다.
	: 위 방법대로 진행하기 위해서는 stack을 활용해봅니다.
		: a[0]에서 시작해서 아직 오큰수를 구하지 못한 수를 stack에 넣어 둔다고 생각합니다.
		: 그리고 하나씩 pop하면서 a[i]가 오큰수가 될 수 있는지 확인하는 방법입니다.

# 의사코드
	: 아직 오큰수를 구하지 못한 a[i]의 i를 담을 stack을 선언합니다.
  : 그리고 a[1]부터 순회합니다.
      : a[stack.last]가 a[i]를 NGE로 가질 수 있는지 따집니다.
	    : stack이 비었거나 a[stack.last] a[i]보다 작다면 (= stack에는 a[i]보다 큰 수만 들어있다 = a[i]가 더 이상 아래 수들의 NGE가 될 수 없다.)
      : i를 스택에 넣습니다.

# 시간 복잡도
  : while문에 while문이 있어 이중반복문처럼 생겼지만
	: 논리적으로 생각하면 a[i]와 그 아래 모든 수를 비교하는 것이 아니라 오큰수를 구하지 못한 수들과만 비교하는 것이므로
	: 시간복잡도는 O(n)이라고 볼 수 있습니다.

풀이

// 오큰수

// 입력 받기
let N = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map { Int(String($0))! }

// 오큰수가 아직 구해지지 않은 값들을 stack에 넣는다.
var stack = [0] //👉 0번 index의 숫자는 누구의 오큰수도 될 수 없으므로 미리 stack에 넣어둔다.
//⭐️ 실제 값이 아니라 index를 stack에 넣어야 하는 이유
    // 오큰수를 순서래도 출력해야한다.
    // 즉 Ai의 오큰수라는 정보가 아니라 i번째 오큰수라는 것을 저장해야한다.

// 현재 인덱스
var i = 1

// index의 오큰수를 찾아서 저장하는 배열 (오큰수가 없으면 -1을 출력하므로 기본적으로 -1로 세팅)
var result = Array(repeating: -1, count: N)

// 반복문
while i < N { //👉 1 ~ N - 1의 인덱스 내에서
    
    // stack이 아직 비지 않음 (= 왼쪽에 아직 오큰수를 없는 수가 남아있음) &&
    // a[stack.last!]보다 a[index] 더 큼 (= a[index]이 a[stack.last!]의 오큰수)
    while !stack.isEmpty && a[i] > a[stack.last!] {
        result[stack.popLast()!] = a[i] // 오큰수를 구했으니까 기록하고 pop한다.
    }
    
    // stack이 비었거나 (= 이미 오큰 수를 다 찾았다.)
    // a[stack에 있는 수들]이 현재 a[i]의 값보다 크다 (= 더 이상 a[i]의 값은 오큰수가 될 수 없음)
    stack.append(i) //👉 현재 index의 오큰수를 구하기 위해서 push한다.
    i += 1
}
//⭐️ 반복문을 도는 동안 stack 안은 오름차순으로 정렬된다.
    // stack에 있는 a[i]보다 작은 것들은 다 pop해 버리고 더 a[i]보다 큰 수를 만났을 때 push되기 때문에

print(result.map { String($0) }.joined(separator: " "))