[프로그래머스] Lv. 2 모음사전(Java)

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=java

프로그래머스

 

정답 코드 : 성능 개선 전 - 완전 탐색 (백트래킹)

import java.util.*;

class Solution {
    
    private static final int WORD_LENGTH_LIMIT = 5;
    private static final char[] CHARS = "AEIOU".toCharArray();
    
    public int solution(final String word) {
        return generate("").indexOf(word);
    }
    
    private List<String> generate(final String word) {
        final List<String> words = new ArrayList<>();
        words.add(word);
        
        if (word.length() == WORD_LENGTH_LIMIT) {
            return words;
        }
        
        for (char c : CHARS) {
            words.addAll(generate(word + c));
        }
        
        return words;
    }
    
}

 

실행 결과 : 성능 개선 전 - 완전 탐색 (백트래킹)

 

설명

이 문제를 해결하는 방법은 크게 두 가지이다.

 

• 완전 탐색 (Brute Force)
  가능한 모든 단어를 생성하여 리스트에 저장한 후, 해당 단어의 인덱스를 찾는 방법.
  사전 순서대로 단어를 생성하는 것이 중요하다.
• 수학적 접근 (위치 계산)
  각 자리의 가중치를 활용하여 직접 인덱스를 계산하는 방법.
  리스트를 사용하지 않고 O(1) 연산으로 해결이 가능하다.

 

완전 탐색 (백트래킹)

우선, 가능한 모든 단어를 만들어 리스트에 저장한 후, 주어진 단어의 인텍스를 찾는 방법을 구현한다.

 

구현 방법
1. 재귀 함수를 이용하여 가능한 모든 단어를 생성한다.
2. 생성된 단어들을 ArrayList<String>에 저장한다.
3. indexOf(word)를 호출하여 몇 번째 단어인지 찾는다.

 

그러나, 리스트를 계속 생성하고 병합하는 과정은 큰 성능 손실을 발생시킨다.

 

정적 캐싱과 해시맵을 활용한 최적화

위 문제를 해결하기 위해 정적 캐싱을 활용한 HashMap<String, Integer>로 탐색 속도를 개선할 수 있다.

 

구현 방법
1. 모든 단어를 미리 생성하면서 HashMap<String, Integer>에 저장한다.

2. 이후, dictionary.get(word)를 호출하여 O(1) 시간 복잡도로 빠르게 인덱스를 찾는다.

 

이 방식은 불필요한 객체 생성이 없고, 탐색 속도가 훨씬 빨라진다.

 

정답 코드 : 성능 개선 후 - 해시맵을 활용한 최적화

import java.util.*;

class Solution {
    
    private static final int WORD_LENGTH_LIMIT = 5;
    private static final char[] CHARS = "AEIOU".toCharArray();
    private static final Map<String, Integer> dictionary = new HashMap<>();
    
    static {
        generate("", 0);
    }
    
    public int solution(final String word) {
        return dictionary.get(word);
    }
    
    private static void generate(final String word, final int index) {
        dictionary.put(word, index);
        
        if (word.length() == WORD_LENGTH_LIMIT) return;
        
        for (char c : CHARS) {
            generate(word + c, dictionary.size());
        }
    }
    
}

 

실행결과 : 성능 개선 후 - 해시맵을 활용한 최적화

 

마무리

처음 문제를 접했을 때, 단순하게 모든 단어를 리스트에 저장하고 탐색하는 방식을 떠올렸다.

 

그러나 테스트 케이스를 돌려보면서 성능이 점점 나빠지는걸 보면서 "뭔가 잘못됐다" 라는 생각이 들었다.

 

처음에 "백트래킹을 활용했으니 최적의 풀이겠지?"라고 생각했지만,

실제로는 리스트를 계속 생성하고 병합하는 과정이 엄청난 비효율을 초래하고 있었다.

 

그래서 "이걸 더 빠르게 최적화할 방법이 없을까?" 고민하다가

→ 해시맵과 static를 활용한 정적 캐싱을 떠올렸다.

 

이 과정에서 리스트를 무조건적으로 사용하기보다, 탐색과 저장 방식까지 고려하는 것이 중요하다는 점을 깨달았다.

 

또한, 단순히 문제를 풀고 끝내는 것이 아니라

"왜 이 방식이 느릴까?", "다른 방법은 없는가?" 고민 해보는 과정이

문제 해결에서 가장 중요한 부분이라는 걸 다시금 체감한 경험이었다.

 

참고 자료 :

취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략 : 자바 편 | 김현이

프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편 | 김현이 - 교보문고