[프로그래머스] 모음사전 (JAVA)

소요시간

10분이 안걸렸다.
문제 자체가 쉬웠기 때문에 백트래킹에 대한 이해만 있다면 누구나 풀 수 있다.

사용한 자료구조 및 알고리즘

백트래킹의 문제다. DFS를 사용했다. 그리고 찾을 때마다 값을 추가해줘야 하므로 ArrayList 를 사용했다.

풀이과정

1. 백트래킹을 통해 단어를 탐색할 때마다 list에 추가. 이때 depth가 1이던, 5이던 추가해줘야 하므로 무조건 추가함.
2. A, AA, AAA 등 중복된 값이 계속 나올수 있으므로 visited 배열을 선언하지 않았음.
3. depth가 5가 되었다면 우선 List에 추가하고 return 함으로써 depth가 6인 경우는 탐색하지 않음.
4. 백트래킹이 끝나면 list에 추가된 단어들을 정렬함

• 1가지 예외
  지금 코드를 봤을 때 "A" 뿐만 아니라 "" 의 공백도 추가되는 코드이다. 여기서 정렬을 헀을 때 0번째 인덱스에는 "" 가 오고, 1번째 인덱스에는 "A" 가 온다. 그러므로 "" (공백) 을 고려하여서 인덱스를 탐색해야 한다.

소스코드

import java.util.*;
class Solution {
	static ArrayList<String> list=new ArrayList<>();
	static char ch[]={'A','E','I','O','U'};

	public int solution(String word) {

		backtracking(0,"");
		Collections.sort(list);
		int index=0;
		for(int i=0;i<list.size();i++){
			if(list.get(i).equals(word)){
				index=i;
				break;
			}
		}
		return index;

	}
	public static void backtracking(int depth,String word){
		list.add(word);
		if(depth==5){
			return;
		}

		for(int i=0;i<ch.length;i++){
			backtracking(depth+1,word+ch[i]);
		}


	}

}

회고

백트래킹 문제가 많이 나오는 것 같다. 처음에 백트래킹을 배우면서 생소한 개념이라 익숙하지 않았는데 익숙해지고 나니 이만한 알고리즘이 없다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212