Jenikeju

내가 푼 풀이

- 문제의 분류는 그리디였지만 조금 편한방법으로 풀었다.

- 연속된 하나 이상의 숫자를 뒤집을 수 있다.

- 주어진 문자열 S에서 0사이에 있는 1들의 갯수와 1사이에 있는 0들의 갯수를 구해서 둘중 최소값이 행동의 최소횟수가 된다.

• 0001100 -> ["000", "00"] , ["11"]  : 0을 1로 뒤집으면 2번 , 1을 0으로 뒤집으면 1번 뒤집게되므로 최소횟수: 1
• 11001100110011000001 -> ["00", "00", "00", "00000"] , ["11", "11", "11", "11", "1"] :
• 0을 1로 뒤집을때 4번, 1을 0으로 뒤집을때 5번이므로, 최소횟수: 4번

import Foundation

var input = readLine()!
var zero = input.split(separator: "0").count
var one = input.split(separator: "1").count
print(min(zero, one))

내가 푼 풀이

- B를 역순으로 가능한 두가지의 역연산을 한다.

- B의 최댓값이 10^9이므로 UInt64에 담아서 연산한다.

- A에서 두가지연산을 했을때 결과값이 중복이 될 수 없다.

- 2의 배수의 끝자리는 1이 될 수 없고, 뒷자리가 1이면 2의배수가 아니기때문이다.

import Foundation

let input = readLine()!.split(separator: " ").map{ UInt64($0)! }
var a = UInt64(input[0])
var b = UInt64(input[1])
var result = 1

while b != a {
    
    if b < a {
        result = -1
        break
    }
    if b % 2 == 0 {
        b /= 2
    } else if b % 10 == 1 {
        b /= 10
    } else {
        result = -1
        break
    }
    result += 1
}
print(result)

내가 푼 풀이

- 서류시험과 면접시험 둘 중 하나가 다른 지원자보다 높다면 그 지원자를 선발한다.

- 지원자의 숫자만큼 배열을 선언해서 인덱스는 서류심사의성적, 값은 면접성적의 순위를 넣는다.

- 배열의 첫번째 인덱스는 서류심사 1위인 지원자이므로 무조건 선발된다.

- 인덱스의 값이 올라간다는 것은, 서류심사의 순위가 낮아진다는 뜻이다.

- 배열을 순회하며 arr[i] 가 arr[i-1]보다 낮은번호라면( 순위가 더 높다면) i번째 지원자는 i-1번째 지원자보다 서류순위는 낮지만, 면접순위가 높다 -> 선발된다.

- 선발된다면, 기준이 되었던 면접순위는 arr[i] 가 되고, arr[i+1]은 arr[i]와 비교한다. (같은 순위는 없다는 점을 이용함)

- 이 문제는 O(N)도 시간초과가 뜨는것같다.. 그래서 readLine()이였던 느린 입출력을 fileIO()로 바꾸니 시간초과가 뜨지않았다.

import Foundation

final class FileIO {
    private var buffer:[UInt8]
    private var index: Int
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
        index = 0
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer.withUnsafeBufferPointer { $0[index] }
    }
    
    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true
        
        while now == 10
                || now == 32 { now = read() }
        if now == 45{ isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }
        
        return sum * (isPositive ? 1:-1)
    }
    
    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()
        
        while now == 10
                || now == 32 { now = read() }
        
        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }
        
        return str
    }
}

let file = FileIO()
var count = file.readInt()

for i in 0..<count {
    let num = file.readInt()
    var arr = Array(repeating: 0, count: num+1)
    var result = 1
    for j in 1...num {
        arr[file.readInt()] = file.readInt()
        
    }
    var compare = arr[1]
    
    for i in 2..<arr.count {
        if arr[i] < compare {
            result += 1
            compare = arr[i]
        }
    }
    print(result)
}

내가 푼 풀이

- 묶음의 숫자카드들을 저장해둔 배열 A 에서 가장 작은 두 묶음끼리 비교를 하면된다.

- 매번 비교를 할때 배열 A중에서 가장 작은 두개의 카드 묶음을 이용해야하므로 비교할 때 마다 배열이 정렬되어야한다.

- N개의 카드묶음이 있다면 비교횟수는 N-1번이 된다.

1. 배열을 오름차순으로 정렬한다.

