[백준 브루토포스/백트래킹/비트마스킹] 가르침

문제

 

첫 풀이와 실패

우선 가장 먼저 생각나는 방법으로 코딩을 하였다. 

n, p = map(int, input().split())

words = [input() for _ in range(n)]
#words = []

#for i in range(len(arr)):
#  words.append(arr[i][4:len(arr[i]) - 4])

obj = {}
for word in words:
  for letter in word:
    obj[letter] = 1

for i in range(len(words)):
  for j in range(len(words[i])):
    for k in range(i + 1, len(words)):
      if i == k:
        continue

      if words[i][j] in list(words[k]):
        obj[words[i][j]] += 1

letters_tuple = []

for o in obj:
  letters_tuple.append((o, obj[o]))

letters_tuple.sort(key=lambda x: -x[1])
letters = []

for l in letters_tuple[:p]:
  letters.append(l[0])

cnt = 0
for word in words:
  flag = True
  for i in range(len(word)):
    if word[i] not in letters:
      flag = False
      break

  if flag:
    cnt += 1

print(cnt)

#https://www.acmicpc.net/problem/1062

 

코테 문제를 많이 풀어본 티가 나지 않는 코드이다. 가장 먼저 생각나는 아이디어로 단순하게 코딩을 했다. 

 

백준 사이트의 정책이지만 정답이 틀렸을 때 어떤 테스트 케이스에서 틀렸는지 볼 수 없는게 아쉽다.  틀린 부분을 확인하고 고치는 과정도 참 값져 보이는데.

 

1%에서 틀려버렸지만 해당 페이지에 나와있는 테스트케이스는 다 통과했다.

 

난 단어가 구성하는 알파벳들의 빈도수 대로 정렬하고 k개 만큼 잘라서 각각의 단어들에 포함이 되는지 검사하는 방법을 생각했다. 이 아이디어를 잘 못 구현한건지 아니면 이 아이디어가 캐치하지 못하는 반례가 있는지 궁금했다.

 

약 1분 정도 고민후 반례를 찾았다 이 아이디어는 필수로 알고 있어야 하는 글자인 a, c, i, n, t의 우선순위를 낮출 수 있다.

 

이렇게 풀면서도 어디서 백트래킹을 하라는 거지? 라는 의문이 생겼었다.

 

https://oh2279.tistory.com/158

 

이 분의 정답을 참고했고 따라서 구현해보았다.