[백준 2872번] 우리집엔 도서관이 있어 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

먼저 입력으로 알 수 있는 항목은 총책의 수와 현재 책이 쌓여 있는 형태를 알 수 있습니다.

 

3

1

4

5

2

배열의 왼쪽이 위쪽이고 오른쪽이 바닥 쪽이고 위 표처럼 책이 쌓여 있다면 이동이 필요한 책은 1번과 2번입니다.

5번의 경우 입력으로 주어진 책 중 가장 큰 값을 가진 책이므로 어느 위치에 있든 움직일 필요가 없습니다.

4번의 경우는 5번 다음으로 위쪽에 위치하므로 4번 또한 이동이 필요 없습니다.

그럼 3번의 경우는 바로 위쪽이 아니지만, 이동이 필요없는 이유는 무엇일까요?

그건 1번이 움직이면 자연적으로 4번 위쪽으로 위치되기 때문입니다.

2

3

1

4

5

먼저 2번의 책을 가장 위쪽으로 이동하고

1

2

3

4

5

마지막으로 1번의 책을 가장 위쪽으로 이동하면 정렬은 완료됩니다.

즉 이것을 풀어보면 입력받은 책 중 가장 큰 책을 기준으로 왼쪽으로 정렬이 된 책을 제외하면 이동해야 되는

책의 숫자가 나오는 것입니다.

예시에서는 5번이 가장 큰 책이니 가장 오른쪽 Index에서부터 가장 왼쪽 0 Index로 5번을 찾기 시작합니다.

가장 오른쪽에서부터 찾는 이유는 가장 큰 숫자의 책이 있어야 하는 위치는 가장 오른쪽 이기 때문입니다.

만약 5번을 찾았다면 이번에는 4번을 찾아 이동을 계속합니다.

이동 도중 찾고자 하는 책이 아닌 숫자의 책이 있다면 그 책은 이동이 필요한 책이라는 것을 알 수 있습니다.

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int bookCnt = Integer.parseInt(br.readLine());

List<Integer> bookList = new ArrayList<>();

for(int i=0; i<bookCnt; i++)
	bookList.add(Integer.parseInt(br.readLine()));

int result = 0;

Collections.reverse(bookList);

int target = bookCnt;

for(int i=0; i<bookCnt; i++){
	if(bookList.get(i) == target)
		target--;
	else
		result++;
}

bw.write(result + "\n");
bw.flush();