Jenikeju

내가 푼 풀이

접근방법: DP

암호를 해석하는 경우의수를 먼저 찾아보았다.

1. 주어진 암호가 1~26사이면 해석이 가능하다.

2. 암호가 10~26이면, [1, 1- ], [2, 2- ]로 경우의수가 더 늘어난다.

3. 암호에 0이 주어질 수도 있다.

0의 경우의수

1. 00: 앞 0은 10,20으로 사용되었어도, 0이 연속으로 오는경우 해석이 불가능하다.

2. 10, 20: 해석이 가능하다. 하지만 경우의수는 늘지않는다.

3. 30, 40, ... , 90: 해석이 불가능하다.

위 경우의 수를 토대로 암호의 첫번째 문구부터 마지막까지 탐색한다.

탐색할 때,

암호가 0이라면 --> 0의 경우의수를 탐색

암호가 0이 아니라면 --> 무조건 해석이 가능하고, 해석이 되더라도 이전 해석문 + [현재암호] 이므로 경우의수가 늘어나지 않는다.

현재 암호와 이전암호를 합쳐서 비교했을 때, 10이상 26이하라면

-> 2번 경우의수 처럼 경우의수가 더 늘어난다.

ex) 11 이 주어졌다면, 1을 해석했을땐 A 1가지지만, 11을 해석하면 AA와 K가 된다. (2가지)

네번째 암호 1이 주어졌을때, 이전암호와 합치면 11이된다.

이때 네번째 암호까지의 해석 경우의수는 BEA + [A], BE + [K] , YA + [A], Y +[K] 로 4가지가 된다.

dp[4] = (dp[4] +dp[3]) + (dp[4] + dp[2]) 가 된다.

세번째 암호가 주어졌을때, 이전암호와 합치면 51이되고, 이는 해석이 가능한 암호가 아니다.

세번째 암호까지의 해석 경우의 수는 이전 두번째 암호까지의 경우의수와 동일하다.

dp[3] = dp[3] + dp[2]

따라서 점화식을 다음과 나타낼 수 있다.

dp[n] = dp[n] + dp[n-1] (n > 0)

dp[n] = dp[n] + dp[n-2] (10 <= n <= 26)

코드로 구현하면 다음과 같다.

import Foundation

// 입력 받기
var str = Array(readLine()!).map{String($0)}
let n = str.count
str.insert("0", at: 0)
var alphabet = ["."]
var dp = Array(repeating: 0, count: str.count+1)
var chan = true
for i in 65...90 {
    alphabet.append(String(UnicodeScalar(UInt32(i))!))
}
dp[0] = 1

// dp[n]: n자리 암호코드를 변환할 수 있는 경우의 수
// 단, 0에 예외처리를 해야함. 코드는 1~26 A~Z까지 변환 가능하므로, 0 또는 26보다 큰수는 변환이 불가.(마찬가지로 00도 불가.)
for i in 1..<str.count {
    if i == 1 {
        // 첫번째 수가 0이면 애초에 변환 불가
        if Int(str[i])! == 0 {
            dp[n] = 0
            break
        } else {
            dp[i] = 1
        }
        continue
    }
    // 숫자가 0이라면, 세가지 경우의수가 존재
    // 앞자리가 1,2인 10 20 , 앞자리가 0인 00, 앞자리가 2보다 큰수 30, 40, 50 ...
    // 앞자리가 0이거나 앞자리가 2보다 큰수면 변환자체가 불가능
    // 앞자리가 1,2인경우는 경우의수가 늘어나지않음. 1 -> A , 10 -> J 1가지임
    if str[i] == "0" {
        if str[i-1] == "0" || Int(str[i-1])! > 2 {
            dp[n] = 0
            break
        }
    } else {
        dp[i] = (dp[i] + dp[i-1]) % 1000000
    }
    // 만약 앞자리수를 포함한 숫자가 10~26 이라면 경우의수가 늘어남. 1 -> A , 11 -> AA, L 1가지에서 두가지로 늘어난다.
    if Int(str[i-1] + str[i])! <= 26 && Int(str[i-1] + str[i])! >= 10 {
        dp[i] = (dp[i] + dp[i-2]) % 1000000
    }
}
print(dp[n])

문제

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

내가 푼 풀이

접근방법: DP

