[백준] 이모티콘 (14226번) Swift

문제 내용

이모티콘 S개를 만든다.처음에는 화면에 이모티콘 1개 존재한다.다음 3가지 연산으로 이모티콘 S 개를 만든다.

• 화면에 있는 이모티콘을 모두 복사하여 저장
• 복사되어있는 이모티콘을 붙여넣기 함
• 이모티콘 1개 삭제

모든 연산은 1초가 걸린다.

---

전체 코드

// 1. 목표 이모티콘 개수 받기
let s = Int(readLine()!)!

// 2. queue 생성
// count = 현재 화면의 이모티콘 개수, time = 시간, copyCount = 현재 복사되어 있는 이모티콘 수
var queue: [(count: Int, time: Int, copyCount: Int)] = []

// 3. queue 를 가리킬 queueIndex 생성
var queueIndex = 0

// 4. 결과 저장
var result = 0

// 5. 해당 값을 방문했는지 확인하기 위한 배열
var visited: [[Int]] = Array(repeating: [], count: s * 2 + 1)

// 6. 초기 값 설정
// 초기에 화면에 이모티콘 1개가 존재하고, 시간은 0초, 그리고 복사된 것은 없기 때문에 0으로 함
queue.append((1, 0, 0))

while queueIndex < queue.count {
    // 7. queue 에 있는 값을 뽑아옴
    let now = queue[queueIndex]
    queueIndex += 1
    
    // 8. 만약 count 가 원하는 결과면 종료
    if now.count == s {
        result = now.time
        break
    }
    
    // 9. 그렇지 않으면 다음 이모티콘 만드는 함수 실행
    makeEmoji(now.count, now.time, now.copyCount)
}

func makeEmoji(_ count: Int, _ time: Int, _ copyCount: Int) {
    // 10. count 가 visted.count 보다 작을 때 진행하고
    // 현재 값이 기존에 방문했던 값이 아니면 방문
    if count < visited.count && !visited[count].contains(copyCount) {
        // 11. 먼저 visted 에 현재 값을 저장함
        visited[count].append(copyCount)
        
        // 12. 화면에 있는 이모티콘 수를 복사하는 연산
        queue.append((count, time + 1, count))
        
        // 13. 복사되어 있는 이모티콘을 화면에 붙여넣는 연산
        queue.append((count + copyCount, time + 1, copyCount))
        
        // 14. 화면에 있는 이모티콘 하나를 삭제하는 연산
        if count - 1 > 0 {
            queue.append((count - 1, time + 1, copyCount))
        }
    }
}

print(result)

 

S = 4 라고 가정하면,

처음에 queue 에 (1, 0, 0) 을 넣는다.

7 번에서 queue 에 있는 값을 꺼내면

(1, 0, 0)

이모티콘: 🍠, 시간: 0초, 복사: X 이다.

 

makeEmoji 함수가 호출이 되고

11 번 이 호출 되어

visited[1] = [0] 이 되고

queue 에

12 번 (복사) - (1, 1, 1),

13 번 (붙여넣기) - (1, 1, 0)

이 추가가 된다.

 

다시 while 문에서

(1, 1, 1)

이모티콘: 🍠, 시간: 1초, 복사: 🍠

이 선택이 된다.

 

 

makeEmoji 함수가 호출되어

queue 에 (1, 2, 1), (2, 2, 1) 이 추가가 된다.

 

이런 식으로 반복하면

마지막에

(4, 4, 2)

이모티콘: 🍠🍠🍠🍠, 시간: 1초, 복사: 🍠🍠

가 호출이 되어 화면에 4개의 이모티콘이 생성이 되어서 종료된다.

---

결론

visited 배열에 대해 contains 하는 것에서 시간 초과가 날 줄 알았는데

S 크기가 최대 1,000 이라 괜찮았다.

 

출처 : 백준 이모티콘
https://www.acmicpc.net/problem/14226

14226번: 이모티콘