[BOJ_1759]암호 만들기 (골드 5) - JAVA

---

🐾 알고리즘

• 조합론과 백트래킹을 적절히 합쳐 생각하면 풀리는문제다.

---

🐾 생각 포인트

• 출력형식이 잘못되었다는 오류때문에 한참을 고민했다. 알고리즘 스터디원 덕분에 해결완료!! 
• 원래는 print함수를 아래와 같이 작성했었다.
  
  

private static void print(String[] arr, boolean[] visited) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            if (visited[i] && check(arr, visited)) {
                result.append(arr[i]);
            }
        }
        result.append("\n");
        System.out.print(result);
    }

 

이렇게 작성하면, 모든 경우의 수를 다돌면서 조건에 맞지 않는 경우는 출력을 하지 않고, 줄바꿈만 한다. 그래서 자음2개 이상, 모음 1개이상이 있어야 하는 조건을 충족하지 못하면 공백이 생기고 이로 인해 오류가 발생했던 것이다. ㅠㅠ

그래서 아래 소스코드와 같이 조건에 충족되지 않으면 return 시키기! 이 또한 백트래킹의 원리를 활용해 출력하는 거였던 것이다........  열심히 생각해야겠다.

---

🐾 소스코드

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

public class Main_1759 {
	static int L;
	static int C;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		String[] arr = new String[C];
		boolean[] visited;
		for (int i = 0; i < C; i++) {
			arr[i] = st.nextToken();
		}
		Arrays.sort(arr);
		// 6개중에 4개뽑기
		combination(arr, new boolean[C], 0, 0, L);

	}

	private static void combination(String[] arr, boolean[] visited, int start, int depth, int r) {
		// 기저조건
		if (depth == L) {
			print(arr, visited);
			return;
		}

		// 재귀조건
		for (int i = start; i < arr.length; i++) {
			if (!visited[i]) {
				visited[i] = true;
				combination(arr, visited, i + 1, depth + 1, r);
				visited[i] = false;
			}
		}

	}

	private static void print(String[] arr, boolean[] visited) {
        StringBuilder result = new StringBuilder();

        if (check(arr, visited)) {
        	//check 함수가 true : 자음모음개수 충족되면 출력
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    result.append(arr[i]);
                }
            }
        } else {
        	//자음모음개수가 충족되지 못하면 출력 불가능 
        	//아예 조건에 맞지 않기 때문에 리턴시키기..!
            return;
        }

        result.append("\n");
        System.out.print(result);

    }

	private static boolean check(String[] arr, boolean[] visited) {
		int cnt = 0;
		int cnt2 = 0;
		for (int i = 0; i < arr.length; i++) {
			if (visited[i]) {
				if (arr[i].contains("a") || arr[i].contains("i") || arr[i].contains("e") || arr[i].contains("u")
						|| arr[i].contains("o")) {
					cnt++;
				}else {
					cnt2++;
				}
			}

		}
		if (cnt >= 1 && cnt2>=2) {
			return true;
		}
		return false;
	}

}

---

😵‍💫 공부해야 할 점

• 진득하게 생각하기..
• 안되면 끝까지 잡고 해결하기,,
• 바로 물어보지 않기