각 좌석은 양 옆으로만 배치할 수 있다.

예시로 [1, 2, 3, 4] 좌석을 배치하는 경우의 수를 확인해보자.

[1]: [1] 1가지

[1, 2]: [1, 2], [2, 1] 2가지

[1, 2, 3]: [1, 2, 3], [2, 1, 3], [1, 3, 2] 3가지

[1, 2, 3, 4]: [1, 2, 3, 4], [2, 1, 3, 4], [1, 3, 2, 4], [1, 2, 4, 3], [2, 1, 4, 3] 5가지

위 좌석 4개로 규칙을 알 수 있다.

3개의 좌석 배치수를 구할 때: (2개 좌석이 배치된경우) + (3의 위치를 바꾼 경우)

( [1,2] + [3]  , [2,1] + [3] ) + ( [1] + [3, 2] ) 으로 총 3가지

4개의 좌석 배치수를 구할 때: (3개의 좌석이 배치된 경우) + (4의 위치를 바꾸는 경우)

( [1,2,3] + [4] , [2,1,3] + [4] , [1,3,2] + [4]) + ( [1,2] + [4,3] , [2,1] + [4,3] )으로 총 5가지

이를 점화식으로 나타내면 다음과 같다. 

dp[n] = dp[n-1] + dp[n-2]

여기서 추가조건으로 vip석은 이동할 수 없다.

위 예제를 보면 vip를 제외한 좌석은 아래와 같다.

[1,2,3] , [5,6] , [8,9] 

각각 배치가능한 경우의 수를 구하면, 3 , 2 , 2 가 되고, 모두 곱하면 12가 나온다.

이렇게 vip좌석을 경계로 배치방법 수를 구하고 모두 곱해주면 결과가 나오게 된다.

코드에서는 중간 결과값을 저장하여 마지막 수와 곱해서 출력했다.

import Foundation

//입력받기
let N = Int(readLine()!)!
let M = Int(readLine()!)!
var vip = [Int]()
for i in 0..<M {
    vip.append(Int(readLine()!)!)
}
// dp[n]: 중간 vip좌석 없이 n번째까지의 배치 경우의 수
var dp = Array(repeating: 1, count: N+1)
// vip좌석을 만나면 값을 저장할 변수
var mul = 1
var idx = 0
var vp = false

// 탐색
for i in 1...N {
    // vip좌석을 만나면 중간값 저장
    if idx < M && i == vip[idx] {
        idx += 1
        dp[i] = 1
        mul = dp[i-1] * mul
        vp = true
        continue
    }
    // 이전에 vip좌석이였다면 그 다음 배치경우의수는 좌석 1개이므로 1
    if vp {
        dp[i] = 1
        vp = false
        continue
    }
    // 첫번째 좌석은 경우의수가 1가지
    if i == 1 {
        dp[i] = 1
        continue
    }
    dp[i] = dp[i-1] + dp[i-2]
}
print(dp[N] * mul)
//print(mul)

내가 푼 풀이

접근방법 1: DFS(시간초과)

일반적인 DFS로 풀어봤다가 같은 경로를 재탐색하게되어 시간초과가 났다(31퍼에서 안오름..)

접근방법 2: DFS + DP

DFS로 탐색하면서, 탐색한 경로에 값을 저장해둔다. 다른 출발점에서 탐색할 때, 이미 탐색된 곳이라면 탐색하지 않는다.

예시로 출발점 1에서 탐색한 경로가 (1 - 2 - 3 - 5)라면, 각 도착점에 값을 저장해둔다.

그 다음 출발점 2에서 탐색한다면 (2 - 3 - 5)로 재탐색하게된다.

이는 이전에 1번에서 탐색했고, 2번에서 출발해도 최댓값은 1번에서 출발한 크기 4가 된다.

1번 출발점에서 조건에 맞춰 갈 수 있는 모든 지점을 도달했고,

그 지점마다 이동한 칸수가 저장되어 있으므로, 다시 재탐색을 할 필요가 없다.

DP[y][x]: (x,y)지점에서 이동할 수 있는 칸의 최댓값

코드로 구현하면 다음과 같다.

import Foundation

// 입력 받기
let n = Int(readLine()!)!
var arr = [[Int]]()
for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

