알고리즘 지식 정리(11월 4일)[백준 클래스 2]

프린터 큐

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())
            cnt+=1
        } else {
            // 대상 문서일 경우 출력 및 while문 중단
            if queue[0].index == M {
                print(cnt)
                break
            }
            // 맨 앞의 문서 출력하여 제거 및 cnt에 1 추가\
            queue.removeFirst()
            cnt+=1
        }
    }
}

 

기존 코드

import Foundation
var cnt: Int
for i in 0 ..< Int(readLine()!)! {
    let inputArr = readLine()!.components(separatedBy:" ").map{Int($0)!}
    // enumerated 메서드만 사용
    var priorities = readLine()!.components(separatedBy:" ").map{Int($0)!}.enumerated()
    cnt = 0
    // for문을 통한 순회
    for j in 0 ..< inputArr[0] {
        // 첫번째 배열요소가 대상 문서와 동일하면, 재배치 횟수 출력
        if priorities[0].offset == inputArr[1] {
            print(cnt+1)
            break
        }
        // 나머지 문서들 중, 현재 문서보다 중요도가 높은 문서가 있다면, 재배치
        if inputArr[0]>1 {
            for element in priorities[1..<inputArr[0]]{
                if element > priorities[0].element{
                    let tmp = priorities.removeFirst()
                    priorities.append(tmp)
                    cnt+=1
                    break
                }
            }
        }
    }
}

 

현재 바라보고 있는 문서가 추적이 필요한 문서인지를 파악하기 위해선, 주어진 우선순위 값 외에 각 문서의 초기 index값이 필요했다. 따라서 enumerated() 함수를 사용해 한번의 순회로 인덱스와 값을 동시에 얻을 수 있도록 로직을 구성하였다. 하지만, enumerated() 함수가 최종적으로 반환하는 것은 배열이 아닌 EnumeratedSequence로 인덱스로 접근이 불가하다. 따라서 map 함수를 마지막에 재적용하여 튜플로 구성된 Array 형태로 변환해주었다.

 

또한 for 루프 대신 while 루프를 사용하여 큐처리를 진행하였는데, 프린터 큐 문제에서는 문서 배열의 크기가 출력을 진행하면서 동적으로 감소한다. 때문에, 고정된 횟수를 반복하는 for문이 아닌, queue가 빌 때까지 반복하는 while문이 불필요한 추가반복없이 목표를 달성할 수 있다 판단하였다.

 

---

스택 수열

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])
}

 

 

감사합니다.