[Swift 알고리즘] 백준 17615 볼 모으기

안녕하세요 코코종입니다!

4일차 문제인 볼 모으기 문제를 가져와써효

문제를 풀다가 모르게써서 구글에 검색하는데 Swift로 푼 내용이 하낫~~두 없더라구요? 도움이 되고자 글을 써봅니닷

 

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/06.
//

import Foundation

let n = Int(readLine()!)
let input = Array(readLine()!)

var arr: [Character] = []
var tmp = input.first!
arr.append(tmp)

for i in input {
    if i != tmp {
        tmp = i
        arr.append(i)
    }
}
//print(arr)

if arr.count == 1 || arr.count == 2 {
    print(0)
} else {
    print((arr.count - 1) / 2)
}

또 틀린 풀이를 가져와씁니다 >< ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

문제를 제대로 안읽어가지구... 뭉탱이를 한번에 옮기는건줄 알고 '뭐야 쉽네'라고 하면서 까불고 바로 틀렸습니다^^

(예제도 안넣어 본 나.. 눈감아..)

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/06.
//

import Foundation
// 17615 볼 모으기 그리디 실1
let n = Int(readLine()!) ?? 0
let arr = Array(readLine()!)

let redCnt = arr.filter { $0 == "R"}.count
let blueCnt = arr.filter { $0 == "B" }.count

// idea: R..B...B 또는 B...R...R 두가지 중 하나다.
// -> R를 왼쪽 or 오른쪽에 몰아넣음, B를 왼쪽 or 오른쪽으로 몰아넣음

func redToLeft() -> Int {
    // 첫 뭉탱이 R은 제외하고 뒤에 나오는 R의 갯수를 세어준다.
    var cnt = 0
    var arr = arr
    if arr.first! == "R" {
        for i in arr.firstIndex(of: "B")!..<n {
            if arr[i] == "R" { cnt += 1}
        }
    } else {
        cnt = arr.filter { $0 == "R" }.count
    }
    return cnt
}

func redToRight() -> Int {
    // 첫 뭉탱이 R은 제외하고 뒤에 나오는 R의 갯수를 세어준다.
    var cnt = 0
    var arr = arr
    arr.reverse()
    if arr.first! == "R" {
        for i in arr.firstIndex(of: "B")!..<n {
            if arr[i] == "R" { cnt += 1 }
        }
    } else {
        cnt = arr.filter { $0 == "R" }.count
    }
    return cnt
}

func blueToLeft() -> Int {
    // 첫 뭉탱이 B은 제외하고 뒤에 나오는 B의 갯수를 세어준다.
    var cnt = 0
    if arr.first! == "B" {
        for i in arr.firstIndex(of: "R")!..<n {
            if arr[i] == "B" { cnt += 1}
        }
    } else {
        cnt = arr.filter { $0 == "B" }.count
    }
    return cnt
}

func blueToRight() -> Int {
    // 첫 뭉탱이 B은 제외하고 뒤에 나오는 B의 갯수를 세어준다.
    var cnt = 0
    var arr = arr
    arr.reverse()
    if arr.first! == "B" {
        for i in arr.firstIndex(of: "R")!..<n {
            if arr[i] == "B" { cnt += 1}
        }
    } else {
        cnt = arr.filter { $0 == "B" }.count
    }
    return cnt
}

func solution() -> Int {
    return min(redToLeft(), redToRight(), blueToLeft(), blueToRight())
}

if arr.count <= 2 || redCnt == n || blueCnt == n {
    print(0)
} else {
    print(solution())
}

기본적인 아이디어는 주석으로 써있는데요! 4가지 방법 중 가장 작은 걸 고르면 됩니닷!

 

그래서 R로 시작하는데 R을 왼쪽으로 옮기는 경우에 처음에 나오는 R뭉탱이는 옮길 필요가 없어서 firstIndexOf를 활용해서 B가 나올때 까지 무시하고 지나간 다음에 나오는 애들을 옮겼답니다.

RBBRBBR 이라고 하고 R을 왼쪽으로 모는경우에 첫 R다음으로 나오는 R(index3)을 좌측으로 넘기고 나면 RRBBBBR 이 되고 또 마지막 R을 넘겨주면 되니까 이 경우에 첫 뭉탱이를 제외한 나머지 오른쪽에 있는 R의 갯수가 최소 이동 횟수가 됩니다! (잘 생각해보십셔 ><)

 

p.s 계속 75퍼에서 런타임 에러가 떴었는데... 그 이유가 맨 아래에 실수로 solution()을 또 실행시켜버렸지 뭐에요 ^^ 망충이...

열어분들은 저처럼 실수하지마세요~