라스칼라 코딩단 문제 페이지 (다른 분들 해법도 볼 수 있다.)
라스칼라 코딩단에서 푼 문제를 정리해본다. 한 달 전쯤부터 나가고 있는데 스칼라에 대한 단순한 궁금증에서 시작되었지만 훌륭한 분들이 많이 계셔서 금요일 저녁이지만 매 주 빠지지 않는 스케줄이 되었다. 제대로 키보드를 잡아서 푼 문제들의 풀이를 여기에 올려보고자 한다. 사실 이 문제는 스터디 시간에 다 풀지 못해서 집에 와서 끙끙대며 풀었다. (시간도 엄청 걸림)
일단 마지막 문제인 D인데다 도전자 수도 적고 스몰 케이스 성공 확률도 낮은 걸 보면 이 레벨에서 최고 난이도를 자랑한다.
문제를 대략 설명하자면 a, b, c, d로 이루어진 문자열에서 특정 DNA 패턴의 조합수를 찾아내는 문제이다. DNA 패턴의 조건은 “A와 C의 개수와 B와 D의 개수가 일치해야 하는 것”이고 Albocede-n은 이런 DNA가 여러 번 반복될 수 있다. 주어진 문자열에서 가능한 모든 Albocede-n의 숫자를 세는 게 이번 문제이다.
먼저 어려운 점은 다음과 같다.
- 문자열이 길면 길어질수록 가능한 가짓수가 기하급수적으로 불어나기 때문에 중간에 잘라주는 일종의 early termination이 필요하다.
- 재귀로 도는 게 거의 필수이고 동적 프로그래밍이기 때문에 메모이제이션이 꼭 있어야 한다.
입출력을 담당하는 main 함수는 빼고 설명하자면 solve 함수는 String을 그대로 매개변수로 받아서 가능한 가짓수를 Long 형식으로 반환한다. 메모이제이션을 담당할 HashMap을 선언하는데 약간 특이하게 느껴졌던 점은 Map에 원소를 추가하는데 mutable 선언만 하면 var로 명시적으로 바뀔 수 있는 변수라고 선언하지 않아도 된다는 것이었다.
이제 재귀를 돌릴 _solve 함수가 나오는데 String의 뒤에서부터 세기 때문에 dna의 길이가 될 i, 현재 필요한 a와 b의 개수를 기록하는 a와 a, b 그리고 들고 있는 캐릭터인 ch가 _solve의 매개변수가 된다.
x는 현재 보고 있는 캐릭터를 꺼내지 않고 지나갈 경우를 세는 것인데, 밑에서 계속 쓰이므로 미리 계산해둔다. (라인 9)
앞까지 다 셌을 때 (i == 0) a나 b가 더 필요하다거나 들고 있는 캐릭터가 a가 아니면 Albocede-n 형식으로 볼 수 없으니 0을 반환한다. (라인 10–11)
그렇지 않다면 패턴 매칭으로 d, c, b, a 순서대로 가기 시작하는데 우선 필요한 a나 b의 수보다 현재 남은 String의 a나 b의 수가 적으면 더 볼 것도 없이 Albocede-n 구성이 불가능하므로 0을 반환한다. (라인 13) 이 최적화 없이 로직만 돌릴 경우 시간 내에 끝낼 수 없다.
들고 있는 캐릭터가 빈 칸이면 아직 a,b,c,d 중 아무것도 꺼내지 않은 상태이다. 그렇다면 들고 있는 캐릭터가 빈 칸이나 d라야만 d를 꺼낼 수 있다. (라인 14) d를 꺼내면 b가 짝으로 필요하므로 재귀 돌면서 필요한 b값을 1 증가시킨다. c, b, a 다 같은 로직이며 그 외엔 필요한 a, b를 다 채웠을시 다음 dna를 찾을 때의 경우의 수와 멈출 때의 경우의 수를 각각 계산해 더해준다. (라인 18)
