오랜만에 하루에 두 문제를 풀어보는거 같다. 아침에 너무 진 빠지게 해가지고 좀 의욕이 안나다가 두번째 문제를 풀게 되었다. 골드4 수준에 문제이고 가르침이라는 제목의 이 문제는 설명 또한 상당히 신기했다.
지구온난화로 얼음이 녹게되서 학교가 무너지기 때문에 선생님이 마지막 수업으로 가르칠수있는 최대한 많은 단어의 숫자를 리턴해야한다. 솔직히 문제를 읽었을때는 의미가 많이 헷갈렸는데 가리칠수있는건 단어가 아니라 글자였다. 그리고 남극에서 알려줄 수 있는 단어는 "anta" 로 시작하고 "tica"로 끝난다고 한다.
N만큼의 단어와 K만큼의 단어를 가르칠 수 있을때 가장 많은 단어를 가르칠수있도록 리턴해야 하는데 문제를 읽으면 단순한 구현 문제보다는 backtracking 타입에 문제에 더 가까웠다. 다만 이 문제는 메모리에 제한이 있기 때문에 좀 더 효울적인 방법을 찾거나 풀이를 써야했다.
내 첫번째 풀이였는데 보기 좋게 시간초과로 틀려버렸다. 일단 몇가지 로직은 맞았는데, 모든 단어는 "anta" 와 "tica" 가 들어가기때문에 K만큼의 단어를 가르칠 수 있음에도 "a, n , t, i, c" 단어는 사용을 못한다. 그렇기때문에 만약 K가 5개 미만 일 경우에는 가르칠수있는 단어는 없기때문에 바로 0을 리턴하면된다.
그 외에 경우에는 dfs 탐색을 하게 됐었는데 내가 생각했던 방법은 단어 리스트를 읽으면서 탐색을 안한 단어가 남은 K (leftK) 보다 적게 되면 배울수있는 단어가 더 있다는 의미로 dfs 탐색을 진행했고 leftK보다 많은 단어가 남게되면 그대로 dfs 를 진행했다. 그 과정에서 visited 과정을 업데이트 하는 등, 전형적인 Yes or No 형식의 완전탐색을 하였고 시간으로만 따지면 (2^n) 은 된거같기에 그냥 틀린거같다.
로직까지는 맞았는데 좀 더 효울적으로 문제를 풀어야했기때문에 생각했던 방법은.. 이렇게 단어 하나하나 보면서 yes or no 의 초이스를 할 바에 알파벳을 모든 조합대로 맞춘다음에 wordList 를 읽어주면서 최대한의 카운트를 리턴하자 라는 생각이였다.
이렇게 쓰니깐 정말로 간단한 조합 방법이 나왔는데 여기까지 생각하는게 좀 더 어려웠던거 같다. 얍문님의 블로그를 보면서 아이디어를 구상했고 막상 구현하고 나니 정말로 쉬운 코드가 나와서 놀랐다. DP까지 써야하나 생각했었는데 되게 기분좋게 풀었던거 같다.
배운점:
1. 생각을 좀 더 간결하게 하면은 dfs 가 쉬워진다
2. 완전탐색할때 조심할것.
