백준 Swift 1743번, 2667번, 2583번, 2468번, 7562번, 1697번, 1182번, 2512번, 10815번,

Swift 5 | 코테/백준 | 실버 - 문제풀이 / / 2022. 3. 24. 18:47

문제 풀이를 할 때 마다 계속 추가됩니다.

cmd + F 를 통해 문제번호 찾기를 추천드립니다.

 

22.03.24 업데이트

22.03.27 업데이트

22.03.29 업데이트

22.03.30 업데이트

22.04.04 업데이트

22.04.05 업데이트

 

아래 깃허브 주소에서 모든 백준 문제풀이를 확인하실 수 있습니다.

https://github.com/SuminPark-developer/BaekJoonPS

 

GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS

백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.

github.com

백준 Swift 1743번(DFS)

// MARK: - 1743번(DFS)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, K) = (input[0], input[1], input[2])
var board = Array(repeating: Array(repeating: ".", count: M + 1), count: N + 1)
var visited = Array(repeating: Array(repeating: false, count: M + 1), count: N + 1)

for _ in 0..<K {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (r, c) = (input[0], input[1])
    
    board[r][c] = "#" // 음식물 표시.
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func isValidCoord(_ y: Int, _ x: Int) -> Bool { // board 밖으로 안나가야됨.
    return (1 <= y && y <= N) && (1 <= x && x <= M)
}

var count: Int = 0
var temp: [Int] = []

func dfs(_ y: Int, _ x: Int) {
    for k in 0..<4 {
        let ny = y + dy[k]
        let nx = x + dx[k]
        
        if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == "#" {
            visited[ny][nx] = true
            count += 1
            dfs(ny, nx)
        }
    }
}

for y in 1...N {
    for x in 1...M {
        if !visited[y][x] && board[y][x] == "#" {
            visited[y][x] = true
            count = 1 // 방문한거로 되면서, 음식물 크기 1부터 시작.
            dfs(y, x)
            
            temp.append(count)
        }
    }
}

print(temp.max()!)

백준 Swift 1743번(BFS)

// MARK: - 1743번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, K) = (input[0], input[1], input[2])
var board = Array(repeating: Array(repeating: ".", count: M + 1), count: N + 1)
var visited = Array(repeating: Array(repeating: false, count: M + 1), count: N + 1)

for _ in 0..<K {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (r, c) = (input[0], input[1])
    
    board[r][c] = "#"
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (1 <= y && y <= N) && (1 <= x && x <= M)
}


func bfs(_ startY: Int, _ startX: Int) -> Int {
    visited[startY][startX] = true
    var count: Int = 1
    let q = Dequeue([(startY, startX)])
    
    while !q.isEmpty {
        let (y, x) = q.popFirst()
        
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            
            if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == "#" {
                visited[ny][nx] = true
                count += 1
                q.pushLast((ny, nx))
            }
        }
    }
    return count
}

var temp: [Int] = []

for y in 1...N {
    for x in 1...M {
        if !visited[y][x] && board[y][x] == "#" {
            visited[y][x] = true
            let count = bfs(y, x)
            temp.append(count)
        }
        
    }
    
}

print(temp.max()!)

 

백준 Swift 2667번(DFS)

// MARK: - 2667번(DFS)
let N = Int(readLine()!)!
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
for _ in 0..<N {
    let input = readLine()!.map{Int(String($0))!}
    board.append(input)
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < N) && (0 <= x && x < N)
}

var count: Int = 0

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func dfs(_ y: Int, _ x: Int) {
    for k in 0..<4 {
        let ny = y + dy[k]
        let nx = x + dx[k]
        if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == 1 {
            visited[ny][nx] = true
            count += 1
            dfs(ny, nx)
        }
    }
}


var temp: [Int] = []
for y in 0..<N {
    for x in 0..<N {
        if !visited[y][x] && board[y][x] == 1 {
            count = 1
            visited[y][x] = true
            dfs(y, x)
            temp.append(count)
        }
    }
    
}

