https://programmers.co.kr/learn/courses/30/lessons/12983
-
flow
예전에 솔루션이 한번에 생각이 안 나서 넘어갔었는데 이번에 다시 보니 금방 dp 쪽으로 idea가 생각이 났다. dp[i] 의 값을 t 를 앞에서부터 i+1까지 자른 스트링이라고 생각할 때, strs 에서 가가장 적은 수의 집합을 이용해서 만들 수 있는 경우라고 하자. 예를 들어, t = 'banana' 이고, strs = [ba,na,n,a] 일 때, dp[0] = 0 (t[:1] = 'b' 인데 b is not in strs). dp[1] = 1 (t[:2] = 'ba' is in strs) 이런 식으로 최종 dp[5] = 3 이 될 것이다. (ba na n a 처럼 4도 가능하지만 ba na na 3이 최소 경우).
디테일한 구현은 t[:i+1] 이 strs에 존재하면 무조건 dp[i] = 1, 다른 경우에 t[j+1:i+1] 이 strs에 존재할 때, dp[j] != 0 인 경우 dp[i] = min(dp[i], dp[j]+1) (dp[i]!=0) 이런 식으로 i 값을 늘려나가면 된다.
그런데 정확도는 다 맞았지만 효율성 테스트에서 전부 시간초과가 되었다. 내가 짠 코드를 자세히 보다 보니 이게 말이 dp지 정작 반복문은 O(N^2) 으로 돌고 있다는 것을 깨달았다.. i 반복문 돌면서 안에서 j<i 반복문 도는 것이 비효율적이구나 생각하고 다른 방법을 갈구한 결과
i 반복문 안에서 모든 j<i 를 확인할 필요 없이 strs의 element들을 확인하면서 (strs 길이가 100이하 조건!) 위 경우에 맞으면(알고리즘 로직 본질은 동일) dp 값을 바꿔주는 식으로 바꾸었다. 정확도 테스트에서 시간이 많이 줄은 것이 보였지만 그래도 효율성 테스트를 통과시키지 못하였다..
멘탈이 나가서 list 대신 dictionary 를 이용해 보기도 했는데 역시나 변함이 없었다.. 일단 또 다른 생각이 안나서 나중에 이런 문제들을 한꺼번에 고치기로 하고 일단 넘어가겠다.
(번외로 재귀함수도 이용해봤는데 정확성에도 시간초과 났다.. ㅋㅋ) 재귀함수 짜면서 느낀건데 뭔가 트리쪽 이용하면 될 것 같기도 하다. (쓸데없는 반복 줄이면 가능할듯..) -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A12983.py
