12933번: 오리

12933번: 오리

오리

 

문제

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.

영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.

갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.

녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다.

출력

영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.

예제 입력 1 

quqacukqauackck

예제 출력 1 

2

---

풀이

 

문제를 제대로 이해해보자.

 

1. 오리의 울음소리는 "quack"이다.
2. 오리는 울음 소리를 한 번 또는 여러 번 낼 수 있다.
3. 오리의 울음소리는 연속될 필요 없다.
4. 녹음한 소리가 주어지고, 방에 있을 수 있는 오리의 최소 수를 구해라.

 

내가 처음에 이 문제를 풀기 위해서 생각한 방법은, 

 

quack이 주어져 있으니 배열에 quack을 저장하고 녹음한 소리를 반복문을 돌려 quack을 가진 오리의 수를 cnt로 증가시키면 되지 않을 까 생각했다. 하지만 문제점이 있다.

 

예제를 생각해보자.

 

 

duck[][]을 이차원 배열로 만들어 녹음한 소리를 탐색하며 개수를 증가시킨다. 마지막으로 모든 울음소리의 개수가 같다면 녹음소리가 올바르고, 개수에 차이가 있다면 올바르지 않은 것으로 판단하려 했다.

 

하지만 여기서 문제점은 다음과 같다.

 

• 오리의 최소개수를 구해야 한다. 
• quack이 연속되진 않아도 순서대로 울음소리가 이뤄져야한다.

 

해당 문제에 대해 해결하지 못해 다른 방법을 떠올렸다.

 

---

설계

 

중요한 점은 오리의 최소 수와 quack 울음소리의 순서이다.

 

다음과 같은 방법으로 설계했다.

 

1. 일단 일차원 배열 duck[]에 quack을 저장한다.
2. 녹음한 소리를 끝까지 다 탐색하며 quack 순서에 맞는 소리를 방문했다고 "O"로 바꿔준다. 
3. 녹음한 소리가 모두 "O"로 바뀔때까지 계속 탐색을 하며 최소 오리수를 찾는다.

 

즉, 녹음한 소리를 끝까지 다 탐색해 "O"로 바꿔주는 행위 하나가 오리 수 하나 증가하는 것과 같다.

 

 

예제 1로 확인하면 다음과 같다.

 

 

---

구현

 

위에서 설계한 대로 코드를 구현해보자.

 

1. 녹음한 소리 탐색

 

• 반복문이 한번 돌아갈 때마다 오리의 수가 증가하니 cnt값을 증가한다.
• 녹음한 소리가 "O"이라면 이미 방문한 곳이니 탐색하지 않는다.
• remain 값이 0이라면 => 녹음한 소리가 올바르므로, 오리 최소 수 출력
• remain 값이 0이 아니라면 => 녹음한 소리가 올바르지않아, -1 출력

 

=> check 값을 찾는데 힘들었다... 반복문을 한번 돌렸을 때 "quack"까지 다 탐색을 하지 못했다면 remain 값도 감소하지 않았을 테니, 

반복문 들어가기 전의 remain 값과 나온 후의 remain 값을 확인한다.

 

값이 같다면 올바르지 않은 녹음 소리로 break하고 -1을 출력한다.

 

 

2. 녹음한 소리 방문 처리

 

• index는 녹음소리의 위치, duck_index는 울음소리 "quack"의 위치이다.
• 녹음 소리와 duck의 울음소리가 일치한다면 "O"로 바꿔준다.
• duck_index = 5라면, "quack"까지 완벽하게 탐색한 것이니 duck_index 초기화하고 remain 값을 5감소 시켜준다.

 

 

---

전체코드

var arr : [String] = Array(readLine()!).map {String($0)}
let duck : [String] = ["q", "u", "a", "c", "k"]
var cnt = 0
var duck_index = 0
var remain = arr.count

while remain != 0 {
    let check = remain
    
    cnt += 1
    duck_index = 0
    for i in 0..<arr.count{
        if arr[i] != "O"{
            search(i)
        }
    }
    
    if check == remain {
        break
    }
}

func search(_ index: Int){
        
    
    if arr[index] == duck[duck_index]{
        arr[index] = "O"
        duck_index += 1
    }
    
    if duck_index == 5{
        duck_index = 0
        remain -= 5
    }
    
}

print( remain==0 ? cnt : -1)