Jenikeju

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

내가 푼 풀이

- 집의 좌표들을 오름차순으로 정렬하여 첫번째 집부터 차례대로 공유기를 설치하여 C만큼 설치했을때 공유기 거리의 최댓값으로 구해보자

- 이분탐색을 이용하였는데, 집의 좌표 사이의 거리들을 탐색하였다.

- 거리의 최소값은 집과 공유기의 갯수가 같으면 집집마다 설치하면 되므로 0이 되고, 거리의 최대값은 첫번째 집과 마지막번째 집사이의 거리가 된다.

- 이 거리를 공유기 설치 거리로 생각하고, 중간값부터 공유기를 설치해보고, 설치 개수가 C보다 같거나 많이 설치가 됬다면 거리를 좀 더 늘리고, C보다 적게 설치됬다면 설치거리를 줄여서 다시 설치하는 방향으로 한다.

import Foundation
// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0]
let C = input[1]
var arr = [Int]()
for i in 0..<N {
    arr.append(Int(readLine()!)!)
}
// 집좌표 오름차순 정렬
arr.sort(by: <)
// 집과 집사이의 공유기 설치거리 최솟값과 최댓값
// 최솟값은 집집마다 공유기 설치한다면 0, 최댓값은 정렬된 집좌표에서 첫번째집과 마지막번째 집사이의 거리가된다.
var startIndex = 0
var endIndex = arr[arr.endIndex - 1] - 0
var result = 0  // 결과를 저장할 변수

// 이분탐색
while startIndex <= endIndex {
    var count = 1
    var house = arr[0]
    let midIndex = (endIndex + startIndex) / 2
    // 첫번째 집부터 공유기를 설치해보고, 다음집까지 설치거리가 닿는다면 패스
    // 닿지 않으면 공유기를 새로 설치해야하므로 count ++ 하고, 기준이 되는 집 갱신한다.
    for i in 0..<N {
        let nextHouse = arr[i]
        if midIndex <= nextHouse - house {
            count += 1
            house = nextHouse
        }
    }
    // 공유기가 더 많이 설치가 됬다면, 설치거리가 짧아서 많은 집들에 설치가된것으로, 설치거리를 늘린다.
    // 공유기가 더 적게 설치가 됬다면, 설치거리가 길어서 한 집이 많은 집을 커버했다. 설치거리를 줄인다.
    // 이렇게 반복하면 설치거리가 최대가 될때까지 반복이 된다.
    if count >= C {
        result = midIndex
        startIndex = midIndex + 1
    } else {
        endIndex = midIndex - 1
    }
}

print(result)

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

내가 푼 풀이

- 주어진 두 배열을 완전탐색한다면 O(N^2) 걸리므로 시간초과가 뜰것이다.

- 정렬된 배열 기준으로 더 빠른 탐색방법인 이분탐색방법을 이용했다.

func binarySearch<T: Comparable>(array: [T], start: Int, end: Int, target: T) -> Int? {
    var arr = array
    var startIndex = start
    var endIndex = end
    var midIndex = (end + start) / 2
    
    if startIndex > endIndex { return nil}
    if arr[midIndex] == target {
        return midIndex
    } else if arr[midIndex] > target {
        endIndex = midIndex - 1
        return binarySearch(array: arr, start: startIndex, end: endIndex, target: target)
    } else {
        startIndex = midIndex + 1
        return binarySearch(array: arr, start: startIndex, end: endIndex, target: target)
    }
}

let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
let M = Int(readLine()!)!
var findNums = readLine()!.split(separator: " ").map{Int(String($0))!}
for i in 0..<M {
    let num = findNums[i]
    
    if let finded = binarySearch(array: arr, start: 0, end: arr.endIndex - 1, target: num) {
        print(1)
    } else {
        print(0)
    }
}

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

내가 푼 풀이

- 최소힙 기반으로 정렬기준을 좀 바꾸면 된다.

