코딩 잘하고 싶어

해커랭크에 있는 Lily's Homework 문제에 대해 정리해보려고한다. 어떤 알고리즘을 써야 적합한지에 대해서는 생각해냈지만, 구현방식을 생각해내지 못해 몇개의 테스트케이스에서 시간초과가 났다. 해결 과정 먼저, 문제를 읽고 도출해야하는 것이 크게 두가지라고 생각한다. 1. "인접한 인덱스의 원소의 차가 가장 작게 만들어야한다" -> 오름차순이나 내림차순으로 정렬이 되어야한다는 말이다. 2. "두 인덱스를 최소 횟수로 swap하여 1번 상태를 만들어야한다." -> 정렬 방법 중에 선택 정렬을 한다. 그런데, 선택 정렬은 시간복잡도가 O(N^2)이다. 기준 인덱스를 모두 도는 것이 (N) * 나머지 인덱스 중에 가장 작거나 큰 값 찾기 (N-1) 이 문제의 N의 최대값은 10^5이기 때문에 시간초과가 ..