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

벌집

import Foundation
let input = Int(readLine()!)!
var stdNum = 8 // 다음단계로 넘어가는 기준숫자
var offset = 12 // 기준숫자 변동폭
var ans = 2
// 1의 경우, 변동폭 예외적으로 4 차이남 따라서 예외 케이스
if input == 1 { print("1") } else {
    while true {
        if input < stdNum { 
            print(String(ans))
            break
        }
        stdNum+=offset
        offset+=6
        ans+=1
    }
}

필요로 하는 블록 수가 변경되는 기준숫자값이 단계별로 일정하게 6씩 증가하는 것을 알 수 있었다. 다만 1에서 다음단계로 넘어갈 경우, 4씩 증가하였기에 이는 예외로 처리하여 고정적으로 1을 출력하게 해주었다.

 

블랙잭

import Foundation
let arr = readLine()!.components(separatedBy:" ").map{Int($0)!}
let cards = readLine()!.components(separatedBy:" ").map{Int($0)!}.sorted()
var ans:[Int] = []
// 모든 카드 숫자를 중복없이 3개씩 더해보고, 
// 500보다 작으면 ans에 추가 / 순회 도중 500 넘기면 그 이후도 넘기기에 순회 중단
for i in 0..<cards.count {
    for j in i+1..<cards.count {
        for k in j+1..<cards.count {
            if cards[i]+cards[j]+cards[k]>arr[1]{
                break
            } else {
                ans.append(cards[i]+cards[j]+cards[k])
            }
        }
    }
}
print(String(ans.max()!))

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, m) = (input[0], input[1])
let arr = readLine()!.split(separator: " ").map{ Int($0)! }
var maxResult = 0
for i in 0..<arr.count {
    for j in i+1..<arr.count {
        for k in j+1..<arr.count {
            let sum = arr[i] + arr[j] + arr[k]
            if sum <= m && maxResult < sum {
                maxResult = sum
            }
        }
    }
}
print(maxResult)

3중 for문을 이용해서, 모든 카드숫자들에 대해서 3개의 합을 구해보고, Arr에 담는 로직을 구성하였다. 이때 arr를 올림차순으로 정렬하였는데, 이로 인해 for문 순회중 처음으로 3개의 합이 500을 넘기면, 그 이후의 순회에도 500을 넘기게 되기 때문에, 반복을 중단하도록 하여 불필요한 연산을 최소화 했다. 다른 사람의 문제풀이를 보니, 배열을 따로 생성하는 대신, maxResult 변수를 선언한 후에, maxResult 변수값만 갱신하는 접근방식을 취하였는데, 소요시간이 대폭 감소한 것을 볼 수 있었다. 배열 생성은 안할 수 있으면 하지 말아야지...

 

덱

import Foundation
let N = Int(readLine()!)!
var arr:[String] = []
for i in (0..<N){
    let input = readLine()!.components(separatedBy:" ")
    if input.contains("push_front"){
        arr.insert(input[1],at:0)
    } else if input.contains("push_back"){
        arr.append(input[1])
    } else if input.contains("front"){
        print(arr.isEmpty ? "-1" : arr[0])
    } else if input.contains("back"){
        print(arr.isEmpty ? "-1" : arr[arr.count-1])
    } else if input.contains("pop_front"){
        if arr.isEmpty {
            print("-1")
        } else {
            print(arr[0])
            arr.removeFirst()
        }
    } else if input.contains("pop_back") {
        if arr.isEmpty {
            print("-1")
        } else {
            print(arr[arr.count-1])
            arr.removeLast()
        }
    } else if input.contains("size") {
        print(String(arr.count))
    } else {
        print(arr.isEmpty ? "1" : "0")
    }
}