[백준 / BOJ] 2872 우리집엔 도서관이 있어

문제

출처 : www.acmicpc.net/problem/2872

2872번: 우리집엔 도서관이 있어

상근이가 책을 정리할려고한다. 책은 1 2 3 4 5 ... N 순서대로 정리해야한다. 

책을 정리하는 방법은 임의의 책 한권을 뽑아서 가장 앞에 놓는다.

 

최소 몇번의 이동으로 책을 정리할수있는지 출력하는 문제다.

 

풀이

i번째 책이 i+1번째 책보다 낮은위치에 존재하는지 확인해주며 풀면 되는 문제다.

예를들어,

 

9

1 2 3 4 5 7 6 8 9

의 책이 있다고 하자.

 

(9번은 움직이지 않아도 된다. 9 번을 움직이면, 9보다 작은 모든책을 한번씩 움직여야해서, N번이동으로 정렬하게 된다. -> 최악 또, 9번을 제외한 모든 책을 앞으로 순서대로 움직이면, 항상 N-1번의 이동으로 끝낼수 있기때문에 9번을 움직이면 항상 최악의 횟수가 나온다.)

 

1. 8번 책을본다. 

8번책이 9보다 앞에 있으므로 정렬하지 않아도 된다.

 

2. 7번 책을 본다.

7번책은 8보다 앞에 있으므로 정렬하지 않아도 된다.

 

3. 6번 책을 본다.

6번책은 7보다 앞에있지않다. 따라서 맨앞으로 이동시켜야한다.

 

위 처럼 코드를 짜서 풀면 되는데,

주의할점이 배열로 자료구조를 선언해서 풀었다면,

6번책을 움직였을때 idx상으론, 5번책이 6번책보다 앞에있지만, 6번책을 움직였으므로 사실상 6번이 가장 앞에있는 구조가 된다.

이를, 맨앞으로 책을 옮길때마다 각 책의 인덱스를 하나씩 움직이면서(시뮬레이션?? 해가며)풀면 

30000 * 15000 만큼 반복해서 시간초과가 난다.

이를 해결하기 위해서, check 배열을 따로 선언해서,

5번책이 6번 책보다 앞에있지만, check[6번책]에 체크가 되어있다면, 5번책은 무조건 앞으로 이동시켜줬다.

(체크 되어있다는 뜻은 해당 책이 정렬되었다는 뜻이다. 즉 맨앞으로 이동했으니 항상 모든 수보다 작은 idx에 위치하고있다.)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2872%20%EC%9A%B0%EB%A6%AC%EC%A7%91%EC%97%94%20%EB%8F%84%EC%84%9C%EA%B4%80%EC%9D%B4%20%EC%9E%88%EC%96%B4/main.cpp

devxb/JJUNalgo