[백준] 2631 줄세우기 (JAVA) - 풀이

문제 분석

• 아이들의 번호 순서가 뒤바뀐 상태에서 오름차순으로 정렬하려고 할 때
• 위치를 옮기는 아이들의 최소 횟수 구하기

 

의사 결정

• 번호가 뒤바뀐 상태에서 LIS(최장 증가 부분 수열)의 갯수를 구하고, 전체 아이들 수에서 횟수를 빼는 방식을 사용했습니다.

 

코드 구현

1. 아이들의 수 입력, 배열에 번호 순서 저장

번호가 증가하는 순서대로 횟수를 저장하기 위해 배열을 선언하고, count 배열의 모든 인덱스를 1로 초기화 했습니다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] a = new int[N];
        int[] count = new int[N]; // 증가하는 순서대로 횟수 저장
		for(int i=0 ; i<N ; i++) {
			a[i] = Integer.parseInt(br.readLine());
            count[i] = 1; // 1로 초기화
		}

 

 

2. LIS(최장 증가 부분 수열) 갯수 구하기, 출력

그대로 유지하는 번호의 최대 개수를 구하기 위해 max를 1로 초기화했습니다.

 

이중 for문 사용해서 번호 a[i]를 기준으로 번호가 작은 a[j]를 찾습니다.

i번째 번호까지 만들 수 있는 가장 긴 수열의 길이를 유지하기 위해 번호 i의 횟수와 번호 j의 횟수 + 1 한 값을 비교해서 더 큰 값을 count[i]에 저장했습니다.

 

전체 번호 수에서 max 값을 빼서 최소한으로 이동해야 하는 번호의 수를 구해서 출력했습니다.

		int max = 1;
		for(int i=1 ; i<N ; i++) {
			for(int j=0 ; j<i ; j++) {
				if(a[i] > a[j]) {
					count[i] = Math.max(count[i], count[j]+1);
				}
			}
			max = Math.max(max, count[i]);
		}
		
		System.out.print(N-max);

 

 

 

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] a = new int[N];
        int[] count = new int[N];	
		for(int i=0 ; i<N ; i++) {
			a[i] = Integer.parseInt(br.readLine());
            count[i] = 1;
		}
		
		int max = 1;
		for(int i=1 ; i<N ; i++) {
			for(int j=0 ; j<i ; j++) {
				if(a[i] > a[j]) {
					count[i] = Math.max(count[i], count[j]+1);
				}
			}
			max = Math.max(max, count[i]);
		}
		
		System.out.print(N-max);
	}
}