[BOJ - JAVA] 1759 - 암호 만들기

# 주소

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

1759번: 암호 만들기

 

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	static int n,m;
	static char ans[],arr[];
	static boolean visit[];
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt();
		m = scan.nextInt();
		arr = new char[m];
		visit = new boolean[m];
		for(int i=0;i<m;i++) {
			arr[i] = scan.next().charAt(0);
		}
		Arrays.sort(arr);
		ans = new char[m];
		dfs(0, 0);
	}
	static void dfs(int start,int depth) {
		if(depth==n) {
			int a = 0;
			int b = 0;
			StringBuilder sb = new StringBuilder();
				for(int i = 0; i < n; i++) {
					sb.append(ans[i]);
					
					if(ans[i]=='a'||ans[i]=='e'||ans[i]=='i'||ans[i]=='o'||ans[i]=='u') {
						a++;
					}else {
						b++;	
				}
			}
			if(a>=1 && b>=2) System.out.println(sb);
		
		}
		//백트래킹
		for(int i=start;i<m;i++) {
			if(!visit[i]) {
				visit[i]=true;
				ans[depth] = arr[i];
				dfs(i + 1,depth+1);
				visit[i]=false;
			}
		}
	}
}

지난 시간에 다루었던 백트래킹 문제입니다. 

문제를 잘 보시면 모음은 최소 1개 이상, 자음은 최소 2개 이상이 있어야 합니다.

처음엔 이걸 안보고 그냥 오름차순으로 정렬했다가 오답인 것을 보고 문제를 다시보고 깨닫았습니다.

이번에는 ans와 arr에 정수가 아닌, character타입의 입력값이 들어가기 때문에 char타입의 배열을 두 개 선언합니다.

n과 m을 입력받고 boolean 타입의 visit도 마찬가지로 선언합니다.

arr에는 입력 받는 문자들을 각각 저장합니다.

그리고 반드시 arr를 입력 받을 때 scan.next().charAt(0)이라고 해주서야 합니다.

이유는 String 타입으로 변환시켜 줘서 저장해야 하기 때문입니다!!

 

이 후 Arrays.sort(arr)로 arr를 정렬합니다. 

dfs로 넘어와서 시작점을 start로 두고 늘 그랬듯이 depth를 통해 n과 비교하여 출력하도록 합니다.

이후 int a,b를 0으로 초기화를 하는데, a와 b는 각각 모음과 자음의 개수입니다.

 

StringBuilder sb를 생성하고 ans를 sb에 append합니다. 

이후 ans가 a, e, i, u, o를 가지고 있을 때마다 a를 증가(모음), 아니면 b를 증가시키겠습니다.

이후 a가 1이상, b가 2이상일 때만 출력합니다.

 

그리고 가장 밑엔 이 문제의 핵심 알고리즘인 백트래킹입니다.

N과M시리즈에서 정말 많이 봤던 구문이죠??

여기선 마찬가지로 if(!visit[i])일 때

visit[i]를 true로 바꾸고 ans에 arr의 현재 인덱스값을 넣습니다.

그리고 dfs의 i값과 depth값을 1씩 증가시키고 visit[i]를 false로 바꾸면 이 문제가 정상적으로 출력되는 것을 확인하실 수있겠습니다. 

 

감사합니다.