temp.sort(by: <)

print(temp.count)

for num in temp {
    print(num)
}

백준 Swift 2667번(BFS)

// MARK: - 2667번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}
let N = Int(readLine()!)!
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
for _ in 0..<N {
    let input = readLine()!.map{Int(String($0))!}
    board.append(input)
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < N) && (0 <= x && x < N)
}

var count: Int = 0

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func bfs(_ startY: Int, _ startX: Int) -> Int {
    visited[startY][startX] = true
    let q = Dequeue([(startY, startX)])
    count = 1
    
    while !q.isEmpty {
        let (y, x) = q.popFirst()
        
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            
            if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == 1 {
                visited[ny][nx] = true
                count += 1
                q.pushLast((ny, nx))
            }
        }
    }
    return count
}

var temp: [Int] = []

for y in 0..<N {
    for x in 0..<N {
        if !visited[y][x] && board[y][x] == 1 {
            visited[y][x] = true
            let count = bfs(y, x)
            temp.append(count)
        }
        
    }
}

temp.sort(by: <)

print(temp.count)

for num in temp {
    print(num)
}

 

백준 Swift 2583번(DFS)

// MARK: - 2583번(DFS)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N, K) = (input[0], input[1], input[2])
var board = Array(repeating: Array(repeating: 0, count: N), count: M)
var visited = Array(repeating: Array(repeating: false, count: N), count: M)

for _ in 0..<K {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (x1, y1, x2, y2) = (input[0], input[1], input[2], input[3])
    
    for y in y1..<y2 { // 직사각형에 속하는 부분을 다 1처리.
        for x in x1..<x2 {
            board[y][x] = 1
        }
    }
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < M) && (0 <= x && x < N)
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
var count: Int = 0

func dfs(_ y: Int, _ x: Int) {
    for k in 0..<4 {
        let ny = y + dy[k]
        let nx = x + dx[k]
        
        if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == 0 {
            visited[ny][nx] = true
            count += 1
            dfs(ny, nx)
        }
    }
}

var temp: [Int] = []
for y in 0..<M {
    for x in 0..<N {
        if !visited[y][x] && board[y][x] == 0 {
            visited[y][x] = true
            count = 1
            dfs(y, x)
            temp.append(count)
        }
    }
    
}

temp.sort(by: <)
print(temp.count)
print(temp.map{String($0)}.joined(separator: " "))

백준 Swift 2583번(BFS)

// MARK: - 2583번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N, K) = (input[0], input[1], input[2])
var board = Array(repeating: Array(repeating: 0, count: N), count: M)
var visited = Array(repeating: Array(repeating: false, count: N), count: M)
for _ in 0..<K {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (x1, y1, x2, y2) = (input[0], input[1], input[2], input[3])
    
    for y in y1..<y2 {
        for x in x1..<x2 {
            board[y][x] = 1
        }
    }
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < M) && (0 <= x && x < N)
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
var count: Int = 0

func bfs(_ startY: Int, _ startX: Int) -> Int {
    visited[startY][startX] = true
    count = 1
    let q = Dequeue([(startY, startX)])
    
    while !q.isEmpty {
        let (y, x) = q.popFirst()
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            
            if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == 0 {
                visited[ny][nx] = true
                count += 1
                q.pushLast((ny, nx))
            }
        }
    }
    return count
}


var temp: [Int] = []
for y in 0..<M {
    for x in 0..<N {
        if !visited[y][x] && board[y][x] == 0 {
            visited[y][x] = true
            let area = bfs(y, x)
            temp.append(area)
        }
        
    }
}

temp.sort(by: <)
print(temp.count)
print(temp.map{String($0)}.joined(separator: " "))

 

백준 Swift 2468번(DFS)

// MARK: - 2468번(DFS)
let N = Int(readLine()!)!
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: false, count: N), count: N)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    board.append(input)
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < N) && (0 <= x && x < N)
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]


