Jenikeju

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

내가 푼 풀이

- 주어진 지도를 배열로 입력한다.

- 입력하면서 섬의 위치 (x, y) (값이 1)를 저장해 둔다.

- 섬의 위치로 DFS 탐색 후 모든 인접한 곳(8방향)이 섬인 곳을 탐색한다면 카운트해 준다.

- 카운트한 값 출력

import Foundation

// 8가지 방향
var dx = [0, 1, 1, 1, 0, -1, -1, -1]
var dy = [1, 1, 0, -1, -1, -1, 0, 1]

// DFS
while true {
    // 0 0 입력시 반복탈출
    var input = readLine()!.split(separator: " ").map{ Int($0)! }
    let w = input[0]
    let h = input[1]
    if w == h && h == 0 {
        break
    }
    
    // DFS 탐색을 위한 변수
    var needVisitQueue = [(x: Int, y: Int)]()
    var finalVisitedQueue = [(x: Int, y: Int)]()
    var count = 0
    var arr = [[Int]]()

    // 배열로 입력받아 1의 위치를 저장해둔다.
    for i in 0..<h {
        arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
        for j in 0..<arr[i].count {
            if arr[i][j] == 1 {
                finalVisitedQueue.append((x: j, y: i))
            }
        }
    }
    
    // 1과 인접한 모든 위치중 값이 1인곳을 모두 탐색 후 카운트
    while !finalVisitedQueue.isEmpty {
        needVisitQueue = [finalVisitedQueue.removeLast()]
        if arr[needVisitQueue[0].y][needVisitQueue[0].x] == -1 { continue }
        while !needVisitQueue.isEmpty {
            var loc = needVisitQueue.removeLast()
            arr[loc.y][loc.x] = -1
            for i in 0..<8 {
                var x1 = loc.x + dx[i]
                var y1 = loc.y + dy[i]
                
                if (x1 >= 0 && x1 < w) && (y1 >= 0 && y1 < h) {
                    if arr[y1][x1] == 1 {
                        needVisitQueue.append((x: x1, y:y1))
                    }
                }
            }
        }
        count += 1
    }
    print(count)
}

내가 푼 풀이

- 주어진 크레인과 박스를 배열로 입력한다.

- 크레인의 무게 한도가 높은 크레인을 우선으로 무게가 높은 박스를 옮긴다.

- 크레인의 무게 한도보다 높은 무게의 박스가 있는 경우 옮길 수 없다.

import Foundation

let count = Int(readLine()!)!
var crain = readLine()!.split(separator: " ").map{ Int($0)! }
let boxCount = Int(readLine()!)!
var box = readLine()!.split(separator: " ").map{ Int($0)! }
var time = 0

// 크레인과 박스 내림차순
crain.sort{ $0 > $1}
box.sort{ $0 > $1}

// 크레인중에 박스의 무게보다 무게제한이 낮은 크레인은 지운다.
while !crain.isEmpty && crain[crain.endIndex - 1] < box[box.endIndex - 1] {
    crain.removeLast()
}

// 옮길수 없다면 -1
// 크레인의 무게제한이 큰것부터 무게가 많이나가는 박스를 우선으로 옮겨준다.
if crain.count == 0 || crain[0] < box[0] {
    print(-1)
} else {
    while !box.isEmpty {
        var c = crain
        for i in 0..<crain.count {
            var idx = 0
            while idx < box.count && crain[i] < box[idx] {
                idx += 1
            }
            if idx < box.count {
                box.remove(at: idx)
            }
        }
        time += 1
    }
    print(time)
}

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

내가 푼 풀이

- 사자를 배치할때, 가로 세로로 붙어있게 배치할 수 없다.

- 사자를 한마리도 배치하지 않는 경우도 포함한다.

- 결국 N칸이 늘어나도 생기는 경우의수는 두 가지다. N번째에 사자를 채우는 경우와 채우지 않는 경우

- N = 1 일 때, 사자를 채우는 방법은 사자가 0마리일때 1 , 사자가 1마리일때 2 총 3가지이다.

