백준 12933 오리

오리떼의 합창

 

한마리 오리의 울음 소리는 quack의 순서로 진행된다.

 

정확하게 녹음된 오리의 소리라면 현재 처리해야 하는 한 글자는 이전의 글자 다음에 위치하면 되고
만약에 현재까지의 오리들의 마지막 울음소리 중에 이전의 글자를 찾지 못하면 새로운 오리가 등장한 것이다.
( 소리 q를 처리할 경우라면 q는 k 다음에 위치해야 하고 

  현재까지 울음소리의 마지막을 k로 낸 오리가 없다면 새로운 오리인 것이다.)

 

모든 녹음 처리가 끝났을 때 quack을 모두 없애고 남은 글자가 있다면 잘못 녹음된 것이다.

 

sound='quack'  # 오리의 소리
d=dict(zip(sound,'kquac')) # 현재 글자의 이전글자 맵핑 {q:k, u:q, a:u, c:a, k:c}
ducks=[]  # 오리의 리스트

for c in input():  # 소리를 하나씩 처리
 new=1 # 새로운 오리 생성을 위한 플래그
 for e in ducks: # 현재 존재하는 오리들을 하나씩 탐색
  # 현재까지 마지막 울음소리가 지금글자 이전글자와 일치한다면 그 소리 다음에 추가하고 새로운 오리 생성은 필요 없음.
  if e[-1]==d[c]:e+=[c];new=0;break 
 if new: ducks+=[[c]] # 일치하는 게 없다면 우렁찬 첫 소리와 함께 새로운 오리 생성

wrong=0 # 잘못됨 flag
for e in ducks: # 오리들을 순환하면서
 temp=''.join(e).replace(sound,'')  # 정상적인 오리소리 제거
 if temp: wrong=1  # 남은 소리가 있다면 잘못됨 flag를 true로 

print(-1 if wrong else len(ducks))  # 잘못되었으면 -1, 정상이면 오리의 수 출력

 

https://www.acmicpc.net/problem/12933