[문제] SORTGAME

2017. 10. 13. 23:41ㆍ[개발] 지식/알고리즘 문제풀이

문제 정보

문제

중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면 두 번만의 연산으로 정렬할 수도 있다.

정렬을 위해 뒤집기 연산을 최소 몇 번 해야 하는지를 계산하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 1000) 이 주어진다. 각 테스트 케이스의 첫 줄에는 수열의 길이 N (1 <= N <= 8) 이 주어진다. 다음 줄에 N개의 정수로 각 수열의 원소들이 순서대로 주어진다. 한 수열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋다. 모든 수는 1부터 1백만 사이의 정수이다.

출력

각 테스트 케이스마다 입력을 정렬하기 위해 필요한 최소 뒤집기 연산의 수를 출력한다.

예제 입력

3
8
1 2 3 4 8 7 6 5
4
3 4 1 2
3
1 2 3

예제 출력

1
2
0

https://algospot.com/judge/problem/read/SORTGAME


1차 시도

package apss;



import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.FileInputStream;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;



public class Sortgame {

	public static int N;
	public static ArrayList<Integer> visited;
	public static int finalDepth;

	public static void main(String[] args) throws NumberFormatException, IOException {

		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("D:\\sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine().trim());

		for(int tc=0; tc<T; tc++){

			N = Integer.parseInt(br.readLine());
			visited = new ArrayList<Integer>();
			int[] firstSeq = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());

			for(int i=0; i<N; i++){
				firstSeq[i] = Integer.parseInt(st.nextToken());
			}

			finalDepth = 0;
			makeGraph(firstSeq);

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

		}
		
		bw.close();

	}

	public static void makeGraph(int[] preSeq){

		Queue<int[]> Q = new LinkedList<int[]>();
		Queue<Integer> Q_Depth = new LinkedList<Integer>();
		Q.add(preSeq);
		Q_Depth.add(0);

		boolean flag = false;
		for(int i=0; i<N; i++){

			if(preSeq[i] != (i+1)){
				flag = true;
				break;
			}

		}

		if(!flag){
			return;
		}

		while(!Q.isEmpty()){

			int[] nextSeq = Q.poll();
			int[] buffSeq;
			int depth = Q_Depth.poll();
			boolean isNotSorted = false;

			for(int i=0; i<N; i++){

				for(int j=i+1; j<N; j++){

					int h = j;
					isNotSorted = false;
					buffSeq = new int[N];
					
					for(int k=0; k<N; k++){

						if(k >= i && k<=j){
							buffSeq[k] = nextSeq[h];
							h--;
						}else{
							buffSeq[k] = nextSeq[k];
						}

						if((k+1) != buffSeq[k]){
							isNotSorted = true;
						}

					}

					if(isNotSorted == false){ // 정렬이 되었다면
						finalDepth = depth+1;
						return;
					}

					Q.add(buffSeq);
					Q_Depth.add(depth+1);

				}

			}

			

		}

		

	}


}

단순 BFS를 이용해서 풀었다.

하지만 이렇게 하면 모든 경우를 탐색하기 때문에 시간초과가 뜬다.
인풋을 가공해서 중복되는 계산을 줄이면 수십배 빠른 결과를 얻을 수 있다.

예를 들어 [2, 1, 3, 4] 와 [21, 13, 46, 47]은 동일한 결과를 얻을 것이다. 결국 정렬에 필요한 이동 수는 같기 때문이다. 이를 [1, 0, 2, 3] 으로 표준화 하면 된다. 
방법은 아래에 있다.

2차 시도

package apss;



import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Sortgame_solution {

	public static int N;
	public static ArrayList<Integer> visited;
	public static int finalDepth;
	public static Map<int[], Integer> toSort;

	public static void main(String[] args) throws NumberFormatException, IOException {

		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("D:\\sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine().trim());

		for(int tc=0; tc<T; tc++){

			N = Integer.parseInt(br.readLine());
			visited = new ArrayList<Integer>();
			int[] firstSeq = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());

			for(int i=0; i<N; i++){
				firstSeq[i] = Integer.parseInt(st.nextToken());
			}

			toSort = new HashMap<int[], Integer>();
			finalDepth = 0;
			
			makeGraph(N);

			bw.write("" + solve(firstSeq) + "\n");
			bw.flush();

		}
		
		bw.close();

	}

	public static void makeGraph(int n){
		
		int[] seq = new int[n];
		for(int i=0; i<n; i++){
			seq[i] = i;
		}

		Queue<int[]> Q = new LinkedList<int[]>();
		Q.add(seq);
		toSort.put(seq, 0);

		while(!Q.isEmpty()){

			int[] nextSeq = Q.poll();
			int[] buffSeq;
			int depth = getValue(toSort, nextSeq);

			for(int i=0; i<N; i++){

				for(int j=i+1; j<N; j++){

					int h = j;
					buffSeq = new int[N];
					
					for(int k=0; k<N; k++){

						if(k >= i && k <= j){
							buffSeq[k] = nextSeq[h];
							h--;
						}else{
							buffSeq[k] = nextSeq[k];
						}

					}
					
					if(!containsKeyInMap(toSort, buffSeq)){
						toSort.put(buffSeq, depth+1);
						Q.add(buffSeq);
					}

				}

			}

		}

	}
	
	public static boolean containsKeyInMap(Map<int[], Integer> map, int[] destArr){
		
		int[] srcArr;
		Set keySet = map.keySet();
		Iterator iter = keySet.iterator();
		while(iter.hasNext()){
			srcArr =  (int[])iter.next();
			if(Arrays.equals(srcArr, destArr)){
				return true;
			}
		}
		
		return false;

	}
	
	public static int solve(int[] srcArr){
		int n = srcArr.length;
		int[] fixed = srcArr.clone();
		
		for(int i=0; i<n; i++){
			int smaller = 0;
			for(int j=0; j<n; j++){
				if(srcArr[j] < srcArr[i]){
					smaller++;
				}
			}
			fixed[i] = smaller;
		}
		
		return getValue(toSort, fixed);
	}
	
	public static int getValue(Map<int[], Integer> map, int[] key){
		
		int[] srcArr;
		Object value;
		Set keySet = map.keySet();
		Iterator iter = keySet.iterator();
		while(iter.hasNext()){
			value = iter.next();
			if(Arrays.equals((int[])value, key)){
				return map.get(value);
			}
		}
		
		return -1;
		
		
	}



}