// dp[y][x]: (x,y)에서 최대로 이동할 수 있는 수
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
var result = 0

// 상,하,좌,우 4방향
let dx = [0,1,0,-1]
let dy = [1,0,-1,0]

// DFS + DP
// DFS로 깊이 탐색하며, 최대로 이동한 값을 저장한다.
// DP에 저장하는이유: 이미 최대로 이동한 경로를 재탐색 하지 않기 위해서
// 예시) (1 - 2 - 3 - 4)로 이동한게 최대라면, 2번에서 이동경로는 (2 - 3 - 4)를 갖게된다.
// 2번에서 이동한 경로는 이미 탐색된 경로이므로 굳이 다시 탐색하지않아도된다. (가지치기)
func dfs(_ x: Int,_ y: Int) -> Int {
    // 이미 이동했던 경로라면 종료
    if dp[y][x] != 0 { return dp[y][x] }
    // 이동했던 경로로 표시
    dp[y][x] = 1
    // 네방향으로 조건에 맞춰서 이동
    for k in 0..<dx.count {
        let mx = x + dx[k]
        let my = y + dy[k]
        if (mx >= 0 && mx < n) && (my >= 0 && my < n) {
            if arr[my][mx] > arr[y][x] {
                dp[y][x] = max(dp[y][x], dfs(mx, my) + 1)
            }
        }
    }
    return dp[y][x]
}
// 모든 시작점에서 출발해보고, 최댓값을 구한다.
for i in 0..<n {
    for j in 0..<n {
        result = max(result, dfs(j, i))
    }
}
print(result)

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

내가 푼 풀이

접근방법: DP

이 문제는 이전에 풀었던 파일합치기 문제와 유사하다

https://www.acmicpc.net/problem/11066

 

연산에 순서에 따라 총 연산횟수가 달라지는 행렬곱셈으로, DP를 이용해 풀었다.

가장 좁은 구간부터 연산횟수를 구하고 저장하여 구간을 넓히며 값을 구해나갔다.

 

dp[i][j]: i번째 행렬부터 j번째 행렬까지 곱셈연산의 최솟값 이고,

dp[i][i] = 0이다.( dp[1][1] == dp[2][2] == dp[i][i] = 0, 행렬한개로 곱셈을 하지않는다.)

예시를 통해 알아보자.

dp 2차원배열을 다음과 나타낼 수 있다.

각 행과 열은 행렬의 크기를 나타낸다.

최종적으로 dp[1][3]을 구하기 위해 작은 구간부터 칸을 채워나가보자.

구간의 길이가 2일때 : [1,2], [2,3]

위 2차원 배열에선 dp[1][2], dp[2][3]의 값을 구하는것이다.

구간의 길이가 2일땐, 순서상관없이 연산횟수가 같다.(순서는 바꾸면안된다. 행렬곱셈이 안됨)

dp[1][2] =  $5\times3\times2$ = $30$

dp[2][3] =  $3\times2\times6$ = $36$

구간의 길이가 3일때: [1,2] + 3, 1 + [2,3] 

위와 다르게 표현한 이유는 점화식으로 표현하기 위해서이다.

결국 구간 [1,2,3]의 값이 저장된 dp[1][3]을 구하는 것이지만,

[1,2] 와 [2,3]은 이미 이전에 구한뒤 저장해두었다.

dp[1][2] $\times$ [3]과 [1] $\times$ dp[2][3]의 결과중 최솟값을 넣으면 된다.

dp[1][2] $\times$ [3]: dp[1][2] + ($5 \times 2 \times 6$) = 90(1번행렬과 2번행렬을 곱하면 5x2 배열)

[1] $\times$ dp[2][3]: dp[2][3] + ($5 \times 3 \times 6$) = 126(2번행렬과 3번행렬을 곱하면 3x6 배열)

따라서 dp[1][3]은 더 작은값 90을 저장한다.

정리)

1. N개의 행렬이 주어지면 dp[1][N]의 값을 구한다.(dp[1][N]: 1번째행렬부터 N번째 행렬까지 연산의 최소횟수)

2. 가장작은 구간의 곱셈부터 구하고 최솟값을 저장한다.

3. 저장된 구간으로부터 더 넓은 구간의 연산횟수를 구한다.(최솟값을 비교하여 저장)

4. 최종적으로 dp[1][N]을 구한다.

