[JAVA] 백준 7570 줄 세우기

https://www.acmicpc.net/problem/7570

문제분석

제목 그대로 순서대로 줄을 세우는 것이다. 단, 맨 앞이나 맨 뒤로만 보낼 수 있다는 조건을 지켜야 한다.

예를들어, 5 4 2 3 1로 서있는 경우, 1을 맨 앞으로,  4를 맨 뒤로, 5를 맨 뒤로 보내야 1 2 3 4 5로 정렬이 된다.

최소한으로 움직여서 정렬이 완료되는 경우, 그 최소한으로 움직인 값은?

해결과정

"덩어리" 를 만들기로 했다. 여기서 "덩어리" 의 정의는 다음과  같다.

1. 연속적인 수(3, 4, 5, 6...)

2. 이 수들은 붙어있을 필요는 없다(3, 5, 2, 6, 1, 7, 4...)->덩어리 5,6,7

3. 최소한으로 움직이는 경우는, 이 덩어리들 중  가장 큰 덩어리가 움직이지 않는 경우.

이 덩어리가 가장 클  때가, 최소한으로 움직이는 경우이고, 그때의 값은 (전체 인원)-(덩어리 인원)이다(덩어리는 움직이지 않기 때문).

 

Map자료형을 사용하기로 했다. 이때, Map에는{최대값 : 덩어리 내용물의 갯수}가 저장된다.

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<Integer,Integer> m=new HashMap<>();//{최대값:저장된 숫자 수}
        int max=0;
        for(int i=0;i<=n-1;i++){
            int temp=Integer.parseInt(st.nextToken());
            if(m.containsKey(temp-1)) {//map안에 키값으로 temp-1가 존재
                m.put(temp,m.get(temp-1)+1);
            }else{//키값으로 temp가 존재하지 않음
                m.put(temp,1);
            }
            max=Math.max(max,m.get(temp));
        }
        System.out.println(n-max);
    }
}

 

 

확실히 파이썬과 자바 서로 장단점이 있는 것 같다. 정석적으로 배운건 자바여서 그런지 모르겠지만, 다양한 자료형을 사용할 수 있는 것이 장점인 것 같다.