BOJ 10923 - 정렬하기
어케 푸는지 모르겠는데 그냥 맞아버렸다.
일단 마지막에 어떻게 되는지를 직접 해본다.
그런다음 를 가 마지막에 어느 위치에 가있는지에 대한 값으로 초기화하자.
개의 수들이 계속 위치가 변하는 과정을 생각해보면 개의 선이 계속해서 겹칠때 없이 움직이는 모양으로 생각할 수 있다.
번째 수를 고려한다.
번째 수가 현재 위치가 이면 이랑 이걸 swap한다.
이제 번째 수도 계속 번을 진행하며 직접 구해준다.
이 방법이 유효한 이유는 개의 선이 겹치지 않고, 번 째 수는 이미 번째로 가는 라인으로 태워줬기 때문에 그 이후 과정에서 이 라인을 건드릴 일이 없기 때문이다.
나머지 개는 으로 적당히 채워주도록 하자.
Comments