[백준 JAVA] 15663번: N과 M (9) - 중복 입력 값 순열

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

 

if (i + 1 < n)

if(a[i+1] == a[i])

continue;

 

이전 문제와 다른게 중복되는 입력 값이 있다.

 

이 중복되는 입력 값을 다 출력하는 것이 아니고 같은 싸이클 즉 arr의 같은 자릿수에 있는 중복된 값을 제거해서 출력해야한다.

 

따라서 for문에서 a(입력받은 배열)의 맨 마지막 값이 아니고 다음 값과 현재 값이 같을 경우 continue를 통해 같은 숫자의 맨 마지막에서만 출력하게끔 설계 하였다. 

 

예제를 실행한 결과인데

4 2

9 7 9 1

1 7

1 9

7 1

7 9

9 1

9 7

 

나와야 하는 결과 값은

 

1 7

1 9

7 1

7 9

9 1

9 7

9 9

 

이렇게이다.

 

앞은 잘 나오고 있지만 9 9 라는 값은 나오고 있지 않다.

 

뭔가 값을 범위나 제한을 조금 바꿔주면 될꺼 같아서 계속 고민해 보았지만 애초에 케이스 하나를 더 출력하는것이 문제가 아니였다.

 

4 4

1 1 1 1

1 1 1 1 출력값이 나와야 하지만 나오지 않는다.

 

그 이유를 생각해 보았을 때 

dfs(0) 에서 for문 i는 0부터 3까지 돌았을때 0부터 2까지는 그 이후값이랑 같으므로 전부 continue해주고, i = 3값만 그 이후 값이 없으므로 처음 if문을 통과하여 두번째 if 문 visit[i]까지 도달하고 arr[0]째에 a[3]값을 넣어준다. 

 

여기까지는 괜찮은 데 문제는 다음에 일어난다.

 

dfs(1) 에서 똑같이 for문 i는 0부터 3까지 돌았을때 0부터 2까지는 그 이후값이랑 같으므로 전부 continue해주고, i = 3 값은 그다음 if문에 도달하지만 visit문에 걸려서 통과하게 된다.

 

문제 해결 방식이 잘못된거 같아서 hash를 사용할까하다가 다른 블로그를 참고해서 풀었다.

 

우선 dfs 에 

int before = 0; 변수를 하나 삽입해 준다.

그러고 이전에 쓴 문자를 다음 dfs에 넣지 않게 하기 위해 if(visit[i])를 해준 것 처럼 이전에 사용한 같은 문자를 같은 사이클(같은 dfs)에서 사용하지 않기 위해 이 변수도 dfs에 넣어주고 if (before != a[i])에 넣어준다. 그 이후로 문자를 사용한다면 이전에 사용한 문자는 before에 넣어준다.

 

전체 코드는 다음과 같다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static int n, m;
	public static int[] a;
	public static int[] arr;
	public static boolean[] visit;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		a = new int[n];
		arr = new int[m];
		visit = new boolean[n];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		Arrays.sort(a);

		dfs(0);
		System.out.println(sb);

	}

	public static void dfs(int depth) {
		if (depth == m) {
			for (int val : arr) {
				sb.append(val + " ");
			}
			sb.append('\n');
			return;
		}
		int before = 0;
		for (int i = 0; i < n; i++) {
			if (!visit[i]) {
				if (before != a[i]) {
					before = a[i];
					visit[i] = true;
					arr[depth] = a[i];
					dfs(depth + 1);
					visit[i] = false;
				}
			}
		}
	}
}