[PS] 99클럽 코테 스터디 16일차 TIL (모음사전)

문제

문제 링크

설명

알파벳 모음 5개로 만들 수 있는 모든 조합에서 특정 단어가 몇번째 인덱스에 있는지 반환하면 된다.

풀이

단순하게 단어 하나로 만들 수 있는 조합부터 단어 다섯개의 조합까지 모두 계산해 배열에 담고, 배열을 사전순으로 정렬한다. 그 후 찾고자 하는 단어의 인덱스를 반환한다.

class Solution {
  public int solution(String word) {
    int answer = 0;
    String[] alphabet = {"A", "E", "I", "O", "U"};

    String[] all =
      new String[(int) (5 + Math.pow(5, 2) + Math.pow(5, 3) + Math.pow(5, 4) + Math.pow(5, 5))];

    int index = 0;

    for (int i = 0; i < 5; i++) {
      all[index++] = alphabet[i];
    }

    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        all[index++] = alphabet[i] + alphabet[j];
      }
    }

    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        for (int k = 0; k < 5; k++) {
          all[index++] = alphabet[i] + alphabet[j] + alphabet[k];
        }
      }
    }

    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        for (int k = 0; k < 5; k++) {
          for (int l = 0; l < 5; l++) {
            all[index++] = alphabet[i] + alphabet[j] + alphabet[k] + alphabet[l];
          }
        }
      }
    }

    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        for (int k = 0; k < 5; k++) {
          for (int l = 0; l < 5; l++) {
            for (int m = 0; m < 5; m++) {
              all[index++] = alphabet[i] + alphabet[j] + alphabet[k] + alphabet[l] + alphabet[m];
            }
          }
        }
      }
    }

    Arrays.sort(all);
    for (int i = 0; i < all.length; i++) {
      if (all[i].equals(word)) {
        answer = i + 1;
        break;
      }
    }

    return answer;
  }
}

이렇게 풀어도 통과를 하긴 하는데 시간과 메모리 사용이 많다.

풀이 (dfs)

위 과정은 결국 "A", "E", "I," "O", "U" 를 계속해서 덧붙여 나간다는 것을 알 수 있다. 처음 “” 빈 문자열에서 출발해 길이가 5가 될 때 까지 모음 배열을 순회하면서 이전 문자열에 덧붙이는 과정을 재귀함수로 구현한다.

all =
[A, E, I, O, U, 
AA, AE, AI, AO, AU, 
EA, EE, EI, EO, EU, 
IA, IE, II, IO, IU, 
OA, OE, OI, OO, OU,
UA, UE, UI, UO, UU,
AAA, AAE, AAI, AAO, AAU,
AEA, AEE, AEI, AEO, AEU,
AIA, AIE, AII, AIO, AIU,
  ...
]

import java.util.*;

class Solution {
  static String[] alphabet = {"A", "E", "I", "O", "U"};
  static String[] all =
    new String[(int) (5 + Math.pow(5, 2) + Math.pow(5, 3) + Math.pow(5, 4) + Math.pow(5, 5))];
  static int index = 0;

  public int solution(String word) {
    for (int i = 1; i <= 5; i++) {
      dfs("", i, 0);
    }

    Arrays.sort(all);
    return Arrays.binarySearch(all, word) + 1;
  }

  static void dfs(String word, int length, int depth) {
    if (depth == length) {
      all[index++] = word;
      return;
    }
    for (String a : alphabet) {
      dfs(word + a, length, depth + 1);
    }
  }
}