이 소스로 제출하면 훨씬 느려진다.

C코드 솔루션을 기준으로 java로 변환하려고 한건데, HashMap에서 key를 Object로 주니 containsKey와 get 메서드를 사용할 수 없다. 즉, Object key로 value를 찾을 수 없다.

이를 해결하려면 hashCode()와 equals()를 오버라이드 할 필요가 있어 보인다.

오버라이드 말고 다른 방법이 있는지도 찾아봐야겠다. 아니면 아예 다르게 접근하는 것도 고려할 필요가 있어 보인다.

Solution

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Sortgame_solution {

	public static int N;
	public static Map<Integer, Integer> toSort[];
	public static int[] firstSeq;
	public static int[] sorted;

	public static void main(String[] args) throws NumberFormatException, IOException {

		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("E:\\sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine().trim());
		
		toSort = new HashMap[8];
		for(int i=0; i<8; i++){
			toSort[i] = new HashMap<Integer, Integer>();
		}
		
		for(int i=0; i<8; i++){
			sorted = new int[i+1];
			for(int j=0; j<i+1; j++){
				sorted[j] = j;
			}
			toSort[i].put(Arrays.hashCode(sorted), 0);
			makeGraph(i+1);
		}
		
		for(int tc=0; tc<T; tc++){

			N = Integer.parseInt(br.readLine());
			firstSeq = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());

			for(int i=0; i<N; i++){
				firstSeq[i] = Integer.parseInt(st.nextToken());
			}
			
			bw.write("" + solve(firstSeq) + "\n");
			bw.flush();

		}
		
		bw.close();

	}

	public static void makeGraph(int n){

		Queue<int[]> Q = new LinkedList<int[]>();
		Q.add(sorted);

		while(!Q.isEmpty()){

			int[] nextSeq = Q.poll();
			int[] buffSeq;
			int depth = toSort[n-1].get(Arrays.hashCode(nextSeq));

			for(int i=0; i<n; i++){

				for(int j=i+1; j<n; j++){

					int h = j;
					buffSeq = new int[n];
					
					for(int k=0; k<n; k++){

						if(k >= i && k <= j){
							buffSeq[k] = nextSeq[h];
							h--;
						}else{
							buffSeq[k] = nextSeq[k];
						}

					}
					
					if(!(toSort[n-1].get(Arrays.hashCode(buffSeq)) != null )){
						toSort[n-1].put(Arrays.hashCode(buffSeq), depth+1);
						Q.add(buffSeq);
						
					}

				}

			}

		}

	}
	
	
	public static int solve(int[] srcArr){
		int[] fixed = srcArr.clone();
		
		for(int i=0; i<N; i++){
			int smaller = 0;
			for(int j=0; j<N; j++){
				if(srcArr[j] < srcArr[i]){
					smaller++;
				}
			}
			fixed[i] = smaller;
		}
		
		Map rtMap = toSort[N-1];
		int rtDepth = (int) rtMap.get(Arrays.hashCode(fixed));
		return rtDepth;
	}
	


}

HashMap의 Key를 int 배열을 그대로 쓰지 않고, hash값을 생성해서 사용했다.
결과는 정확히 나오는데, '시간초과'가 계속 떴다.
이유는 N이 1~8의 범위까지인데, 테스트케이스마다 반복해서 동일한 sorted 배열을 생성하는데 있어 시간낭비가 생겼기 때문이다.
8개의 sorted 배열만 미리 만들어두면 여러개의 테스트케이스에서 재활용할 수 있으므로 시간을 절약할 수 있다.

저작자표시

'[개발] 지식 > 알고리즘 문제풀이' 카테고리의 다른 글

[문제][Algospot] PROMISES(선거공약)  (0) 2018.04.22
[문제] 감시 카메라 설치 (GALLERY)  (0) 2017.11.11
벨만-포드 알고리즘  (0) 2017.09.20
[DFS] 오일러 서킷  (1) 2017.08.20
[DFS] 문제 : 고대어 사전  (0) 2017.08.07

관련글

댓글 0
<

티스토리툴바