2872 우리집엔 도서관이 있어

1. 문제 풀이법

 

<예시1>

35421

 

이때 책 번호 5,4,3,2,1 순서로 생각해보면 된다.

자세히 살펴보자.

 

책을 빼서 맨 위에 올려 놓을 떄마다 count 를 증가시켜 보자.

 

1) 5는 그냥 그 자리에 두면 된다.

 

2) 4는 5 뒤에 있기 때문에 책을 빼서 맨 위에 올려 놓아야 한다.

=> 43521

count = 1

 

3) 3은 4뒤에 있기 때문에 책을 빼서 맨 위에 올려 놓아야 한다.

=> 34521

count = 2

 

4) 2도 마찬가지이다.

=> 23451

count = 3

 

5) 1도 마찬가지이다.

=> 12345

count = 4

 

최종 답은 4가 된다.

 

그러면 생각해보자.

35421에서,

5뒤에 있는 4,2,1은 모두 그 자리에서 빼서 맨 위에 올려 놓았다.

 

5앞에 있던 3 역시 이동이 있었다.

2)에서 4를 맨 위로 올린(43521)다음

3)에서 3을 4위로 올렸다. (34521)

 

그런데 생각해보자.

만약 5 앞에 4가 있었다면 어땠을까?

 

<예시2>

34521

 

5뒤에 있는 2,1은 당연히 위로 올려야 된다.

그런데 5 앞에 있는 3,4는 이미 정렬된 상태이기 때문에 그냥 둬도 된다.

 

이런 풀이를 코드에서 볼 수 있다.

우선 입력값을 book 배열에 넣는다.

처음에 max = N = 5 이다.

그리고 책을 올릴 때마다 result 를 1씩 증가시킨다.

 

1) book[4] =1 로 max 값인 5가 아니다.

=> result를 증가시킨다. (책을 맨 위로 올림)

result = 1

 

2) book[3] = 2 도 max 와 다르다.

=> result = 2

 

3) book[2] = 5는 max 값과 같다. 그래서 그냥 그 자리에 둬도 된다.

=> max = 4 가 된다. (max 값을 1줄인다.)

 

4) book[1] = 4도 max 값과 같다. 그냥 둔다.

=> max = 3

 

5) book[0] = 3 으로, max 값과 같다. 그냥 둔다.

 

그래서 최종 result =2 이다.

즉, 책을 2번만 이동시키면 된다.

 

맨 처음 설명한 <예시1>도 코드로 다시 살펴보자.

<예시1>

35421

 

맨 처음 max = 5 이다.

 

1) book[4] =1 로 max 값과 다르므로 result = 1

2) book[3] = 2로 max 값과 다르므로 result = 2

3) book[2] = 4 로 max 값과 다르므로 result = 3

4) book[1] = 5 로 max 값과 같으므로 그냥 둔다. max = 4가 된다.

5) book[0] = 3 으로 max 값과 다르므로 result = 4

 

최종 4번 책을 이동시키면 된다.

 

 

 

2. 최종 코드

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
				
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int book [] = new int[N];
		
		for(int i=0; i<N; i++) {
			book[i] = Integer.parseInt(br.readLine());
		}
		
	
		int max = N;
		int result = 0;
		
		for(int i=N-1; i>=0; i--) {
			if(book[i] == max) {
				max--;
			}else {
				result++;
			}
		}
		
		System.out.println(result);
		
	}
}

 

 

참고 블로그 :

https://comengin.tistory.com/350

백준 2872