예시: [1,2,3,4,5]

구간 2: [1,2], [2,3], [3,4], [4,5]

구간 3: [1,2,3], [2,3,4], [3,4,5]

구간 4: [1,2,3,4], [2,3,4,5]

구간 5: [1,2,3,4,5]

점화식은 다음과 나타낼 수 있다.

$\mathbf{dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j] + ((j행 \times k열 \times i+j열)(k: i와 i+j 사이의 점)} $

3중 for문을 이용하여 코드를 구현해보자.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)
var arr = Array(repeating: Array(repeating: 0, count: 2), count: N+1)

// 주어진 행렬들의 행,열 저장
for i in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i+1][0] = input[0]
    arr[i+1][1] = input[1]
}

// dp[i][j]: i번째부터 j번째까지 연산의 최소횟수
// 가장 좁은구간부터 구한 값을 이용해 넓은 구간의 최솟값을 구한다.
for i in 1...N {
    for j in 1..<N-i+1 {
        dp[j][j+i] = Int.max
        for k in j..<j+i {
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + (arr[j][0] * arr[k][1] * arr[i+j][1]))
        }
    }
}
print(dp[1][N])

배열의 크기를 무분별하게 크게 선언했다가 시간초과가 났다..

행렬들의 행,열은 곱셈을 하면 결과의 행,열이 변할 수 있어도, 값 자체가 변하진 않는다. (피연산 행렬들의 행 열을 가져옴)

(5x2와 2x3의 결과가 왼쪽행렬의 행, 오른쪽행렬의 열을 가져와 5x3이 되는것처럼)

이를 이용해 2차원배열에 저장해두었다.

아예 튜플로 저장하여 문제풀이를 시도했지만, 시간초과가 났다.

시간초과가 난 코드

import Foundation

let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)
var arr = Array(repeating: Array(repeating: (x: 0, y: 0), count: N+1), count: N+1)

for i in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i+1][i+1] = (x: input[0], y: input[1])
}

for i in 1...N {
    for j in 1..<N-i+1 {
        dp[j][j+i] = Int.max
        for k in j..<j+i {
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + (arr[j][k].x * arr[j][k].y * arr[k+1][j+i].y))
            arr[j][j+i] = (x: arr[j][k].x, y: arr[k+1][j+i].y)
        }
    }
}

print(dp[1][N])

내가 푼 풀이

접근방법: 부분합

이전에 체스판 다시 색칠하기 1 문제는 브루탈포스로 모든 경우의수를 구해서 대입하고 구했다면,

이 문제는 체스판의 크기가 최대 2000 x 2000 이므로 브루탈포스로는  시간초과가 난다.

부분합을 이용해서 구해보자

주어진 수열에서 i번째까지의 합은 다음과 같다.

 $S_{i} = A(i) + A(i-1) + \cdots + A(1) $

이 성질을 이용해 부분합 i부터 j까지의 합은 다음과 같다.

$S_{ij} = A(j) + A(j-1) + A(j-2) +\cdots + A(i+1) + A(i) = S_{j} - S_{i-1}$

이것을 2차원 배열에 적용하는데, 체스판은 총 두가지 경우가 있다.

• 왼쪽상단이 검정색으로 시작하는 경우
• 왼쪽상단이 흰색으로 시작하는 경우

두개의 체스판을 이용하여 2차원배열 부분합을 구한다.

먼저 예시의 체스판과 두개의 정상 체스판을 보자.

Board: 주어진 보드판, Black: 왼쪽 상단이 검정으로 시작, White: 왼쪽 상단이 흰색으로 시작

주어진 보드판을 두개의 정상 체스판처럼 만들어보려고 한다.

보드에서 각 칸과 정상 체스판의 색이 같다면 색칠하지 않아도되고, 색이 다르면 색칠을 해줘야 한다.

i행 i열의 값은 1행1열부터 i행 i열까지 색칠한 수를 모두 합한 수가 되도록 구해준다.

이렇게 2차원배열로 부분합을 구해주면 위와 같다.

배열 S[i][j] : 1행1열부터 i행i열까지의 합

여기서 주어진 K x K 크기의 체스판을 만들 때 최소로 색칠하는 횟수를 구하려고 한다.

