백준 2450 (모양 정돈) - java

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

2450번: 모양 정돈

 

문제

여러 개의 세모, 네모, 동그라미 모양들이 일렬로 나열되어 있다. 임의의 위치에 있는 두 개의 모양을 서로 맞바꾸는 작업을 반복하여 같은 모양끼리 연속하도록 정돈하려고 한다. 단, 정돈된 모양의 순서는 상관없다.

예를 들어, 모양들이 다음과 같이 나열되어 있다고 하자. 

△ ○ ○ □ △ △ ○ □

첫 번째 위치에 있는 세모와 일곱 번째 위치에 있는 동그라미를 맞바꾸면 다음과 같이 된다.

○ ○ ○ □ △ △ △ □

이어서, 다섯 번째 위치에 있는 세모와 마지막에 있는 네모를 맞바꾸면 다음과 같이 된다.

○ ○ ○ □ □ △ △ △

위와 같이 맞바꾸기를 두 번하면 같은 모양들끼리 연속하도록 정돈할 수 있지만, 한 번의 맞바꾸기만으로 같은 모양들끼리 연속하도록 하는 방법은 없으므로 이 경우 모양을 정돈하기위해 필요한 맞바꾸기의 최소 횟수는 2이다. 

일렬로 나열된 모양들의 순서가 입력으로 주어질 때, 같은 모양들끼리 연속하도록 정돈하기 위해 필요한 맞바꾸기 의 최소 횟수를 출력하는 프로그램을 작성하시오.

 

유형 : 구현

 

접근 방식

• 입력이 최대 100,000이므로 2중 반복문을 통한 탐색은 시간 초과가 발생한다.
• 우리가 고려해야 할 가짓 수는 몇가지일까?
  • 6가지 : 1, 2, 3 모양이 존재하기 때문에 3의 순열값인 {1,2,3} , {1,3,2} , {2,1,3}, {2,3,1} , {3,1,2} , {3,2,1} 6가지만 고려하면 된다.
  • 모양을 정렬시키는 방법은 무엇일까 ? (이 로직을 생각해내는 것이 어렵다)
    • 우선 주어진 입력에 대해서 1,2,3 모양의 개수를 파악한다.
    • 간단히 생각해보자면 첫번째 모양을 전부 맞추고 나머지 2개의 모양을 맞추는 것이다.
      • 6가지 경우의 수를 전부 수행한다면 첫번 째 모양이 1,2,3인 경우 모두를 고려할 수 있다.
      • 각 모양이 원래 위치해야 하는 위치와 현재 입력의 잘못된 정도를 저장한다.
      • dp[i][j] : i 번째 모양이 와야 하는 위치에 j 모양이 있는 수
  • 정답 : dp[cur[1]][cur[2]] + dp[cur[1]][cur[3]] + max(dp[cur[2]][cur[3]] , dp[cur[3]][cur[2]])

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;
    static int[] board;

    // 6가지 경우의 수
    static int[][] sum = {
            {1,2,3},{1,3,2},
            {2,1,3},{2,3,1},
            {3,1,2},{3,2,1}
    };
    
    static int result = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());

        board = new int[n+1];
        st = new StringTokenizer(bf.readLine(), " ");

        for(int i=1;i<=n;i++){
            board[i] = Integer.parseInt(st.nextToken());
        }

        // 6가지 경우의 수에 대해 수행
        for(int i=0;i<6;i++) {
            makeTmp(i);
        }

        System.out.println(result);
        bf.close();
    }

    static void makeTmp(int cur){
        int[][] dif = new int[4][4]; // i 모양이 와야 하는 영역에 j 모양이 있는 경우

        int tmpResult = 0;
        int idx = 1;

        for(int i=1;i<=num[sum[cur][0]];i++){
            dif[sum[cur][0]][board[idx]] += 1;
            idx ++;
        }

        for(int i=1;i<=num[sum[cur][1]];i++){
            dif[sum[cur][1]][board[idx]] += 1;
            idx++;
        }

        for(int i=1;i<=num[sum[cur][2]];i++){
            dif[sum[cur][2]][board[idx]] += 1;
            idx++;
        }

        // 첫번째 모양을 맞추기 위해 옮겨야 하는 횟수
        tmpResult += dif[sum[cur][0]][sum[cur][1]] +  dif[sum[cur][0]][sum[cur][2]];
        
        // 나머지 두가지 모양을 맞추기 위해 옮겨야 하는 횟수
        tmpResult += Math.max(dif[sum[cur][1]][sum[cur][2]] ,  dif[sum[cur][2]][sum[cur][1]]);

        result = Math.min(result,tmpResult);
    }

}