경우의 수 출력하기

오랜만의 간단한 알고리즘 문제를 가지고 돌아왔습니다!!

문제)

두개의 수를 입력받는다

첫번째 입력 K에는 K의 수만큼 a를 출력하고

두번째 입력 N에는 N의 수만큼 b를 출력하는데 규칙이 존재한다.

a와 b의 우선순위에서는 ab의 순서로 출력이 되며 각각의 나올수 있는 경우의 모든 수를 출력한다.

예시)

입력
- K : 2, N : 2
출력
  aabb
  abab
  abba
  baab
  baba
  bbaa

입력
- K : 3,  N : 2
출력
  aaabb
  aabab
  aabba
  abaab
  ababa
  abbaa
  baaab
  baaba
  babaa
  bbaaa

설명 

먼저 K의 수만큼 a가 출력 되고 N의 수만큼 b가 출력됩니다.

a와b가 출력 될수있는 모든 경우의 수가 출력이 되는데

a와b의 우선순위는 a>b이기때문에 a부터 순서대로 b까지 출력이 됩니다.

어떻게 풀어야 할지 감이 오셨나요?

K가 1이고 N이 1이라면

ab, ba 이런 식으로 출력이 되겠지요

조건 분기를 생각해보면 매우 간단히 문제가 풀립니다.

2,2를 예시로 들어보겠습니다.

먼저 맨 처음으로 a가 출력된뒤 나올수있는 경우의 수는 a,b입니다 ( a + (a ? b) + ~~~ 이런 순서가 되겠지요)

a가 우선순위로 먼저이기때문에 a다음 k만큼 반복한뒤 k의 수만큼 끝난다면 그때부터는 처음 조건 분기로 돌아와서 N의수만큼 b를 출력하면 됩니다.

말이 어려웠을것 같은데 즉 재귀를 이용하면 매우 간단히 문제가 풀립니다.

밑의 코드를 통해 보시면 되실것 같습니다.

import java.util.Scanner;

public class Main {

    static void restart(String t, int number1, int number2) {

        if (0 < number1) {
            restart(t + "a", number1 - 1, number2);
        }
        if (0 < number2) {
            restart(t + "b", number1, number2 - 1);
        }
        if (number1 == 0 && number2 == 0) {
            System.out.println(t);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number1 = scanner.nextInt();
        int number2 = scanner.nextInt();
        restart("", number1, number2);
    }
}

정말 간단하게 풀리지 않나요?

이렇게 재귀를 이용하면 매우 간단하게 풀리지만

알고리즘으로는 좋지 않다고 생각합니다.

왜냐하면 재귀를 사용하는 만큼 시간은 그만큼 오래걸리기 때문이죠 이런 부분은 점차 공부를 더 해봐야겠습니다.