- N = 2 일때, 2번째에 사자를 채우는 경우 바로 이전의 사자의 위치에 따라 다르지만 칸이 2개 더 생기므로 3 * 2 = 6이다.

- 반대로 사자를 채우지 않는 경우는 위에 사자를 채울 때, 이전의 위치까지 고려하여 경우의수를 정했으므로 아예 채우지 않는경우는

- n-2 위치까지의 경우의 수가 된다.

- 이를 점화식으로 나타내면 다음과 같다.  "dp[n] = 2 * n 칸에 사자를 채우는 경우의 수"

- dp[n] = 2 * dp[n-1] + dp[n-2]

import Foundation

let count = Int(readLine()!)!
var dp = Array(repeating: 0, count: 100001)
dp[0] = 1

// dp 입력
for i in 1...count {
    if i == 1 {
        dp[1] = 3
        continue
    }
    dp[i] = (2 * dp[i-1] + dp[i-2]) % 9901
}

print(dp[count])

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

내가 푼 풀이

- 토마토 위치를 3차원 배열로 저장하면서, 토마토의 위치를 따로 저장해둔다.

- 토마토의 위치를 시작점으로 BFS로 인접한 위치들을 익힌다.

- 토마토의 모든 위치를 인접한 위치에 익혀주면 카운트해 준다.

- 마지막으로 모든 위치를 검사해 남은 익지 않은 토마토가 있다면 익힐 수 없으므로 -1 출력, 없다면 카운트 출력

import Foundation

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let m = input[0]
let n = input[1]
let h = input[2]
var arr = [[[Int]]]()
var a = [[Int]]()
var needVisitQueue = [(x: Int, y: Int, z: Int)]()
var realNeedVisitQueue = [(x: Int, y: Int, z: Int)]()
var result = 0
var cant = false
var dx = [0, 0, 1, 0, -1, 0]
var dy = [0, 0, 0, 1, 0, -1]
var dz = [1, -1, 0, 0, 0, 0]
var z = 0

// 토마토 위치를 배열에 입력
// 입력할때, 토마토의 위치를 저장 (시작점)
for i in 0..<n*h {
    var inp = readLine()!.split(separator: " ").map{ Int($0)! }
    for j in 0..<inp.count {
        if inp[j] == 1 {
            realNeedVisitQueue.append((x: j, y: i % n, z: z))
        }
    }
    a.append(inp)
    if (i+1) % n == 0 {
        arr.append(a)
        a.removeAll()
        z += 1
    }
}

// 토마토 익히기 BFS
// 저장해둔 시작점부터 인접한곳에 있는 토마토를 익혀준다.
// 인접한 좌표를 따로 저장하고 익히면 카운트
while !realNeedVisitQueue.isEmpty {
    var saveLocation = [(x: Int, y: Int, z: Int)]()
    needVisitQueue = realNeedVisitQueue
    
    while !needVisitQueue.isEmpty {
        var loc = needVisitQueue.removeLast()
        
        for i in 0..<6 {
            var x1 = loc.x + dx[i]
            var y1 = loc.y + dy[i]
            var z1 = loc.z + dz[i]
            
            if (x1 >= 0 && x1 < m) && (y1 >= 0 && y1 < n) && (z1 >= 0 && z1 < h) {
                if arr[z1][y1][x1] == 0 {
                    arr[z1][y1][x1] = 1
                    saveLocation.append((x: x1, y: y1, z: z1))
                }
            }
        }
    }
    realNeedVisitQueue = saveLocation
    if realNeedVisitQueue.count != 0 {
        result += 1
    }
}

// 마지막으로 익히지않은 토마토가 있는지 검사
for i in 0..<h {
    for j in 0..<n {
        for k in 0..<m {
            if arr[i][j][k] == 0 {
                cant = true
                continue
            }
        }
    }
}
if cant {
    print(-1)
} else {
    print(result)
}

내가 푼 풀이

