문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

내가 푼 풀이

접근방법: 스택

스택을 이용하는 문제는 스택을 어떻게 활용하는지 떠오르는게 가장 중요하다.

조건을 자세히 따져보면 다음과 같다.

1. 두 사람 A와 B사이의 아무도 없다면, A,B는 서로 볼 수 있는 쌍이된다.

2. A와 B 사이에 사람이 존재하고, 모두 같은키라면 A,B는 서로 볼 수 있는 쌍이된다.

3. A와 B사이의 A또는 B보다 큰사람이 한명이라도 존재한다면, A,B는 서로 볼 수 없는 쌍이 된다.

 

예시를 통해 확인해보자.

7명 [2, 4, 1, 2, 2, 5, 1]

인덱스의 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)

+ Recent posts