- 절댓값이 같다면, 값이 작은게 우선인 힙을 만들면 된다.

import Foundation

struct Heap<T: Comparable> {
    var elements: [T] = []
    var sortFunction: (T,T) -> Bool
    var isEmpty: Bool {
        return elements.isEmpty || elements.count == 1
    }
    var peek: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements[1]
        }
    }
    var count: Int {
        if elements.isEmpty {
            return 0
        } else {
            return 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 idx = index
        while idx != 1 && self.sortFunction(self.elements[idx], self.elements[parent(of: idx)]) {
            self.elements.swapAt(idx, self.parent(of: idx))
            idx = self.parent(of: idx)
        }
    }
    mutating func insert(element: T) {
        if self.elements.isEmpty {
            self.elements.append(element)
            self.elements.append(element)
            return
        }
        self.elements.append(element)
        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(index, higherPriority)
            self.diveDown(from: higherPriority)
        }
    }
    
    mutating func buildHeap() {
        for i in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: i)
        }
    }
    mutating func remove() -> T? {
        if self.isEmpty {
            return nil
        }
        self.elements.swapAt(1, self.elements.endIndex - 1)
        var returnValue = self.elements.removeLast()
        self.diveDown(from: 1)
        
        return returnValue
    }
}

let N = Int(readLine()!)!
var heap = Heap(elements: [Int](),sortFunction: { if abs($0) == abs($1) {
    return $0 < $1
} else {
    return abs($0) < abs($1)
}})

for i in 0..<N {
    let num = Int(readLine()!)!
    if num == 0 {
        if let poped = heap.remove() {
            print(poped)
        } else {
            print(0)
        }
    } else {
        heap.insert(element: num)
    }
}

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

문제

정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

1. 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
2. 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
3. 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
4. 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
5. 5: 덱에 들어있는 정수의 개수를 출력한다.
6. 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
7. 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
8. 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

내가 푼 풀이

- 덱을 구현해서 해당 명령어를 실행하면 된다.

- 명령수가 많아서 입출력코드를 이용했다

import Foundation

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer[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 now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시

        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시

        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

// 덱
struct Deque<T> {
    var enqueue: [T]
    var dequeue: [T] = []

    init(enqueue: [T]) {
        self.enqueue = enqueue
    }
    var count: Int {
        return enqueue.count + dequeue.count
    }
    var isEmpty: Bool {
        return enqueue.isEmpty && dequeue.isEmpty
    }

    mutating func first() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.last
    }
    mutating func last() -> T? {
        if enqueue.isEmpty {
            if dequeue.isEmpty {
                return nil
            } else {
                return dequeue[0]
            }
        } else {
            return enqueue.last
        }
    }
    mutating func pushFront(_ element: T) {
        dequeue.append(element)
    }
    mutating func pushRear(_ element: T) {
        enqueue.append(element)
    }
    mutating func popFront() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    mutating func popRear() -> T? {
        if enqueue.isEmpty {
            enqueue = dequeue.reversed()
            dequeue.removeAll()
        }
        return enqueue.popLast()
    }
}
let fIO = FileIO()
let N = fIO.readInt()
var dq = Deque(enqueue: [Int]())

for i in 0..<N {
    let op = fIO.readInt()
    
    switch op {
    case 1:
        let element = fIO.readInt()
        dq.pushFront(element)
    case 2:
        let element = fIO.readInt()
        dq.pushRear(element)
    case 3:
        if let popFir = dq.popFront() {
            print(popFir)
        } else {
            print(-1)
        }
    case 4:
        if let popLas = dq.popRear() {
            print(popLas)
        } else {
            print(-1)
        }
    case 5:
        print(dq.count)
    case 6:
        print(dq.isEmpty ? 1 : 0)
    case 7:
        if let fir = dq.first() {
            print(fir)
        } else {
            print(-1)
        }
    case 8:
        if let las = dq.last() {
            print(las)
        } else {
            print(-1)
        }
    default: continue
    }
}