연습문제(벽과 폭탄)

벽과 폭탄

각 테스트 케이스마다 ‘W’, ‘B’로 이루어진 문자열이 입력된다. B는 폭탄을, W는 벽을 의미하는데, 폭탄이 하나 터지면 폭탄을 중심으로 반경 2칸 이내의 벽이 모두 폭파된다. 이 때 폭탄이 일시에 터졌을 때 폭파되는 벽의 개수를 출력하라. (https://www.hackerearth.com/problem/algorithm/bob-and-bombs-cake-walk/description/)

BWW, BW, WB, WWB에 해당하는 W의 수를 세는 문제이므로, 이는 간단하게 정규식으로 해결할 수 있다.

import re
t = int(input())
r = re.compile(r'W{1,2}(?=B)|(?<=B)W{1,2}')
for _ in range(t):
  s = input()
  g = r.findall(s)
  print(len("".join(list(g))))

문제에서 주어진 수행시간은 5초인데, 대부분의 경우 0.1초 수준에서 해결됐다. 심지어 이런 문항도 순식간에 계산됐다. (https://he-s3.s3.amazonaws.com/media/hackathon/better-programming/problems/5c1a7faa-4-input-5c1a7b6.txt?Signature=nTVmjOymYYGiG1irF1haJJSfQhs%3D&Expires=1465883451&AWSAccessKeyId=AKIAJLE6MUHDYS3HN6YQ)

Swift 버전

되는지는 안해봤다.

import Foundation
let t = Int(readLine()!)!
for _ in 1...t {
  let s = readLine()!
  if let exp = try? NSRegulareExpression(pattern: "W{1,2}(?=B)|(?<=B)W{1,2}", options:[]) {
    var result = 0
    let matches = exp.matchesInString(s, options:[], range:NSMakeRange(0, s.characters.count))
    for match in matches {
      let f = match.rangeAtIndex(0)
      result += f.length
    }
    print(result)
  }
}

정규식 없이 처리하는 방법

된다. (https://paiza.io/projects/RUNGu4B_aWX9GUoEybafYg)
폭탄 왼쪽의 벽이 파괴되는 케이스와 폭탄 오른쪽이 파괴되는케이스를 각각 따져서 진행한다. 한 번에 최대 3개씩 스캔해나가면서 스캔한 범위에서 B의 위치에 따라 1개 혹은 2개의 폭탄이 파괴되면 된다. 유효 폭발을 일으킨 폭탄을 다시 스캔 범위의 첫번째 위치에 오도록 다음 범위를 잡아서 진행해나가면 된다.

let t = Int(readLine()!)!
    for _ in 1...t {
    let s = readLine()!.characters.map{ String($0) }
    let l = s.count
    var i = 0
    var result = 0
    while i < s.count - 2 {
        let p = (s[i], s[i+1], s[i+2])
        switch p {
        case ("W", "W", "B"):
            result += 2
            i += 2
        case ("W", "B", _):
            result += 1
            i += 1
        case ("B", "W", "W"):
            result += 2
            i += 3
        case ("B", "W", "B"):
            result += 1
            i += 2
        default:
            i += 1
        }
    }
    print(result)
}