func dfs(_ y: Int, _ x: Int, _ standardHeight: Int) {
    for k in 0..<4 {
        let ny = y + dy[k]
        let nx = x + dx[k]
        
        if isValidCoord(ny, nx) && !visited[ny][nx] && (board[ny][nx] > standardHeight) {
            visited[ny][nx] = true
            dfs(ny, nx, standardHeight)
        }
    }
    
}



var area: [Int] = []
let maxHeight = board.flatMap{$0}.max()! // 기준점 - 제일 높은곳까지

for height in 0...maxHeight { // 비가 안 올 때부터 ~ 비가 최대로 올 때까지.
    visited = Array(repeating: Array(repeating: false, count: N), count: N) // 매 기준점마다, 방문기록 초기화.
    var count: Int = 0 // 영역 카운팅
    
    for y in 0..<N {
        for x in 0..<N {
            if !visited[y][x] && board[y][x] > height {
                visited[y][x] = true
                count += 1
                dfs(y, x, height)
            }
        }
    }
    area.append(count)
}

print(area.max()!)

백준 Swift 2468번(BFS)

// MARK: - 2468번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

let N = Int(readLine()!)!
var board: [[Int]] = []
var visited = Array(repeating: Array(repeating: false, count: N), count: N)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    board.append(input)
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < N) && (0 <= x && x < N)
}

func bfs(_ startY: Int, _ startX: Int, _ standardHeight: Int) {
    visited[startY][startX] = true
    let q = Dequeue([(startY, startX)])
    
    while !q.isEmpty {
        let (y, x) = q.popFirst()
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] > standardHeight {
                visited[ny][nx] = true
                q.pushLast((ny, nx))
            }
        }
    }
    
}

var area: [Int] = []
let maxHeight: Int = board.flatMap{$0}.max()!

for height in 0...maxHeight { // 비가 0부터, 최대높이까지 올 때.
    visited = Array(repeating: Array(repeating: false, count: N), count: N) // 방문기록 초기화.
    var count: Int = 0
    
    for y in 0..<N {
        for x in 0..<N {
            if !visited[y][x] && board[y][x] > height { // 방문기록 없고, 안전할 시
                visited[y][x] = true
                count += 1
                bfs(y, x, height)
            }
            
        }
        
    }
    area.append(count)
}

print(area.max()!)

 

백준 Swift 7562번

문제 유형 : BFS

난이도 : 실버1

// MARK: - 7562번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

let T = Int(readLine()!)!

let dx = [1, 2, 2, 1, -1, -2, -2, -1]
let dy = [2, 1, -1, -2, -2, -1, 1, 2]


for _ in 0..<T {
    let l = Int(readLine()!)!
    var board = Array(repeating: Array(repeating: 0, count: l), count: l)
    var visited = Array(repeating: Array(repeating: -1, count: l), count: l)
    
    var input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (stX, stY) = (input[0], input[1])
    input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (endX, endY) = (input[0], input[1])
    
    board[stY][stX] = 1
    board[endY][endX] = 2 // 임의로 2로 정함.
    
    
    func isValidCoord(_ y: Int, _ x: Int) -> Bool {
        return (0 <= y && y < l) && (0 <= x && x < l)
    }
    
    func isEscape(_ y: Int, _ x: Int) -> Bool {
        return board[y][x] == 2 // board값이 (임의로 정한) 2일 때 탈출.
    }
    
    func bfs(_ startY: Int, _ startX: Int) -> Int {
        let q = Dequeue([(startY, startX)])
        visited[startY][startX] = 0
        
        while !q.isEmpty {
            let (y, x) = q.popFirst()
            
            if isEscape(y, x) { // 목표에 도달하면,
                return visited[y][x]
            }
            
            for k in 0..<8 {
                let ny = y + dy[k]
                let nx = x + dx[k]
                
                if isValidCoord(ny, nx) && visited[ny][nx] == -1 && board[ny][nx] != 1 { // 유효 범위고, 방문한적이 없고, 시작지점이 아니면,
                    visited[ny][nx] = visited[y][x] + 1
                    q.pushLast((ny, nx))
                }
            }
            
        }
        return -1 // 불가능 시 -1 return.
    }
    
    let answer = bfs(stY, stX)
    print(answer)
}

 