2. 배열의 가장 앞자리 두개의 카드묶음을 비교한다.

3. 비교한값을 배열에 다시넣는다.

- 위 1-3 를 반복하면 결과를 얻을 수 있지만, N의 최댓값이 100,000으로 O(N^2)이상은 시간초과가 떴다.

- 최댓값과 최솟값을 빠르게 얻을 수 있는 우선순위 큐를 이용한다.

- 이 문제는 그리디보다 자료구조를 잘 알고 있는지가 더 중요한거같다.

- Swift는 우선순위 큐를 직접 구현해야한다.. 이번기회에 익혀두도록하자.

- 우선순위 큐의 시간복잡도는 O(logN)이다.

import Foundation

// Heap 구현
struct Heap<T: Comparable> {
    private var elements: [T] = []
    private let sortFunction: (T, T) -> Bool
    
    var isEmpty: Bool {
        return self.elements.count == 1
    }
    
    var peek: T? {
        if self.isEmpty { return nil }
        return self.elements[1]
    }
    
    var count: Int {
        return self.elements.count - 1
    }
    
    init(elements: [T] = [], sortFunction: @escaping (T, T) -> Bool) {
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements
        } else {
            self.elements = elements
        }
        self.sortFunction = sortFunction
        if elements.count > 1 {
            self.buildHeap()
        }
    }
    
    func leftChild(of index: Int) -> Int {
        return index * 2
    }
    func rightChild(of index: Int) -> Int {
        return index * 2 + 1
    }
    func parent(of index: Int) -> Int {
        return index / 2
    }
    
    mutating func swimUp(from index: Int) {
        var index = index
        while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
            self.elements.swapAt(index, self.parent(of: index))
            index = self.parent(of: index)
        }
    }
    
    mutating func insert(node: T) {
        if self.elements.isEmpty {
            self.elements.append(node)
            return
        }
        self.elements.append(node)
        self.swimUp(from: self.elements.endIndex - 1)
    }
    
    mutating func diveDown(from index: Int) {
        var higherPriority = index
        let leftIndex = self.leftChild(of: index)
        let rightIndex = self.rightChild(of: index)
        
        if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
            higherPriority = leftIndex
        }
        
        if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
            higherPriority = rightIndex
        }
        
        if higherPriority != index {
            self.elements.swapAt(higherPriority, index)
            self.diveDown(from: higherPriority)
        }
    }
    
    mutating func buildHeap() {
        for index in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: index)
        }
    }
    
    mutating func remove() -> T? {
        if self.elements.isEmpty { return nil }
        self.elements.swapAt(1, elements.endIndex - 1)
        let deleted = elements.removeLast()
        self.diveDown(from: 1)
        
        return deleted
    }
    
}


//PriorityQueue 구현
struct PriorityQueue<T: Comparable> {
    var heap: Heap<T>
    
    init(_ elements: [T] = [], _ sort: @escaping (T, T) -> Bool) {
        heap = Heap(elements: elements, sortFunction: sort)
    }
    
    var count: Int {
        return heap.count
    }
    
    var isEmpty: Bool {
        return heap.isEmpty
    }
    
    func top () -> T? {
        return heap.peek
    }
    
    mutating func clear () {
        while !heap.isEmpty {
            heap.remove()
        }
    }
    
    mutating func pop() -> T? {
        return heap.remove()
    }
    
    mutating func push(_ element: T) {
        heap.insert(node: element)
    }
}

let count = Int(String(readLine()!))!
var arr = [Int]()
var result = 0

for i in 0..<count {
    arr.append(Int(String(readLine()!))!)
}

var list = PriorityQueue(arr, { $0 < $1})
for i in 0..<count-1 {
    let num1 = list.pop()!
    let num2 = list.pop()!
    var sum = num1 + num2
    result += sum
    list.push(sum)
}

print(result)

자료구조 출처:

https://jeonyeohun.tistory.com/325

https://jeonyeohun.tistory.com/327

내가 푼 풀이

- 주어진 수의 자리를 바꿔서 30의 배수가 되는 최댓값을 구하면된다.

- 30의 배수면 마지막 자리는 무조건 0이된다.

- 주어진 수를 배열로 변환해서 0을 포함하고, 각자릿수를 더한 값이 3으로 나누어 떨어지면, 그 수는 30의배수가된다.