각 배열의 원소는 1행1열부터 색칠한 횟수를 저장했다.

부분합 성질을 이용하여 K크기의 체스판을 만들고, 색칠하는 최솟값을 갱신한다.

예시로 중간 2행2열부터 3행3열까지의 부분합을 구해보자.

이를 식으로 나타내면

S[3][3] - S[3][1] - S[1][3] + S[1][1]

이렇게 K x K 크기만큼의 부분합을 구해서 최솟값을 구하면 된다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1], K = input[2]

// 체스판의 맨 왼쪽상단이 검정색, 흰색인경우의 두가지 정상 체스판을 미리 만든다.
var black = Array(repeating: Array(repeating: 0, count: M+1), count: N+1)
var white = Array(repeating: Array(repeating: 0, count: M+1), count: N+1)
var first = false
var bl = true
var minSum = Int.max
for i in 1...N {
    if first {
        bl = true
    } else {
        bl = false
    }
    first = !first
    for j in 1...M {
        if bl {
            white[i][j] = 1
        } else {
            black[i][j] = 1
        }
        bl = !bl
    }
}

// 부분합 구하기
for i in 0..<N {
    let arr = Array(readLine()!)
    for j in 0..<arr.count {
        if (black[i+1][j+1] == 0 && arr[j] == "B") || (black[i+1][j+1] == 1 && arr[j] == "W") {
            black[i+1][j+1] = black[i+1][j] + 1 + black[i][j+1] - black[i][j]
        } else {
            black[i+1][j+1] = black[i+1][j] + black[i][j+1] - black[i][j]
        }
        if (white[i+1][j+1] == 0 && arr[j] == "B") || (white[i+1][j+1] == 1 && arr[j] == "W") {
            
            white[i+1][j+1] = white[i+1][j] + 1 + white[i][j+1] - white[i][j]
        } else {
            white[i+1][j+1] = white[i+1][j] + white[i][j+1] - white[i][j]
        }
    }
}

// 해당 부분합중 최솟값 구하기
for i in 1...N-K+1 {
    for j in 1...M-K+1 {
        let whiteSum = white[i+K-1][j+K-1] - white[i+K-1][j-1] - white[i-1][j+K-1] + white[i-1][j-1]
        let blackSum = black[i+K-1][j+K-1] - black[i+K-1][j-1] - black[i-1][j+K-1] + black[i-1][j-1]
        let m = min(whiteSum, blackSum)
        minSum = min(minSum, m)
    }
}
print(minSum)

인덱스의 0번째부터 6번째순으로 사람이 줄 서 있다. 이를 그래프로 나타내면 아래와 같다.

첫번째 위치한 사람의 키는 2이고, 두번째 위치한 사람의 키는 4이다.

위 첫번째 조건에따라 두 사람은 서로 볼 수 있는 쌍이 된다.

이제 세번째 위치한 사람을 보자.

첫번째 키는 2, 세번째 키는 1이된다. 서로 볼 수 있을까?

3번 조건에 따르면 서로 볼 수 없는 쌍이다.

세번째 이후의 모든 사람들도 1번사람과 볼 수 있는 쌍이 될 수 있을까?

답은 X다. 왜냐하면 첫번째사람보다 두번째사람이 더 크기때문에, 3번 조건에 의해 볼 수 없는 쌍이 된다.

그렇다면 1번은 2번에 의해서 항상 가려지기때문에 1번의 키정보는 필요가 없다.

순차적으로 키를 조사할때, 현재 사람의 키가 이전사람보다 크다면, 이전사람의 키는 더이상 필요가없게된다.

즉 우리는 스택에 이전사람의 키를 저장하고, 이전사람의 키보다 현재사람의 키가 더 크다면,

그 이후사람들은 어차피 못보게되므로, 스택에서 빼내어 볼 수 있는 쌍을 구한다.

-> 내림차순으로 구성된 스택에서 상단 원소보다 현재 원소가 더 크다면, 현재원소보다 작거나 같은 원소는 모두 pop ,

이때 볼 수 있는 쌍을 구한다.

5번째 사람의 서로 볼 수 있는 쌍을 구해보자.

첫번째 사람은 두번째사람에 의해 볼 수 없다.

두번째 사람은 서로 볼 수 있는 쌍이다.

세번째 사람은 네번째 사람에 의해 볼 수 없다.

