알고리즘 지식 정리(11월 6일)[백준 실버 4]

프린터 큐

import Foundation

for i in 0 ..< Int(readLine()!)! {
    let inputArr = readLine()!.components(separatedBy:" ").map{Int($0)!} // [문서 개수, 대상문서 위치]
    let N = inputArr[0]
    let M = inputArr[1]
    
    var queue = readLine()!.components(separatedBy:" ")
    .map{Int($0)!}
    .enumerated()
    .map{ (index:$0.offset,priority:$0.element) }
    
    var cnt = 0
    while !queue.isEmpty {
        // 중요도 더 높은 문서가 나머지 중 존재할 경우, 재배치
        if queue.contains(where:{$0.priority>queue[0].priority}) {
            queue.append(queue.removeFirst())
        } else {
            // 대상 문서일 경우 출력 및 while문 중단
            if queue[0].index == M {
                print(cnt+1)
                break
            }
            // 맨 앞의 문서 출력하여 제거 및 cnt에 1 추가
            queue.removeFirst()
            cnt+=1
        }
    }
}

대상 문서가 최종적으로 몇번째에 출력되는지 확인하기 위해선, 모든 문서에 대한 고유의 식별값이 먼저 필요했습니다. 이를 위해 enumerated()함수를 통해 기존 배열에서 인덱스값을 같이 추가한 후, isEmpty, subscripts, append와 같은 메서드를 활용하기 위해서 map 고차함수를 통해 다시 튜플 형태의 Array로 변경해주었습니다. 문서를 Queue의 가장 뒤에 재배치한다는 것은 즉, 맨 앞의 요소를 제거한 후에 뒤에 추가하는 것을 의미하는데, removeFirst()함수가 결국 첫번째 요소를 반환하기 때문에, append(value.removeFirst())로 위 로직을 구현할 수 있게 됩니다.

 

스택 수열

import Foundation
let N = Int(readLine()!)!
var num = 0
var arr:[Int] = []
var ans:[String] = []
for _ in 0..<N {
    // 제시된 숫자값
    let input = Int(readLine()!)!
    while input > num { // 숫자값이 들어갈때까지, 오름차순으로 요소 추가
        num+=1
        ans.append("+")
        arr.append(num)
    }
    if (arr.last == input){
        arr.popLast()
        ans.append("-")
    } else {
        ans = ["NO"]
        break
    }
}
for i in 0..<ans.count {
    print(ans[i])
}

LIFO 특성을 지닌 스택의 속성으로 인해, 결국 나타내고자 하는 정수가 현재 스택에 있는 수보다 클 경우에는, 정수와 동일한 크기의 숫자가 들어올때까지 스택에 오름차순으로 숫자들을 추가해야하며 숫자를 뽑을 때에도 숫자를 추가했던 역순으로 처리가 되어야합니다. 따라서 이러한 순서에 맞춰 append와 popLast를 번갈아 진행하다가, 요소의 마지막에 출력하고자 하는 수가 나오지 않을 경우, 표현이 불가능한 수열로 판단하고 break하게 코드를 구성하게 되었습니다.

 

쇠막대기

import Foundation
var num = 0
var ans = 0
var prev = ""
for item in readLine()!.map{String($0)} {
    if item == "(" {
        num+=1
    } else {
        num-=1
        // 레이저
        if prev=="(" {
            ans += num
        } else { // 끝맺음에 대한 처리
            ans += 1
        }
    }
    prev=item
}
print(ans)

쇠막대기의 연산 처리방식도 스택에 쌓인 요소의 개수를 세는것과 유사했습니다. "("가 나올때마다 쇠막대기가 추가되면서, 추후 레이저가 나올때 쪼개지게될 막대기의 수가 누적 되게 하였고, 레이저가 나올때 누적하였던 막대기 수를 최종 ans에 더하는 연산을 입력 string의 개수만큼 반복하였습니다. 이때 단순 스택 연산과 달리 가져갔던 것은 쇠막대기의 끝맺음 처리였습니다. 레이저로 절단되어 새로 쪼개지지 않더라도, 쇠막대기의 끝부분 또한 별개의 막대기로 분류되어야 하기 때문에, ans에 1을 추가해주어 마무리하였습니다.

 

Hashing

let alpha = "abcdefghijklmnopqrstuvwxyz".map{String($0)}
let N = Int(readLine()!)!
let input = readLine()!.map{String($0)}
var ans: UInt64 = 0
let M: UInt64 = 1234567891

var power: UInt64 = 1
for i in 0..<N {
    guard let id = alpha.firstIndex(where: {$0 == input[i]}) else { break }
    ans = (ans + ((UInt64(id + 1) * power) % M)) % M
    power = (power * 31) % M
}
print(ans)

이 문제는 거듭제곱을 다루기 때문에 수의 값이 매우 커지는 오버플로우 문제를 처리해줘야한다. 이에 대응하고자 아래와 같은 기법을 사용해주었습니다.

- UInt64 자료형 사용

UInt는 Unsigned Int로 모든 64비트를 숫자 저장에만 사용하기 때문에, Int보다 더 큰범위의 양수를 저장할 수 있게되며, 말그대로 0부터 2의 64제곱 -1인 18,446,744,073,709,551,615까지 저장이 가능합니다. 대신 음수는 저장이 불가능하다는 단점이 있습니다.

 

- 곱셈의 모듈러 연산

(A * B) % M = ((A % M) * (B % M)) % M

중간 계산 과정에서도 M으로 나머지 연산을 수행해 오버플로우를 방지하고자 했습니다.

 

감사합니다.