- 배열을 내림차순으로 바꾼후 위 조건을 따졌을때 30의배수면 그 수를 출력한다.

import Foundation


var arr = Array(readLine()!).map{ Int(String($0))! }
arr.sort{$0 > $1}
var sum = arr.reduce(0, +)

if sum % 3 == 0 && arr.contains(0){
    print(arr.map{ String($0)}.joined(separator: ""))
} else {
    print(-1)
}

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

내가 푼 풀이

- 도시에 도착해야 그 도시의 주유소를 이용할 수 있다.

- 무조건 첫번째 도시에서 주유해야 두번째 도시로 갈 수 있으므로 초기값은 첫번째 도시 가격 X 거리 이다.

- 최대한 적은 비용으로 충전하면서 이동하면 최솟값이 나온다.

- 이전 도시의 기름비용 최솟값을 저장해 두고, 도시에 도착할 때마다 값을 비교한다.

• 이전 도시보다 가격이 비싼경우 -> 이전 도시들의 기름비용 최솟값 X 그 다음 도시의 거리 를 더해준다.
• 이전 도시보다 가격이 싼경우 -> 기름비용 최솟값을 갱신해주고, 그 다음 도시의 거리를 곱한 값을 더해준다.

import Foundation

let count = Int(String(readLine()!))!
var distance = readLine()!.split(separator: " ").map{ Int(String($0))! }
var price = readLine()!.split(separator: " ").map{ Int(String($0))! }
var sum = price[0] * distance[0]
var idx = 0
var minPrice = price[0]

if count == 2 {
    print(sum)
} else {
    for i in 1..<distance.count {
        if minPrice > price[i] {
            minPrice = price[i]
        }
        sum = sum + (minPrice * distance[i])
    }
    print(sum)
}

내가 푼 풀이

- 그리디의 대표문제인 거스름돈과 비슷한 맥락으로 풀면된다.

- 초단위가 더 큰 버튼을 최대한 많이 눌러야 누르는 버튼횟수의 최솟값이 된다.

import Foundation

var time = Int(String(readLine()!))!
var arr = [300, 60, 10]
var result = Array(repeating: 0, count: 3)
for i in 0..<arr.count {
    if arr[i] <= time {
        var num = time / arr[i]
        result[i] = num
        time = time - (arr[i] * num)
    }
}
if time != 0 {
    print(-1)
} else {
    print(result.map{String($0)}.joined(separator: " "))
}

내가 푼 풀이

- 서로다른 N개의 자연수의 합 S 가 주어지는경우 N개가 최댓값이 되기위해선, 낮은 수들끼리의 합이 되어야한다.

- S가 주어진다면 1부터 1씩 증가시키며 S를 차감해준다.

- 증가된 수가 차감된 S보다 커질때의 수가 N의 최댓값이 된다.

S = 10 일때,

• idx = 1 , S = S - idx = 9
• idx = 2 , S = S - idx = 7
• idx = 3 , S = S - idx = 4
• idx = 4 , S = idx 가되므로 N의 최댓값은 4이다. [1,2,3,4]

idx = 4 라고 서로다른 N개의 자연수가 1,2,3,4 로 된 것은 아니다.

예로 S = 4 일때 

idx = 1, S = S - idx = 3

idx = 2, S = S - idx = 1

S < idx 가 되므로 N의 최댓값은 2 이지만, 서로다른 자연수는 [1,3] 이다.

이는 idx를 1씩 증감하고 S에서 빼주는것은

이전 idx가 서로다른 자연수로 들어가 있다고 생각하면된다.

예제 입력 200 의 결과는 19이다.

하지만 1에서 19까지 더한 수는 200이 아닌 190이다.

idx가 1부터 1씩 증가하면서 S를 뺄때, 

idx = 19일때 S에서 idx를 빼면 S = 10

10은 이미 idx가 19까지 올라오면서 거쳤던 자연수이다.

즉 S는 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,29] 로 N의 최댓값은 19개 , 19가 되는것이다.

따라서 S가 idx 보다 작아질때까지 실행 했을때 idx값이 N의 최댓값이 되는것이다.

import Foundation

var num = Int(String(readLine()!))!
var idx = 0

while num > idx {
    idx += 1
    num -= idx
}

print(idx)