백준 Swift 1697번

문제 유형 : BFS 최단거리 -  +1, -1은 상관 없는데 2배조건 때문에 dx를 쓰지 못하고, 각각을 if조건 처리해줌.

(+1,-1,*2 각각의 케이스를 모두 체크해야 하는 거기 때문에 else if로 하면 안됨!)

난이도 : 실버1

// MARK: - 1697번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var board = Array(repeating: 0, count: 100001) // 0부터 100000까지.
var visited = Array(repeating: -1, count: 100001) // 0부터 100000까지.

func isValidCoord(_ x: Int) -> Bool {
    return (0 <= x && x <= 100000)
}

func isEscape(_ x: Int) -> Bool { // 수빈이를 만나면 탈출.
    return (x == K)
}

func bfs(_ startX: Int) -> Int {
    let q = Dequeue([startX])
    visited[startX] = 0 // 첫 위치 0으로 초기화.
    
    while !q.isEmpty {
        let x = q.popFirst()
        
        if isEscape(x) { // 탈출 성공 시,
            return visited[x]
        }
        
        if isValidCoord(x + 1) && board[x + 1] == 0 && visited[x + 1] == -1 { // x+1한게 유효한 범위고, x+1이 갈 수 있는 곳이고, 미방문한 곳이면,
            visited[x+1] = visited[x] + 1
            q.pushLast(x+1)
        }
        if isValidCoord(x - 1) && board[x - 1] == 0 && visited[x - 1] == -1 { // x-1한게 유효한 범위고, x-1이 갈 수 있는 곳이고, 미방문한 곳이면,
            visited[x-1] = visited[x] + 1
            q.pushLast(x-1)
        }
        if isValidCoord(2 * x) && board[2 * x] == 0 && visited[2 * x] == -1 { // 2*x한게 유효한 범위고, 2*x이 갈 수 있는 곳이고, 미방문한 곳이면,
            visited[2*x] = visited[x] + 1
            q.pushLast(2*x)
        }
    }
    return -1
}

let answer = bfs(N)
print(answer)

 

백준 Swift 1182번

문제 유형 : 조합 or DFS

난이도 : 실버2

// MARK: - 1182번(DFS)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, S) = (input[0], input[1])
let numArray = readLine()!.split(separator: " ").map{Int(String($0))!}
var visited = Array(repeating: false, count: N)
//var sum: Int = 0
var count: Int = 0

//func dfs(_ startIndex: Int, _ depth: Int) { // ver1
//
//    if sum == S && depth > 0 { // 부분수열의 합이 S일 때,
//        count += 1
//    }
//
//    for k in startIndex..<N {
//        if !visited[k] {
//            visited[k] = true
//            sum += numArray[k]
//
//            dfs(k, depth + 1)
//
//            sum -= numArray[k]
//            visited[k] = false
//        }
//    }
//
//}

func dfs(_ startIndex: Int, _ depth: Int, _ sum: Int) { // ver2(개선)
    if sum == S && depth > 0 { // 부분수열의 합이 S일 때,
        count += 1
    }
    
    for k in startIndex..<N {
        if !visited[k] {
            visited[k] = true
            dfs(k + 1, depth + 1, sum + numArray[k])
            visited[k] = false
        }
    }
    
    
}



dfs(0, 0, 0)
print(count)

조합 - 속도 느림.

// MARK: - 1182번(조합)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, S) = (input[0], input[1])
let nums = readLine()!.split(separator: " ").map{Int(String($0))!}
var count: Int = 0

