[프로그래머스 / Java] 코딩테스트 연습: 모음사전 (완전탐색)

난이도: Level 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

---

 

A, E, I, O, U를 저장할 char 타입의 배열과 2차원 visited 배열을 사용하여 백트래킹으로 풀면 생각보다 쉽게 풀린다.

백트래킹이라는 문제를 알면서도 A E I O U를 배열로 저장할 생각을 못하고 Map으로 visited 여부 체크를 하려고 해서 시간이 생각보다 꽤 걸렸다.

 

우선 전역에서 사용할 변수로 다음과 같이 선언한다.

위에서 말했듯이 모음('A', 'E', 'I', 'O', 'U')을 모아놓은 vowels 배열과 2차원 visited 배열을 선언한다.

예를 들어 visited[0][3]라면, 0번째 자릿수의 vowels 배열의 3번째 모음의 방문 여부를 체크하는 것이다.

0번째 자릿수는 단어의 가장 첫번째 자릿수이고, vowels 배열의 3번째 모음은 vowels[3] = 'O'이다.

즉, visited[0][3]이 false라면 첫번째 자리는 'O'로 정해진다.

found 변수는 주어진 단어를 찾게 되면 true로 바꾸고, dfs 메서드의 for문에서 break를 해서 dfs 메서드를 더 탐색할 필요 없이 종료시키게 하는 변수이다.

 

    class Solution {

        int answer = 0;     // 주어진 단어의 사전에 위치한 순서

        char[] vowels = {'A', 'E', 'I', 'O', 'U'};  // 모음 배열

        boolean[][] visited;    // 각 자리별 모음의 사용 체크 배열

        boolean found = false;  // 주어진 단어 발견 여부

 

 

메인 solution 메서드는 3줄로 매우 짧다.

주요 로직은 dfs 메서드에서 구현했기 때문이다.

visited 배열의 크기를 행 5개, 열 5개로 초기화한 이유는 단어는 최대 5자리이고, 모음은 5개이기 때문이다.

0~4번째 자릿수에서 각각 5가지 모음('A', 'E', 'I', 'O', 'U')을 모두 사용 여부를 체크해야 한다.

 

dfs 메서드의 매개변수는 다음과 같다.

target: solution 메서드의 매개변수로 주어진 단어 (word)

now: 호출할 메서드에서 사용할 현재 단어("")

depth: 호출할 메서드에서 구할 모음의 자릿수 (0)

dfs 메서드가 끝난 후 주어진 단어(word)의 사전이 몇번째 자리인지를 최종적으로 리턴하면 된다.

 

    public int solution(String word) {

        visited = new boolean[5][5];    // 단어: 5자리, 모음의 수: 5개

        // now: 호출할 메서드에서 사용할 현재 단어 ("")

        // depth: 호출할 메서드에서 구할 모음의 자릿수 (0)

        dfs(word, "", 0);   // 0번째 자리부터 단어를 찾는 dfs 수행

        return answer;  // 주어진 단어의 사전에 위치한 순서 리턴

    }

 

 

dfs 메서드의 매개변수로 받은 현재 단어(now)가 문제에 주어진 단어(target)과 같다면 주어진 단어를 발견한 것이므로 found 변수를 true로 변경하고 메서드를 종료시킨다.

그리고 현재 자릿수 depth가 5이면 0 ~ 4번째 자릿수를 모두 탐색한 것이므로 더 탐색하면 단어의 길이가 길어지기 때문에 메서드를 종료시킨 후, 다시 돌아가서 depth - 1번째 자릿수의 모음을 찾으러 간다.

 

for문으로 depth번째 자릿수의 vowel 배열의 i번째 모음 사용 여부를 판단하고, 사용하지 않았다면 i번째 모음을 사용하고 다음 depth + 1번째 자릿수로 넘어가서 모음을 찾는다.

예를 들어 depth = 0, i = 3일 때, visited[depth][i]는 visited[0][3]이 된다.

visited[0][3]라면, 0번째 자릿수의 vowels 배열의 3번째 모음의 방문 여부를 체크하는 것이다.

vowels = {'A', 'E', 'I', 'O', 'U'}

0번째 자릿수는 단어의 가장 첫번째 자릿수이고, vowels 배열의 3번째 모음은 vowels[3] = 'O'이다.

즉, visited[0][3]이 false라면 첫번째 자리는 'O'로 정해진다.

모음을 정했으면 answer 전역 변수를 1 증가시킨다.

 

    public void dfs(String target, String now, int depth) {

        // 현재 단어가 주어진 단어와 같다면

        if (now.equals(target)) {  

            found = true;   // 주어진 단어 발견 여부를 true로 변경

            return;         // 단어를 발견했으므로 메서드 종료

        }

       

        // 유효 자릿수는 0 ~ 4까지인데, 자릿수가 5라면 더이상 탐색하면 안됨

        // 메서드 종료 후 depth - 1번째 자릿수의 모음을 찾으러 가기

        if (depth == 5) return;

       

        // vowels 배열에 위치한 모음('A', 'E', 'I', 'O', 'U')을 모두 탐색

        for (int i = 0; i < 5; i++) {

            if (found) break;   // 주어진 단어를 발견했다면 더이상 탐색 종료

           

            // depth번째 자릿수의 i번째 모음을 사용하지 않았다면

            if (!visited[depth][i]) {

                visited[depth][i] = true;   // 해당 모음을 사용 체크

                answer++;   // 사전에 위치한 순서(발견 순서) 1 증가

                // now: 호출할 메서드에서 사용할 현재 단어 (now + vowels[i])

                // depth: 호출할 메서드에서 구할 모음의 자릿수 (depth + 1)

                dfs(target, now + vowels[i], depth + 1);

                visited[depth][i] = false;  // 해당 모음을 사용 해제

            }

        }

    }

 

 

과정

answer = 0   // 전역 변수

target = "AAAE"

now = "", depth = 0, i = 0
visited[depth][i] = visited[0][0] = true
now + vowels[i] = now + vowels[0] = "" + 'A' = "A"
answer++ // answer = 1

now = "A", depth = 1, i = 0
visited[depth][i] = visited[1][0] = true
now + vowels[i] =  now + vowels[0] = "A" + 'A' = "AA"
answer++ // answer = 2

now = "AA", depth = 2, i = 0
visited[depth][i] = visited[2][0] = true
now + vowels[i] =  now + vowels[0] = "AA" + 'A' = "AAA"
answer++ // answer = 3

now = "AAA", depth = 3, i = 0
visited[depth][i] = visited[3][0] = true
now + vowels[i] =  now + vowels[0] = "AAA" + 'A' = "AAAA"
answer++ // answer = 4

// 돌아온 뒤 false로 변경

// i를 1로 증가시키고 주황색으로 가기(아래에 있음)

visited[depth][i] = visited[3][0] = false

now = "AAAA", depth = 4, i = 0
visited[depth][i] = visited[4][0] = true
now + vowels[i] =  now + vowels[0] = "AAAA" + 'A' = "AAAAA"
answer++ // answer = 5

// 돌아온 뒤 false로 변경

// i를 1로 증가시키고 보라색으로 가기(아래에 있음)
visited[depth][i] = visited[4][0] = false

now = "AAAAA", depth = 5
return     // 메서드 종료 후 이 메서드를 호출한 파란색으로 돌아감(위에 있음)

now = "AAAA", depth = 4, i = 1
visited[depth][i] = visited[4][1] = true
now + vowels[i] =  now + vowels[1] = "AAAA" + 'E' = "AAAAE"
answer++ // answer = 6

// 돌아온 뒤 false로 변경

// i를 2로 증가시키고 (생략)으로 가기(아래에 있음)
visited[depth][i] = visited[4][1] = false

now = "AAAAE", depth = 5
return    // 메서드 종료 후 이 메서드를 호출한 보라색으로 돌아감(위에 있음)

----------(생략)-----------

now = "AAAA", depth = 4, i = 4
visited[depth][i] = visited[4][4] = true
now + vowels[i] =  now + vowels[0] = "AAAA" + 'U' = "AAAAU"
answer++ // answer = 9

// 돌아온 뒤 false로 변경

// i를 5로 증가시키면 for문이 끝났으므로 메서드 종료 후 이 메서드를 호출한 갈색으로 돌아감(위에 있음)
visited[depth][i] = visited[4][4] = false

now = "AAAAU", depth = 5
return     // 메서드 종료 후 이 메서드를 호출한  초록색으로 돌아감(위에 있음)

now = "AAA", depth = 3, i = 1
visited[depth][i] = visited[3][1] = true
now + vowels[i] =  now + vowels[1] = "AAA" + 'E' = "AAAE"
answer++ // answer = 10

now = "AAAE", depth = 4
now.equals(target) = "AAAE".equals("AAAE")    // 단어를 찾음

found = false
return     // 메서드 종료 후 for문 break 후 최종 answer = 10을 메인 solution 메서드에서 리턴

최종 answer = 10

---

전체 코드

import java.util.*;
 
class Solution {
    int answer = 0;     // 주어진 단어의 사전에 위치한 순서
    char[] vowels = {'A', 'E', 'I', 'O', 'U'};  // 모음 배열
    boolean[][] visited;    // 각 자리별 모음의 사용 체크 배열
    boolean found = false;  // 주어진 단어 발견 여부
    
    public int solution(String word) {
        visited = new boolean[5][5];    // 단어: 5자리, 모음의 수: 5개
        // now: 호출할 메서드에서 사용할 현재 단어 ("")
        // depth: 호출할 메서드에서 구할 모음의 자릿수 (0)
        dfs(word, "", 0);   // 0번째 자리부터 단어를 찾는 dfs 수행
        return answer;  // 주어진 단어의 사전에 위치한 순서 리턴
    }
    
    public void dfs(String target, String now, int depth) {
        // 현재 단어가 주어진 단어와 같다면
        if (now.equals(target)) {   
            found = true;   // 주어진 단어 발견 여부를 true로 변경
            return;         // 단어를 발견했으므로 메서드 종료
        }
        
        // 유효 자릿수는 0 ~ 4까지인데, 자릿수가 5라면 더이상 탐색하면 안됨
        // 메서드 종료 후 depth - 1번째 자릿수의 모음을 찾으러 가기
        if (depth == 5) return;
        
        // vowels 배열에 위치한 모음('A', 'E', 'I', 'O', 'U')을 모두 탐색
        for (int i = 0; i < 5; i++) {
            if (found) break;   // 주어진 단어를 발견했다면 더이상 탐색 종료
            
            // depth번째 자릿수의 i번째 모음을 사용하지 않았다면
            if (!visited[depth][i]) {
                visited[depth][i] = true;   // 해당 모음을 사용 체크
                answer++;   // 사전에 위치한 순서(발견 순서) 1 증가
                // now: 호출할 메서드에서 사용할 현재 단어 (now + vowels[i])
                // depth: 호출할 메서드에서 구할 모음의 자릿수 (depth + 1)
                dfs(target, now + vowels[i], depth + 1);
                visited[depth][i] = false;  // 해당 모음을 사용 해제
            }
        }
    }
}

 

코드에서는 매개변수로 String을 사용했지만, 성능 향상을 위해서는 StringBuilder로 사용하는 것이 더 좋다.

String은 불변 객체이기 때문에 + 연산을 수행하면 원래 문자열은 버리고 새로운 문자열을 다시 할당받는 시간이 추가로 걸리게 된다.

반면 StringBuilder는 가변 객체이기 때문에 append() 메서드를 사용하면 원래 문자열 바로 뒤에 매개변수로 주어진 문자열이 붙어서 새로운 문자열로 변하게 되기 때문에 시간이 덜 걸리게 된다.