Softeer Lv3 - 효도 여행

문제

https://softeer.ai/practice/7649

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

풀이 시간 : 6시간

시도 횟수 : 18

복기

 

문제를 잘못 읽어 시간을 낭비했다

세번째 줄 부터 N-1 개의 줄이 나온다는 것과, 행복지수는 LCS 의 길이로 결정된다는것

나는 최대 행복지수 길이의 갯수가 최대 행복지수가 되는 줄 알았다 ㅠ 3이라고 하면,  ABC, BCA, DDD 3개니깐 3 이라고 생각했지만 이는 잘못된 생각이었다.

 

문제 풀이 방법은 간단했다.

Leaf 노드까지의 거리를 계산 + LCS 

LCS를 너무 오랜만에 봐서 기억을 더듬어 가며 구현하여 시간이 많이 걸렸다.

 

그 결과 시간초과가 났다.... >> 자꾸 시간초과 나는 것을 생각치 못한다. 시간초과를 방지하기 위해 최대크기로 데이터를 넣어서 충분히 통과할 수 있는지 검증하는 버릇이 필요하다.

 

StirngBuffer와 T 의 길이 M 가지고 이리저리 최적화 시도를 했지만 이는 나중에 적기..

 

 

결론적으로는 PriorityQueue  + LeafNode까지의 문자열 중복제거 최적화로 풀었다.

 

 

더 나은 풀이 방법

DP를 더 고도화하면 빠르게 풀 수 있을 것으로 생각된다. 이는 나중에 생각해보자 재밌었다.

 

DP[i][j][k] = i 번째에서 arr j 번째 문자를 썼을때 최대 LCS, 이때 k 는 arr[j]

그러니까.. abc와 abd가 있다 치자.

abc를 계산하고,

ab가 먼저 계산되어있다면 abd는 d만 계산해주면 되는거니깐... ? 될것같은데?