[BOJ_2872] 우리집엔 도서관이 있어

 

📌 문제 링크: https://www.acmicpc.net/problem/2872

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

 

✅ 내 풀이(Success) :

 

🧐 Review:

 풀이를 제출했을 때 시간 초과로 6번이나 틀렸지만, 7번째 제출에서 문제를 맞을 수 있었다. 끝까지 답안을 확인하지 않고 스스로 풀어낸 것이 뿌듯하다. 백준에서 시간 초과로 제출한 풀이가 틀렸다는 것은 답안의 전체적인 로직에는 문제가 없으나 입력값에 따라서 연산 횟수가 크게 증가하는 부분 때문에 상한선을 넘어가는 구간이 발생해 틀렸다는 의미이다. 그래서 시간 복잡도를 최대한 낮추는 방향으로 코드를 수정하면 풀 수 있다고 생각하였고, 몇 번의 실험 끝에 문제를 맞을 수 있었다.

 

🚩 Idea:

 책을 정렬하는 방법은 책 한 권을 빼서 책장에 가장 위에 올리는 것이다. 이렇게 정렬하면 방금 정렬한 책의 숫자보다 낮은 숫자를 가진 책들은 모두 정렬대상이 된다. 이때, 해당 책 보다 큰 수를 가진 책은 나머지 책들을 정렬하는 과정에서 자동으로 책장에 밑으로 이동하기 때문에 정렬하지 않아도 된다.