[백준] 14226번 - 이모티콘 [Swift]

문제 링크

14226번: 이모티콘

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여 넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여 넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여 넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

문제 풀이

이 문제는 BFS를 활용하면 풀 수 있는 문제였습니다.

하지만 문제에 재밌는 조건들이 있어서 몇 가지를 생각해줘야 했습니다.

일단 문제의 조건을 보면 아래와 같습니다.

 

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여 넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

즉 한 번의 단계에서 클립보드에 현재 이모티콘을 복사하거나, 클립보드에 존재하는 이모티콘을 붙여넣기 하거나, 화면의 이모티콘을 하나 지우는 것을 할 수 있습니다.

 

가장 중요한 것은 이미 만들어본 이모티콘이라도 당시 클립보드에 저장된 이모티콘의 개수가 다르다면 새로운 경우라는 점을 생각해줘야 한다는 점입니다!

 

예를 들어보면..

 

화면의 이모티콘 : 🐧🐧 

클립보드에 저장된 이모티콘 : 🐧🐧🐧

 

화면의 이모티콘 : 🐧🐧 

클립보드에 저장된 이모티콘 : 🐧🐧🐧🐧🐧🐧

 

간단하게 위와 같은 경우가 있다면 둘은 다른 경우라는 뜻입니다!

이를 처리하기 위해 저는 alreadyMake라는 배열에 해당 이모티콘을 만들 때 클립보드의 상태를 저장해줬습니다.

 

이러한 점에 유의하여 해결하면 아래와 같은 순서를 반복해주시면 됩니다.

 

1. 현재 화면의 이모티콘 개수가 S개인지 확인한다
2. S 개라면 현재의 시간을 반환
3. S개가 아니라면
   
   1. 화면의 이모티콘을 하나 지웠을 때 현재 클립보드에 저장된 수와 같은 경우가 과거에 존재했는지 확인 후 없었다면 추가
   2. 화면의 이모티콘에 현재 클립보드에 저장된 것을 복사 후, 해당 개수의 경우에 현재 클립보드에 저장된 수와 같은 경우가 과거에 존재했는지 확인 후 없었다면 추가
   3. 화면에 있는 이모티콘을 클립보드에 복사
4. 시간에 1초를 더함

소스 코드

import Foundation

class Queue<T>{
    var enqueue: [T]
    var dequeue: [T] = []
    
    var isEmpty: Bool {
        return enqueue.isEmpty && dequeue.isEmpty
    }
    var count: Int {
        return enqueue.count + dequeue.count
    }
    
    init(_ queue:[T]) {
        self.enqueue = queue
    }
    
    func push(_ n: T) {
        enqueue.append(n)
    }
    
    func pop() -> T? {
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    func removeAll() {
        enqueue.removeAll()
        dequeue.removeAll()
    }
}

func solution() -> Int {
    let s = Int(String(readLine()!))!
    
    var alreadyMake = [[Int]](repeating: [], count: 2001)
    alreadyMake[1].append(0)
    
    // 현재 이모티콘 개수, 클립보드에 복사된 이모티콘 개수
    let queue = Queue([[1, 0]])
    var time: Int = 0
    while !queue.isEmpty {
        
        for _ in 0..<queue.count {
            let now = queue.pop()!
            let nowCount = now[0]
            let nowClipBoard = now[1]
            
            if nowCount == s {
                return time
            }
            
            if nowCount - 1 >= 0 && !alreadyMake[nowCount - 1].contains(nowClipBoard) {
                alreadyMake[nowCount - 1].append(nowClipBoard)
                queue.push([nowCount - 1, nowClipBoard])
            }
            if nowCount + nowClipBoard <= 2000 && !alreadyMake[nowCount + nowClipBoard].contains(nowClipBoard) {
                alreadyMake[nowCount + nowClipBoard].append(nowClipBoard)
                queue.push([nowCount + nowClipBoard, nowClipBoard])
            }
            // 현재 이모티콘을 클립보드에 복사
            queue.push([nowCount, nowCount])
        }
        time += 1
    }
    return time
}
print(solution())