[기출 상] 집으로 가는 길(사다리 타기 문제) - 정렬
[문제] 초기의 사람 배치 순서를 입력받아 각 사람이 자신의 집으로 돌아갈 수 있게 하는 최소 개의 다리의 수를 return 하도록 해라. 예를 들어 [3, 2, 1, 4] 의 순서대로 있는 사람이 [1, 2, 3, 4]의 자신의 집으로 돌아가기 위해 놓아야 하는 최소한의 사다리 개수는 3개이다. [풀이] 사다리 문제의 규칙을 알아내는 것이 중요하다. 사람이 3, 2, 1, 4의 순서로 배치되어있다고 하자. 3과 2 사이에 사다리를 하나 놓으면 [2, 3, 1, 4]로 사다리 왼쪽, 오른쪽 순서가 바뀌는 것을 알 수 있다. 3과 1 사이에 하나 더 놓으면 [2, 1, 3, 4]로, 2와 1 사이에 하나 더 놓으면 [1, 2, 3, 4]로 순서가 바뀌므로 최소 3개의 사다리를 놓아야 한다. 따라서 이는 정..