- 집의 위치가 배열로 주어질때, 오름차순으로 정렬한다.

- 오름차순으로 정렬하면 배열의 중간 인덱스의 값이 모든 집까지의 거리의 총합이 최소가 된다.

- 배열의 개수가 짝수면 중간값이 두 개 이상이 되는데, 이는 중간값 중 가장 작은 값을 출력하면 된다.

- 배열의 개수가 홀수면 정확히 중간값이 나와서, 배열의 중간값을 출력한다.

- 배열의 인덱스가 0부터 시작하므로, 배열의 개수-1 값을 2로 나눈 위치를 출력한다.

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
arr.sort{ $0 < $1}
if count == 1 {
    print(arr[0])
} else {
    print(arr[(count-1) / 2])
}

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

< 그림 1 >

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

내가 푼 풀이

- 전깃줄이 1번부터 차례대로 추가된다고 생각해 보자 A번호를 B번호로 연결.

- 1번 전깃줄을 연결하면 제거해야할 전깃줄은 0개

- 2번 전깃줄을 연결하면 1번 전깃줄과 연결된 B번호보다 높은 숫자여야 한다. 1번의 B번호보다 작은 번호에 연결되면 교차되므로 제거해야 한다.

- 3번 전깃줄을 연결하면, 1번과 2번 전깃줄이 연결된 B번호보다 높아야 하고, 3번 전깃줄의 B번호보다 큰 전깃줄은 교차되므로 제거해야 한다.

- 이 특성을 이용하여 위 예시로 주어진 전깃줄을 A번호를 기준으로 정렬하면 다음과 같다.

- 전깃줄을 연결할 때, 다음전깃줄은 이전 전깃줄의 A번호와 B번호보다 크면 교차하지 않는다.

- 문제는 제거해야 하는 전깃줄의 최소 개수를 구하는 문제이므로, 위와 같이 정렬했을 때, A번호는 오름차순으로 정렬되어 있으니, 이를 기준으로 B번호의 가장 증가하는 긴 수열의 길이를 구하면 된다.

- 수열의 길이를 구한 후, 전깃줄의 개수에서 빼주면 제거해야 할 줄의 개수가 나온다.

이를 코드로 구현해 보자.

import Foundation

let count = Int(readLine()!)!
var a = Array(repeating: 0, count: 501)
var arr = [Int]()

// 연결된 전깃줄 입력 후, A번호 기준으로 오름차순으로 정렬된 B번호 배열 구하기
for i in 0..<count {
    var input = readLine()!.split(separator: " ").map{ Int($0)! }
    a[input[0]] = input[1]
}
for i in a {
    if i == 0 { continue }
    arr.append(i)
}
arr.insert(0, at: 0)
var dp = Array(repeating: 1, count: arr.count+1)

// DP
// DP[n] = n번째 원소를 포함시킨 부분수열의 길이
// 가장 긴 증가하는 부분수열 길이 구하기
for i in 1...count {
    for j in 1..<i {
        if arr[i] > arr[j] {
            dp[i] = dp[j] + 1
        }
    }
}
print(count - dp.max()!)

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

내가 푼 풀이

- 해당 그림이 주어지면, 색의 구역의 수를 출력한다.

- 적록색약은 R,G 를 구분하지못하므로, 그래프를 탐색할 때, R과G는 같다고 판단하고 탐색한다.

- 단순히 구역의 수를 구하는 문제이므로 BFS, DFS 둘다 사용 가능하지만, DFS를 사용했다.

import Foundation

var n = Int(readLine()!)!
var arr = [[String]]()
var result = [Int]()

// dif 는 적록색약인지 판단
var dif = false
// x y 방향
var dx = [1,0,-1,0]
var dy = [0,1,0,-1]

// 그립을 배열에 입력
for i in 0..<n {
    var input = Array(readLine()!).map{ String($0) }
    arr.append(input)
}

