백준 3020 개똥벌레

출처: www.acmicpc.net/problem/3020

분류: 이분탐색

---

접근방식

이 문제는 가로 20 세로 50만이므로 모두 탐색한다거나 h만큼 일일이 배열에 담아준다거나 하는 방식으로는 시간초과를 면하기 어렵습니다.

저희가 원하는 건 특정 높이에서 만나는 장애물의 개수 입니다. 순서는 상관이 없죠! 따라서 이분탐색을 떠올려볼 수 있습니다.

대신 종유석과 석순이 서로 반대방향으로 나있기 때문에 이분탐색 upper/lower 바운드를 잘 섞어서 사용해줘야 하겠습니다.

이분탐색 upper/lower bounds가 익숙하지 않으시다면 여기를 읽어주세요 :]

 

조금 더 구체적으로 알아볼게요.

석순과 종류석의 높이를 따로 배열에 담고 정렬해줍니다.

저는 석순이 난 방향부터 높이를 1로 생각해서 계산해보려고 합니다.

해당 높이에서 만나야하는 석순의 개수는 처음으로 해당 높이를 만나는 인덱스, 그 다음은 모두 더 크기 때문에 다 부셔야 합니다.

--> 장애물의 개수: 석순의 개수 - lower bounds

종유석은 반대기 때문에 (총 높이 H - 현재 높이)로 생각해줬고, 
만나야하는 종유석의 개수는 해당 높이보다 처음으로 커지는 인덱스, 거기부터 끝까지는 더 크기 때문에 다 부셔야 합니다.

--> 장애물의 개수: 종유석의 개수 - upper bounds

이후에는 개수를 키로해서 딕셔너리에 담아줘서 마무리 했습니다 :]

 

해결방법

let nh = readLine()!.split(separator: " ").map { Int(String($0))! }
var stal = [Int]()
var opStal = [Int]()

for i in 0..<nh[0] {
  if i % 2 == 0 {
    stal.append(Int(readLine()!)!)
  } else {
    opStal.append(Int(readLine()!)!)
  }
}

stal.sort()
opStal.sort()

func binary(_ array: [Int], target: Int, isUpper: Bool) -> Int {
  var low = 0
  var high = array.count
  
  while low < high {
    let mid = (low + high)/2
    if target == array[mid] {
      isUpper ? (low = mid+1) : (high = mid)
    } else if target < array[mid] {
      high = mid
    } else {
      low = mid+1
    }
  }
  return low
}

var minTable = [Int: Int]()
var minKey = 555555

for height in 1...nh[1] {
  var count = stal.count - binary(stal, target: height, isUpper: false)
  count += opStal.count - binary(opStal, target: nh[1] - height, isUpper: true)
  
  if minTable.keys.contains(count) {
    minTable[count]! += 1
  } else {
    minTable[count] = 1
    if count < minKey {
      minKey = count
    }
  }
}

print(minKey, minTable[minKey]!)

 

배운점

가장 빨리 푸신 분의 풀이를 봤는데 잘 이해가 가지 않는다 🧐 

이분탐색이 아니고 어떻게 어떻게 전처리만 더 해주시고 푸신 것 같은데..

다음에 좀 더 배우고 다시 보면 이해가 가려나....