네번째 사람은 키가 같고 인접해있으므로 볼 수 있다.

이때 스택에는 현재 사람보다 키가 큰 인원만 저장한다.

(저장되어 있는 원소중에 현재 키보다 작은 사람들은 pop하여 쌍의 개수를 세주었다.)

스택에서 값이 빠지는 과정

이때 키가 같다면 키가 같은 인원을 추가해주고 스택에 저장한다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = [Int]()
// 스택에 튜플형식으로 저장
// 같은 높이의 인원도 볼 수 있으므로
var stack = [(num: Int, height: Int)]()
var count = 0
for i in 0..<N {
    arr.append(Int(readLine()!)!)
}
print(arr)
for i in 0..<arr.count {
    var current = (num: 1, height: arr[i])
    // 현재 사람의 높이보다 작거나 같은 인원들은 모두 볼 수 있는사람들이다.
    // 해당 인원들은 모두 볼 수 있는 쌍이 되므로, 그만큼 count를 더해준다.
    // 키가 같은 인원도 볼 수 있으므로, 키가 같다면 키가 같은 인원수를 더해서 스택에 다시 넣어준다.
    while !stack.isEmpty && stack.last!.height <= current.height {
        if stack.last!.height == arr[i] {
            count += stack.last!.num
            current.num += stack.removeLast().num
        } else if stack.last!.height < arr[i] {
            count += stack.removeLast().num
        }
    }
    // 스택은 키가 내림차순으로 저장된다.
    // 스택에 값이 존재한다면, 이는 내림차순으로 정렬되었을때
    // 현재 사람과 바로 직전의 사람과의 중간은 사람이 존재하지않으므로 무조건 볼 수 있는 사이다.
    if !stack.isEmpty {
        count += 1
    }
    stack.append(current)
}
print(count)

내가 푼 풀이

접근방법: 스택

이전문제인 오큰수를 풀었다면 원리를 알기 쉽다.

주어진 수열을 왼쪽부터 검사한다면, 오른쪽에 위치한 수를 모두파악해야하므로 O($N^{2}$)가 걸린다.

주어진 수열을 반대로 오른쪽부터 왼쪽순으로 검사한다.

스택의 상단 원소와 현재 원소를 비교한다.

스택이 비어있다면, 오등큰수가 존재하지않는다는 의미다

스택이 비어있지않다면, 현재원소와 비교하여 등장횟수가 작거나 같은 원소들은 모두 Pop한다.

이렇게 스택의 원소들을 비워주었다면, 스택의 상단원소는 현재원소의 오등큰수가 된다.

스택이 비어있다면 오등큰수가 존재하지않음(-1)

스택을 갱신해주며 수열의 첫번째 원소까지 검사해준다.

등장횟수를 저장할 딕셔너리를 선언했지만, 시간초과가 났다.

배열의 크기를 100만으로 선언후 등장횟수를 저장했더니, 딕셔너리보다 더 빠르게 접근 가능했다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = Array(readLine()!.split(separator: " ").map{Int(String($0))!}.reversed())
// 등장횟수 저장할 배열
var nums = Array(repeating: 0, count: 1000001)
for i in arr {
    nums[i] += 1
}
// 스택과 결과를 저장할 배열
var result = [Int]()
var stack = [Int]()
var answer = ""

// 주어진 수열의 마지막원소부터 검사
for i in 0..<arr.count {
    // 스택의 상단원소가 현재원소보다 등장횟수가 많은 원소가 위치하도록 Pop
    while !stack.isEmpty && nums[stack[stack.count-1]] <= nums[arr[i]] {
        stack.removeLast()
    }
    // 스택이 비어있다면 오등큰수는 존재하지않음
    // 비어있지 않다면 오등큰수는 스택의 상단원소가 됨
    if stack.isEmpty {
        result.append(-1)
    } else {
        result.append(stack.last!)
    }
    // 오른쪽에 위치한 원소중 가장 왼쪽에 있는 원소가 오등큰수가 되므로 현재원소를 스택에 넣어준다.
    stack.append(arr[i])
}

// 결과 출력
for i in (0..<result.count).reversed() {
    if i == 0 {
        answer += "\(result[i])"
    } else {
        answer += "\(result[i]) "
    }
}
print(answer)