Baekjoon 1759 암호 만들기 - BackTracking

더 깔끔한 노션을 원한다면

Baekjoon 1759 암호 만들기 - BackTracking

1759번: 암호 만들기

1. input

char[] password = new char[L];
visit = new boolean[C];
charArr = new char[C];
String[] strArr = br.readLine().split(" ");
for (int i = 0; i < C; i++) {
  charArr[i] = strArr[i].charAt(0);
}
Arrays.sort(charArr);

공백으로 구분되어 문자들이 입력되므로 split을 사용하여 입력받았다.

암호를 오름차순으로 출력해줘야 하기 때문에 charArr를 정렬해준다.

백트래킹

/**
 * password : 암호
 * vowelCount : 모음의 개수
 * index : 암호의 길이
 * sequence : 오름차순이여야 하므로 전 암호문자의 인덱스 위치
*/
private void backTracking(char[] password, int vowelCount, int index, int sequence) {
  if (index == L) {
    if (index - vowelCount >= 2 && vowelCount >= 1) {
      sb.append(password);
      sb.append("\n");
    }
    return;
  }
  for (int i = sequence; i < C; i++) {
    if (visit[i]) {
      continue;
    }
    int val = 0;
    for (int v = 0; v < 5; v++) {
      if (vowels[v] == charArr[i]) {
        val++;
        break;
      }
    }
    password[index] = charArr[i];
    visit[i] = true;
    backTracking(password, vowelCount + val, index + 1, i);
    visit[i] = false;
  }
}

이미 사용했던 값은 중복되면 안되므로 visit을 설정해준다.

backTracking이 종료되면 visit을 false로 바꿔주는게 포인트!

암호에 부합하는가

모음의 개수가 1 이상, 자음의 개수가 2 이상인지 확인해준다.

if (index == L) {
  if (index - vowelCount >= 2 && vowelCount >= 1) {
    sb.append(password);
    sb.append("\n");
  }
  return;
}

암호에 부합하면 sb에 넣어준다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    Baekjoon solution = new Baekjoon();
    solution.P1759();
  }
}

class Baekjoon {
  char[] charArr;
  boolean[] visit;
  char[] vowels = { 'a', 'e', 'i', 'o', 'u' };
  int L, C;
  StringBuilder sb = new StringBuilder();

  public void P1759() 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());
    char[] password = new char[L];
    visit = new boolean[C];
    charArr = new char[C];
    String[] strArr = br.readLine().split(" ");
    for (int i = 0; i < C; i++) {
      charArr[i] = strArr[i].charAt(0);
    }
    Arrays.sort(charArr); // ※1
    for (int i = 0; i <= C - L; i++) {
      visit[i] = true;
      int vowelCount = 0;
      for (int v = 0; v < 5; v++) {
        if (vowels[v] == charArr[i]) {
          vowelCount = 1;
          break;
        }
      }
      password[0] = charArr[i];
      backTracking(password, vowelCount, 1, i);
      visit[i] = false;
    }
    System.out.println(sb.toString());
  }

  private void backTracking(char[] password, int vowelCount, int index, int sequence) {
    if (index == L) {
      if (index - vowelCount >= 2 && vowelCount >= 1) {
        sb.append(password);
        sb.append("\n");
      }
      return;
    }
    for (int i = sequence; i < C; i++) {
      if (visit[i])
        continue;
      int val = 0;
      for (int v = 0; v < 5; v++) {
        if (vowels[v] == charArr[i]) {
          val++;
          break;
        }
      }
      password[index] = charArr[i];
      visit[i] = true;
      backTracking(password, vowelCount + val, index + 1, i);
      visit[i] = false;
    }
  }

}