[백준/BOJ] 1039번 교환 자바 풀이

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

1039번: 교환

문제

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

 

 

BFS로 풀 수 있는 골드3 문제다.

 

 

 

 

		String temp = st.nextToken();
		M = temp.length();
		N = Integer.parseInt(temp);
		K = Integer.parseInt(st.nextToken());
		
		arr = new int[M];
		for(int i=0;i<M;i++) 
			arr[i] = temp.charAt(i) - '0';

	static int getNumber(int[] a) {
		int ret = a[0];
		
		for(int i=1;i<M;i++) {
			ret *= 10;
			ret += a[i];
		}
		
		return ret;
	}

배열에 각 자리수의 숫자를 저장하고, 숫자를 바꿀 때에는 배열의 값만 바꿔준다.

answer를 구할 때는 배열의 값을 10씩 곱해가면서 숫자를 만든다.

 

 

 

문제의 예제3 처럼,

132 -> 312 -> 321 -> 312 가 되어 같은 값을 중복되게 구할 수 있다.

중복되는 값을 여러번 구하는 것을 줄이기 위해, visit라는 HashSet에 Number 객체를 넣어

visit에 동일한 배열 값이 있다면 큐에 넣지 않고, visit에 동일한 배열 값이 없다면 큐에 넣는다.

 

 

 

	static class Number {
		int[] num;
		int cnt;

		Number(int[] num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		
		@Override 
		public boolean equals(Object o) {
			Number n = (Number)o;
			return Arrays.equals(this.num, n.num);
		}
		
		@Override
		public int hashCode() {
			return ("").hashCode(); // 배열 값을 비교해야 하므로 hashcode는 모두 같은 값을 가지도록 함
		}
	}

 

이때 Number는 각 자리의 숫자가 저장된 배열, 교환 횟수가 담긴 클래스다.

 

 

HashSet 속 Number의 배열이 같은 값을 가지는지 판단하기 위해서는

hashCode()와 equals()를 Override로 재정의해주어야 한다.

HashSet/HashMap/HashTable은 hashCode()로 해시값을 비교한후, 해시값이 같다면 equals로 객체를 비교한다.

여기서는 배열값이 같으면 같다고 판단해야 하기 때문에 해시값은 무조건 같은 값을 갖도록 정의하고,

equals에서는 Arrays.equals(arr1, arr2)를 이용해 배열의 모든 원소가 같은 값이라면 true, 하나라도 다르다면 false를 반환하도록 해준다.

두 함수를 Override해줌으로써 HashSet의 contains 함수가 의도적으로 동작하는 것이다.

 

 

 

위 방법으로만 처리해준다면, 312의 교환횟수가 1이기 때문에 교환횟수가 3일 때의 최대값인 312를 구할 수 없다.

(교환횟수가 3일 때의 312는 HashSet에 contains되어있어 큐에 offer되지 않는다)

 

이때, 312->321->312가 되는 것처럼 같은 위치를 짝수번으로 교환해주면 같은 값을 가진다는 것을 알 수 있다.

즉, 교환횟수가 1일 때의 값은 교환횟수가 3, 5, 7등 교환횟수를 짝수번 더했을 때 같은 값이 나올 것이다.

같은 원리로 교환횟수가 2, 4, 8일때의 값은 교환횟수가 10, 12, 14 일때도 중복되게 나타날 것이다.

 

 

			if(now.cnt % 2 == K % 2) {
				answer = Math.max(getNumber(now.num), answer);
			}

K가 홀수라면 K보다 작고 홀수인 교환횟수일 때 구한 값을 모두 포함한다.

만약 짝수라면 K보다 작고 짝수인 교환횟수일 때 구한 값을 모두 포함한다.

 

 

 

			for(int i=0;i<M;i++) {
				for(int j=i+1;j<M;j++) {
					if(now.num[i] == now.num[j]) {
						answer = Math.max(getNumber(now.num), answer);
						continue;
					}
					if(i == 0 && now.num[j] == 0)
						continue;
					
					int[] next = now.num.clone();
					int temp = next[i];
					next[i] = next[j];
					next[j] = temp;
					
					Number n = new Number(next, now.cnt + 1);
					if(visit.contains(n))
						continue;
					
					visit.add(n);
					q.offer(n);
				}
			}

그리고 N이 1111처럼 같은 값을 가진다면, 여러번 숫자를 교환해봐도 visit에는 하나의 1111만 포함될 것이다.

그 하나의 1111은 가장 처음으로 큐에 삽입한, 교환횟수가 0인 Number의 객체이기 때문에

answer는 K가 짝수인 경우에만 갱신된다.

만약 K가 홀수라면, 1111을 홀수번 바꾸어도 1111번이기 때문에 answer는 1111이지만, 

answer를 갱신하는 if문에 들어가지 못하기 때문에 answer는 -1이 된다.

 

이를 방지하지 위해 교환하려는 숫자 arr[i], arr[j]가 같은 값이라면 그 arr값을 answer에 바로 갱신해준다.

같은 값끼리 교환하면 몇번을 교환해도(짝수번이든 홀수번이든) 그 배열의 값이 되기 때문이다.

(46824 처럼 일부가 같은 값인 경우도 해당)

 

 

 

마지막으로 큐에서 꺼낸 Number 객체의 교환횟수가 K와 같다면, 

그 객체의 값을 더 교환해도 answer가 갱신되지 않으므로 (교환횟수가 K + 1이 되기 때문에) 

continue 해줘서 무한루프가 되는일을 방지한다.

 

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
	static int N, M, K;
	static int[] arr;
	static HashSet<Number> visit;
	static int answer = -1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		String temp = st.nextToken();
		M = temp.length();
		N = Integer.parseInt(temp);
		K = Integer.parseInt(st.nextToken());
		
		arr = new int[M];
		for(int i=0;i<M;i++) 
			arr[i] = temp.charAt(i) - '0';
		
		if(M == 1 || M == 2 && N % 10 == 0) {
			System.out.println(-1);
			return;
		}
		visit = new HashSet<>();

		BFS();
		System.out.println(answer);
	}

	static void BFS() {
		Queue<Number> q = new LinkedList<>();

		Number start = new Number(arr, 0);
		visit.add(start);
		q.offer(start);

		while(!q.isEmpty()) {
			Number now = q.poll();

			if(now.cnt % 2 == K % 2) {
				answer = Math.max(getNumber(now.num), answer);
			}

			if(now.cnt + 1 > K)
				continue;
			
			for(int i=0;i<M;i++) {
				for(int j=i+1;j<M;j++) {
					if(now.num[i] == now.num[j]) {
						answer = Math.max(getNumber(now.num), answer);
						continue;
					}
					if(i == 0 && now.num[j] == 0)
						continue;
					
					int[] next = now.num.clone();
					int temp = next[i];
					next[i] = next[j];
					next[j] = temp;
					
					Number n = new Number(next, now.cnt + 1);
					if(visit.contains(n))
						continue;
					
					visit.add(n);
					q.offer(n);
				}
			}
		}
	}
	
	static int getNumber(int[] a) {
		int ret = a[0];
		
		for(int i=1;i<M;i++) {
			ret *= 10;
			ret += a[i];
		}
		
		return ret;
	}

	static class Number {
		int[] num;
		int cnt;

		Number(int[] num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}
		
		@Override 
		public boolean equals(Object o) {
			Number n = (Number)o;
			return Arrays.equals(this.num, n.num);
		}
		
		@Override
		public int hashCode() {
			return ("").hashCode(); // 배열 값을 비교해야 하므로 hashcode는 모두 같은 값을 가지도록 함
		}
	}

}