2022/10/26 수요일

Gong Intaek·2022년 10월 26일

Level 2 프로그래머스 하노이의 탑

일상

목록 보기

504/1031

오늘 한 일

프로그래머스
- 하노이의 탑 (Level 2)
실내 운동

문제 풀이

하노이의 탑 (Level 2)Github

원판의 갯수가 주어진 하노이의 탑을 풀수 있는 최단 횟수의 방법을 돌려주는 문제.

풀이 완료

우선 풀이법은 직관적으로 다가오진 않았다. 해서 작은 갯수의 원판을 사용 할때의 풀이법을 늘어놓고 고민해 보았다. 아래 주석들은 풀이를 할때 고민하면서 적어본 풀이법이다.

// n= 1  [1,3] s=1 m=2 e=3
// n= 2  [1,2] => [1,3] => [2,3]
// n= 3  [1,3] => [1,2] => [3,2] => [1,3] => [2,1] => [2,3] => [1,3]
// n= 4
// [1,2,3,4] [] []
// [2,3,4] [1] []  = [1,2]
// [3,4] [1] [2] = [1,3]
// [3,4] [] [1,2] = [2,3]
// [4] [3] [1,2] = [1,2]
// [1,4] [3] [2] =  [3,1]
// [1,4] [2,3] [] = [3,2]
// [4] [1,2,3] [] = [1,2]
//    [1,3]

위와 같이 늘어놓고 보니 풀이법의 길이가 원판이 늘어감에 따라 일정한 갯수로 늘어나고 있었으며 그 풀이법도 뭔가 유사해보이는 것을 확인할수 있었다. 그리고 조금더 생각 해본 결과 풀이법의 일부의 차이는 해당 풀이가 진행될때의 원판들의 위치와 움직여야할 장소의 차이라는 생각이 들었다.

해서 원판이 놓여야할 위를 시점, 종점, 중간점으로 구분하고 원판의 갯수까지 포함해서 입력값으로 받는 함수를 생각해보았다.

n 원판의 갯수, s 시점, m 중간점, e 종점
f(n,s,m,e)

그리고 원판의 갯수가 1개와 2개일때와 위에서 생각한 함수를 조합해보았다.

f(2,1,2,3) => f(1,s,e,m) [s,e] f(1,m,s,e)
			=> [1,2], [1,3], [2,3]

f(3,1,2,3) => f(2,s,e,m) [s,e] f(2,m,s,e)
		   => f(1,s,m,e) [s,m] f(1,e,s,m) [s,e] f(1,m,e,s) [m,e] f(1,s,m,e)
		   => [1,3], [1,2], [3,2], [1,3], [2,1], [2,3], [1,3]

위와 같은 관계가 원판의 갯수와 무관하게 적용 되는것을 확인할수 있었고, 이를 통하면 문제풀이를 마무리 할수 있었다.

추후 진행 예정인 작업(잠정 중단.)

socket.io 서버로 하는 단순한 멀티 룸 채팅.
위의 결과를 server-side로 구현해보기.
firebase 사용법 배우기
serverless lambda 학습하기

오늘은...

쿼리 체인
시퀄라이즈 쿼리를 통해 구한 데이터의 아이디 목록을 다음 쿼리에서 조회 조건으로 사용하여 걸러진 데이터를 재활용 하는 방법을 찾음.(이제야 찾아냈다는게 맞겠지...)
where 절에 아이디 배열을 Op.or를 통해 아이디 목록에 일치하는 대상만 선택함. 여기에 필터해야할 조건 하나를 추가하여 결과를 얻어 동일하 아이디목록으로 다음 차례에 넘겨줌.