찰떡개발자 코딩

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

풀이 : 

암호 조합을 만든다는걸 보고, 조합 백트래킹 공부했던것이 생각났다.

처음에 System.out.print로 하나씩 출력했는데 이상하게 계속 틀렸습니다가 떴엇다.. 답은 맞는데...

뭐가 문제지 다시 봐도 봐도 모르겠었다..

결국 혹시나 해서 StringBuilder로 만들어서 한번에 출력했더니 성공했다.. 뭐지..

중요한점

1). 사전순으로 나와야한다. => Arrays.sort를 활용

2). 모음은 1개 이상 자음은 2개이상이다. => 조건 활용

3). 재귀를 통해 조합을 만든다.

static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		sb = new StringBuilder();
		int cnt = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		String[] arr = new String[m];
		int idx = 0;
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens()) {
			arr[idx++]=st.nextToken();
		}

		Arrays.sort(arr);
		boolean[] visit = new boolean[m];
		combination(arr,visit,0,cnt);
		System.out.println(sb);
	}

	static void combination(String[] arr, boolean[] visit, int start, int cnt) {
		//재귀 종료 => 1개의 조합이 끝났을때
		if(cnt == 0) {
			print(arr,visit);
			return;
		}

		for (int i = start; i <arr.length; i++) {
			visit[i] = true;
			combination(arr,visit,i+1,cnt-1);
			visit[i] = false;
		}
	}

	static void print(String[] arr, boolean[] visit) {
		String result="";
		int ja =0;
		int mo =0;
		for (int i = 0; i < arr.length; i++) {
			if(visit[i]) {
				result+=arr[i];
				if(arr[i].equals("a")||arr[i].equals("e")||arr[i].equals("i")||arr[i].equals("o")||arr[i].equals("u")) {
					mo++;
				}else {
					ja++;
				}
			}
		}
		if(mo>=1 && ja>=2) {
			sb.append(result);
			sb.append("\n");
		}
	}

오늘도 화이팅