[Baekjoon] 10775 공항

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

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

10775번: 공항

요약 

공항에 비행기를 도착한 순서대로 도킹시키는데

i번째 비행기는 1 ~ g(i)번째 게이트 중 하나에 도킹을 할 수 있다고 합니다.

이 뜻은 만약 5번째 비행기가 3이라면

1번째 게이트, 2번째 게이트, 3번째 게이트 3개 중 하나에 도킹을 시킬 수 있습니다.

 

전 문제 처음에 대충 읽고 그냥 단순히 3이면 3번째 게이트에 도킹시키면 되겠지 라고 생각했다가 

바로 틀렸습니다......하하

문제풀이

이 문제를 첨에 어케 풀지 생각하다가 그리디 문제인 것 같아서 그리디하게 풀기 시작했어요. 

자료구조는 딕셔너리를 사용해서 

만약 A라면, A부터 하나씩 채워나갔어요. 

A가 이미 도킹되어있다면, A-1에 도킹시켰고, A-1도 이미 도킹되어있다면 A-2에 도킹! 

이런식으로 하나씩 채워나가서 0에 도달하면 더이상 도킹할 수 없다고 판단하고 정답을 return 했습니다. 

그 풀이는 아래와 같아요.

if let gateNumber = readLine(),
   let _ = Int(gateNumber),
   let airplaneNumber = readLine(),
   var airplaneNumber = Int(airplaneNumber) {
  var dockingPlace: [Int:Int] = [:]
  var count = 0
  while (airplaneNumber > 0) {
    airplaneNumber -= 1
    count += 1
    if let g = readLine(),
       var g = Int(g) {
      var done = false
      if let _ = dockingPlace[g] {
        while (g >= 1) {
          g -= 1
          if g == 0 {
            break
          }
          if let _ = dockingPlace[g] {
            continue
          } else {
            dockingPlace[g] = count
            done = true
            break
          }
        }
      } else {
        done = true
        dockingPlace[g] = count
      }
      if done {
        continue
      } else {
        break
      }
    }
  }
  print(dockingPlace.count)
}

하지만 이렇게 푸니까 시간초과가 나더라구요.

게이트와 비행기 모두 10만개까지 가능한데

최악의 경우로 

전부 100,000인 비행기가 들어와 버리면 10,000,000,000번 ....

즉 100억번 중첩 for문을 돌아버리게 되네요.

거뜬히 1초를 넘기게 되죠.

 

그래서 생각한 풀이는,

다음 도킹할 수 있는 게이트를 바로 가리켜 버리기 였습니다.

그 방법에 UnionFind알고리즘이 필요했어요.

A인 비행기가 들어오면 A의 parent를 찾아(find)

parent와 parent-1과 union을 해주면 

결국에는 0에 도달하게 됩니다! 

0이면 이제 while문을 끝내면 되구요!

 

아래 UnionFind 자료구조는 여기를 참고하였고 unionSetsContaining부분만 parent쪽에 합치는 것으로 수정해주었어요. 

struct UnionFind<T: Hashable> {
  private var index = [T: Int]()
  private var parent = [Int]()
  private var size = [Int]()
  
  mutating func addSetWith(_ element: T) {
    index[element] = parent.count
    parent.append(parent.count)
    size.append(1)
  }
  
  mutating func setOf(_ element: T) -> Int? {
    if let indexOfElement = index[element] {
      return setByIndex(indexOfElement)
    } else {
      return nil
    }
  }
  
  mutating func setByIndex(_ index: Int) -> Int {
    if parent[index] == index {
      return index
    } else {
      parent[index] = setByIndex(parent[index])
      return parent[index]
    }
  }
  
  mutating func inSameSet(_ firstElement: T, and secondElement: T) -> Bool {
    if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) {
      return firstSet == secondSet
    } else {
      return false
    }
  }
  
  mutating func unionSetsContaining(parent firstElement: T, child secondElement: T) {
    if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) {
      if firstSet != secondSet {
        parent[secondSet] = firstSet
        size[firstSet] += size[secondSet]
      }
    }
  }
}

그리고 아래는 위의 자료구조를 사용해서 푼 풀이입니다!

if let gateNumber = readLine(),
   let gateNumber = Int(gateNumber),
   let airplaneNumber = readLine(),
   var airplaneNumber = Int(airplaneNumber) {
  var dataStructure = UnionFind<Int>()
  for i in 0...gateNumber {
    dataStructure.addSetWith(i)
  }
  
  var answer = 0
  while (airplaneNumber > 0) {
    airplaneNumber -= 1
    if let g = readLine(),
       let g = Int(g),
       let docking = dataStructure.setOf(g) {
      if docking == 0 { break }
      answer += 1
      dataStructure.unionSetsContaining(parent: docking-1, child: docking)
    }
  }
  print(answer)
  
}