[BOJ] 1759 암호 만들기

1759번: 암호 만들기 (acmicpc.net)

오랜만에 다시 알고리즘 문제를 푸려니까 생각보다 잘 풀리지 않았다.

핵심아이디어는 모음인 경우를 조합안에서 판별하여 모음카운트와 자음카운트를 각각 더해주었다.
기존 조합의 cnt 를 cntv 와 cntc 로 분리하였다고 생각하면 될 것 같다.

조합 알고리즘을 거의 까먹은 덕에, 다시 조합, 순열 예전에 정리했던 코드를 보고 복습했다.
처음에 콤비네이션을 할땐 몰랐는데, 이제 보니깐 콤비네이션 함수에 백트래킹이 들어가 있었던 것 같다.

배열대신 스트링빌더를 이용해서 배열처럼 사용하는 방법도 있을 것 같은데 추가적으로 시도해봐야 겠다.

문제풀면서 주의해야했던 점은 조합을 하기위해선 원소가 정렬된 상태여야 한다.

package _0316;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1759Secret {
	private static int L;
	private static int C;
	private static String vowel = "aeiou";
	private static char[] map;
	private static char[] chars;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[C];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < C; i++) {
			map[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(map);
		chars = new char[L];
		comb(0,0,0);
	}
	//count c== 자음 countv == 모음 
	private static void comb(int start, int countc, int countv) {
		if(countc+countv == L) {
			if(countc >=2 && countv >=1) {
				for (int i = 0; i < chars.length; i++) {
					System.out.print(chars[i]);
				}
				System.out.println();
				return;
			}
			return;
		}
		for (int i = start; i < C; i++) {
			chars[countc+countv]=map[i];
			if(vowel.contains(Character.toString(map[i]))){
				comb(i+1, countc, countv+1);
			}else {
				comb(i+1, countc+1, countv);
			}
		}
	}
}

StringBuilder로 다시 풀어보았다. 로직은 동일하며 배열이 들어가는 부분 대신 StringBuilder를 사용했다.

package com.algo.boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1759SecretStringBuilder {
	private static int L;
	private static int C;
	private static String vowel = "aeiou";
	private static StringBuilder sb = new StringBuilder();
	private static char[] map;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[C];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < C; i++) {
			map[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(map);
		comb(0,0,0);
	}
	//count c== 자음 countv == 모음 
	private static void comb(int start, int countc, int countv) {
		if(countc+countv == L) {
			if(countc >=2 && countv >=1) {
				sb.setLength(L);
				System.out.println(sb);
				return;
			}
			return;
		}
		for (int i = start; i < C; i++) {
			sb.insert(countc+countv, map[i]);
			if(vowel.contains(Character.toString(map[i]))){
				comb(i+1, countc, countv+1);
			}else {
				comb(i+1, countc+1, countv);
			}
		}
	}
}

확실히 배열에 집어넣고 for문으로 이어붙여 출력하는것보다 빠르다.