간만에 프로그래머스에 들어왔다
알고리즘을 풀면서 느끼는 점은, 정말 쉬우면 한 없이 쉬운데 어려우면 한 없이 어렵다.
특히 문제의 끝자락에 왔을 때 마지막 포인트를 살리지 못하고 엎어질때 정말 지옥이다ㅜ
이번 문제도 그랬다.
https://school.programmers.co.kr/learn/courses/30/lessons/118667
deque를 사용해야지 라는 기술적인 접근은 당연히(?)했으나, while문을 돌면서 언제 멈춰야하는지가 문제였다.
두 queue의 length만큼 돌면 되는거 아닌가? 했는데, 두 queue length + 2만큼 돌아봐야 한다.
그리고 기발한 방법을 발견했는데
나의 경우에는 정직하게(?) 하나의 queue에서는 popleft를 다른 쪽 queue에서는 insert를 수행했는데, 두 개의 queue를 하나로 붙여서 start, end flag로 답을 찾을 수도 있었다. 😶
똑똑한 넘들 왜이리 많아 후...
이유는?
n = 3
[1,2,3], [4,5,6][1,2,3,4,5,6]
start = 0
end = n-1 = 2
움직임의 최대를 구해보면
| count | start | end | result(q1) |
|---|---|---|---|
| 1 | 1 | 2 | [2,3] |
| 2 | 2 | 2 | [3] |
| 3 | 2 | 3 | [3,4] |
| 4 | 3 | 3 | [4] |
| 5 | 3 | 4 | [4,5] |
| 6 | 4 | 4 | [5] |
| 7 | 4 | 5 | [5,6] |
| 8 | 5 | 5 | [6] |
n * 2 + 2
end는 n-1 → 2n -1까지 움직임 : 안포함, 포함 : n만큼
start는 end가 움직일때마다 n-1 만큼 움직임
n * n - n ?