// 결과 두가지 호출을 위한 result 배열
// 단순히 구역의 수를 구하기위하므로 DFS 이용
while result.count != 2 {
    var needVisitQueue = [(x: Int, y: Int)]()
    var count = 0
    var copyArr = arr
    // 정상인 사람의 구역 수 를 넣으면 색약인사람을 검사
    if result.count == 1 {
        dif = true
    } else {
        dif = false
    }
    // 정상인 사람의 구역의 개수 구하기
    if !dif {
        for i in 0..<copyArr.count {
            for j in 0..<copyArr.count {
                if copyArr[i][j] == "X" { continue }
                needVisitQueue.append((x: j, y: i))
                var check = copyArr[i][j]
                while !needVisitQueue.isEmpty {
                    var node = needVisitQueue.removeLast()
                    copyArr[node.y][node.x] = "X"
                    
                    for k in 0..<4 {
                        var cx = node.x + dx[k]
                        var cy = node.y + dy[k]
                        
                        if (cx >= 0 && cx < n) && (cy >= 0 && cy < n) {
                            if copyArr[cy][cx] == check {
                                needVisitQueue.append((x: cx, y: cy))
                            }
                        }
                    }
                }
                count += 1
            }
        }
        result.append(count)
    } else {
        // 적록색약인 사람의 구역의 개수 구하기
        for i in 0..<copyArr.count {
            for j in 0..<copyArr.count {
                if copyArr[i][j] == "X" { continue }
                needVisitQueue.append((x: j, y: i))
                var check = copyArr[i][j]
                while !needVisitQueue.isEmpty {
                    var node = needVisitQueue.removeLast()
                    copyArr[node.y][node.x] = "X"
                    
                    for k in 0..<4 {
                        var cx = node.x + dx[k]
                        var cy = node.y + dy[k]
                        
                        if (cx >= 0 && cx < n) && (cy >= 0 && cy < n) {
                            if check == "R" || check == "G" {
                                if copyArr[cy][cx] == "R" || copyArr[cy][cx] == "G" {
                                    needVisitQueue.append((x: cx, y: cy))
                                }
                            } else if copyArr[cy][cx] == check {
                                needVisitQueue.append((x: cx, y: cy))
                            }
                        }
                    }
                }
                count += 1
            }
        }
        result.append(count)
    }
}

print(result.map{String($0)}.joined(separator: " "))

내가 푼 풀이

- 주어진 문자열들의 열들을 비교해가며, 가장 많은 문자를 따온다.

- 만약 해당 열에 여러개의 문자의 수가 같다면, 사전순으로 앞에 있는 문자를 따온다.

- Hamming Distance는 해당 문자와 다른 문자의 갯수다. 

- 문자를 따올때, 해당문자와 다른 문자의 개수를 더해주면 주어진 문자열들과 Hamming Distance의 합이 가장 작은 DNA가 되고,

그 합이 이전에 더해진 수와 같다.

코드로 구현하면 다음과 같다.

import Foundation

let input = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [[String]]()
var str = ""
var hd = 0

// 문자열 입력
for i in 0..<input[0] {
    arr.append(Array(readLine()!).map{String($0)})
}

// 주어진 문자열의 열을 모두 비교
// 문자와 문자의 개수를 구한다.
// 문자를 배열에 저장해 오름차순으로 정렬하면 0번째 원소가 사전순으로 가장 앞선다.
// 해당 문자와 다른문자의 개수를 더해가면 주어진 문자열들과 Hamming Distance의 합이 최소가 된다.
for i in 0..<input[1] {
    var dict = [String: Int]()
    for j in 0..<input[0] {
        if dict[arr[j][i]] == nil {
            dict[arr[j][i]] = 1
        } else {
            dict[arr[j][i]]! += 1
        }
    }
    var hdNum = 0
    var s = [String]()
    for (key,value) in dict {
        if value == dict.values.max()! {
            hdNum = input[0] - value
            s.append(key)
        }
    }
    s.sort{ $0 < $1}
    str += s[0]
    hd += hdNum
}

print(str)
print(hd)