func combi(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result: [[Int]] = []

    func combination(_ index: Int , _ nowCombi: [Int]) {
        if nowCombi.count == targetNum {
            result.append(nowCombi)
            return
        }

        for i in index..<nums.count {
            combination(i + 1, nowCombi + [nums[i]])
        }
    }
    combination(0, [])
    return result
}


for k in 1...N {
    let numArray = combi(nums, k)

    for nums in numArray {
        if nums.reduce(0, +) == S {
            count += 1
        }
    }
}

print(count)

백준 Swift 2512번

문제 유형 : 파라메트릭 서치, Binary Search(이진 탐색)

- 이진탐색문제를 처음 풀어봐서 그런지, 이 문제가 이진탐색을 활용해야 하는지조차 생각하지 못했다.

난이도 : 실버3

// MARK: - 2512번(Binary Search)
let N = Int(readLine()!)!
let moneyArray = readLine()!.split(separator: " ").map{Int(String($0))!}
let M = Int(readLine()!)!
var answerMax: Int = 0

var low = 0
var high = moneyArray.max()!
var middle = (low + high) / 2

func isPossible(_ middle: Int) -> Bool {
    var sum: Int = 0
    for money in moneyArray {
        sum += min(money, middle)
    }
    return sum <= M
}

while low <= high { // Parametric Search & Binary Search
    if isPossible(middle) { // 기준예산(middle)으로 충당이 가능하면,
        low = middle + 1 // 기준예산보다 위로 다시 체크.
        answerMax = middle
    }
    else { // 기준예산(middle)으로 충당이 불가능하면,
        high = middle - 1 // 기준예산보다 밑으로 다시 체크.
    }
    
    middle = (low + high) / 2
}

print(answerMax)

더보기 - 개선전 코드

더보기

개선전 코드

// MARK: - 2512번(Binary Search)
let N = Int(readLine()!)!
let moneyArray = readLine()!.split(separator: " ").map{Int(String($0))!}
let M = Int(readLine()!)!
var answerMax: Int = 0

if moneyArray.reduce(0, +) <= M { // 모든 요청이 배정될 수 있는 경우,
    answerMax = moneyArray.max()!
}
else { // 모든 요청이 배정될 수 없는 경우,
    var start: Int = 0
    var end: Int = moneyArray.max()!
    var mid = (start + end) / 2
    
    while start <= end {
        var sum: Int = 0
        mid = (start + end) / 2
        for money in moneyArray {
            sum += money > mid ? mid : money // money가 기준(중간값)보다 크면 기준을 더하고, 기준보다 작거나 같으면 money를 더함.
        }
        if sum > M {
            end = mid - 1
        }
        else {
            start = mid + 1
        }
    }
    answerMax = end
}

print(answerMax) // 배정된 예산들 중 최댓값

백준 Swift 10815번

문제 유형 : 이분탐색(이진탐색)

난이도 : 실버4

// MARK: - 10815번(이진 탐색)
let N = Int(readLine()!)!
let sanggeunCards = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
let M = Int(readLine()!)!
let checkCards = readLine()!.split(separator: " ").map{Int(String($0))!}
var answerArray = Array(repeating: "0", count: M)

for (index, card) in checkCards.enumerated() {
    var lowIndex: Int = 0
    var highIndex: Int = N - 1
    
    while lowIndex <= highIndex { // 이진 탐색
        let middleIndex: Int = (lowIndex + highIndex) / 2
        
        if sanggeunCards[middleIndex] == card {
            answerArray[index] = "1"
            break
        }
        
        if sanggeunCards[middleIndex] < card {
            lowIndex = middleIndex + 1
        }
        else {
            highIndex = middleIndex - 1
        }
    }
    
}

print(answerArray.joined(separator: " "))

 

 

 

반응형
저작자표시 비영리 변경금지
Swift 5 | 코테/백준 | 실버 - 문제풀이 관련 글
글 더보기

티스토리툴바