[백준 12933] 오리(실버3) 🦢

문제

🔗 백준 12933 오리 (실버3) 문제 바로가기

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

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

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

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

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

입력

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

출력

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

시도 1

문제점

• numpy는 표준 라이브러리가 아니기 때문에 백준에서 쓸 수 없다. 런타임에러가 뜬다.
• qqqqqqqqqquack 를 입력했을 때 -1 가 나와야 하는데 그 처리를 안 해줬다.

import numpy as np

def find_index(duck, q):
  return [i for i in range(len(duck)) if duck[i]==q]

def howmanyducks(quack):
  duck_m = [find_index(quack, i) for i in "quack"]

  # 정상인지 확인
  tran_duck_m = np.transpose(duck_m).tolist()
  for i in range(len(tran_duck_m)):
    if tran_duck_m[i] != sorted(tran_duck_m[i]):
      return -1

  # 정상이면 몇 마린지 확인
  count_duck = [list(tran_duck_m[0])]
  for i in range(1, len(tran_duck_m)):
    if tran_duck_m[i][0] > min([i[-1] for i in count_duck]):
      count_duck[[i[-1] for i in count_duck].index(min([i[-1] for i in count_duck]))].extend(tran_duck_m[i])
    else:
      count_duck.append(tran_duck_m[i])

  return len(count_duck)

print(howmanyducks(input()))

transpose를 하기 위해 numpy가 아닌 map()과 zip(*list)를 이용해 아래처럼 tran_duck_m 를 바꿨다.

tran_duck_m = list(map(list, zip(*duck_m)))

근데 문제점은

[[0, 5], [1, 6], [2, 7], [3], [4]] 와 같이 빈칸이 존재하는(직사각행렬이 아닌) duck_m 을 transpose 하면, tran_duck_m = [[0, 1, 2, 3, 4]] 이렇게 나와버린다.
그래서 먼저 q, u, a, c, k 각 개수가 똑같지 않을 때 먼저 쳐내여야 한다. 아래처럼 코드를 수정했다.

# 정상인지 확인
  if len(set([len(i) for i in duck_m])) != 1:
    return -1
  tran_duck_m = list(map(list, zip(*duck_m)))
  for i in range(len(tran_duck_m)):
    if tran_duck_m[i] != sorted(tran_duck_m[i]):
      return -1

정답 코드

def find_index(duck, q):
  return [i for i in range(len(duck)) if duck[i]==q]

def howmanyducks(quack):
  duck_m = [find_index(quack, i) for i in "quack"]
  
  # 정상인지 확인
  if len(set([len(i) for i in duck_m])) != 1:
    return -1
  tran_duck_m = list(map(list, zip(*duck_m)))
  for i in range(len(tran_duck_m)):
    if tran_duck_m[i] != sorted(tran_duck_m[i]):
      return -1

  # 정상이면 몇 마린지 확인
  count_duck = [list(tran_duck_m[0])]
  for i in range(1, len(tran_duck_m)):
    if tran_duck_m[i][0] > min([i[-1] for i in count_duck]):
      count_duck[[i[-1] for i in count_duck].index(min([i[-1] for i in count_duck]))].extend(tran_duck_m[i])
    else:
      count_duck.append(tran_duck_m[i])

  return len(count_duck)

print(howmanyducks(input()))

풀이

처음부터 find_index 라는 함수를 쓰는데, 이는 q, u, a, c, k 각 문자가 몇 번째 인덱스에 나타나는지 보기 위해 사용한다.

예를들어 “quackqua” 를 입력받으면, duck_m = [[0, 5], [1, 6], [2, 7], [3], [4]] 가 된다. 즉 q는 0번, 5번 인덱스에 / u는 1번, 6번 인덱스 / a는 2번, 7번 인덱스 / u는 3번 인덱스 / a는 4번 인덱스에 등장한다는 의미를 가졌다.

정상적인 울음소리가 아니면 -1 을 리턴해야 한다. 일단 정상인지부터 확인하자.

1. 먼저 각 문자가 동일한 횟수로 등장했는지 확인한다.
   if len(set([len(i) for i in duck_m])) != 1 에서는 q, u, a, c, k 가 각각 등장한 횟수가 동일한지를 확인한다. 위 “quackqua” 예시에서 각 q는 2번, u는 1번만 등장한다. 이런 경우를 쳐낸다.

2. 만약 각 문자가 동일하게 등장한 경우, 문자의 순서가 올바른지 확인해야 한다. “quackqauckquack” 에서 중간에 u랑 a랑 순서가 바뀌어 있다. 이렇듯 quack 의 순서가 맞아야 한다는 뜻이다.

   각 문자가 동일하게 등장하면 duck_m 은 직사각형 매트릭스가 된다. 이때는 tranpose를 취할 수 있다. 이것의 의미하는 건, 위의 “quackqauckquack” 예시의 tran_duck_m 은 [[0, 1, 2, 3, 4], [5, 7, 6, 8, 9], [10, 11, 12, 13, 14]] 처럼 나온다. 각 요소들이 정렬되어 있어야 하는데 중간에 5, 7, 6 와 같이 정렬되지 않았다. quack 의 순서가 맞지 않다는 의미다.

이렇게 정상적이 아닌 경우를 쳐냈으면, 정상이 몇 마린지 확인해야 한다.

“quqacukqauackck” 이 예시의 답은 2 인데, 이 예시의 tran_duck_m은 아래와 같다.
[[0, 1, 3, 4, 6], [2, 5, 8, 11, 12], [7, 9, 10, 13, 14]]

첫번째 [0, 1, 3, 4, 6] 각 숫자는 q, u, a, c, k가 등장한 인덱스이다. 6번 인덱스에 k로 잘 끝났다.

두번째 [2, 5, 8, 11, 12] 에서 q는 2번 인덱스에서 시작한다. 그럼 첫 번째의 울음소리와 연결되지 않는다.(=첫번째 오리와 다른 오리다.)

세번째 [7, 9, 10, 13, 14] 는 첫 번째 오리 소리가 6번째 인덱스에서 끝났으니 이 오리와 연결될 수 있다. 즉, 첫 번째 오리는 [0, 1, 3, 4, 6, 7, 9, 10, 13, 14] 이렇게 울었다는 뜻이다.

이렇게 인덱스 순서가 이어질 수 있으면 같은 오리로 보는 것이다. 이를 구현하면 아래와 같다.

# 정상이면 몇 마린지 확인
count_duck = [list(tran_duck_m[0])] # 일단 첫 번째 울음소리만 담긴 리스트
for i in range(1, len(tran_duck_m)): # 다른 울음소리 하나씩 보면서 
  if tran_duck_m[i][0] > min([i[-1] for i in count_duck]): # count_duck 울음소리 중에 연결할 수 있는 게 있으면 
    count_duck[[i[-1] for i in count_duck].index(min([i[-1] for i in count_duck]))].extend(tran_duck_m[i]) # 연결하고
  else: # 연결 못 하면 
    count_duck.append(tran_duck_m[i]) #count_duck에 새로운 오리의 울음소리로 추가한다.

따라서 count_duck의 길이를 리턴하면 된다.