[Programmers] 옹알이 (1)

lkdcode·2023년 10월 12일
Javaalgorithmprogrammers백트래킹

Algorithm

목록 보기
44/47
post-thumbnail

옹알이 (1)

문제 분석

조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다.

"aya", "ye", "woo", "ma" 4개의 문자열을 1번씩 사용하여
조합한 단어가 몇 개인지 갯수를 체크하여 리턴하는 문제.

풀이 과정

🎯 조합이 가능한 경우의 수, 백트래킹

조카가 발음을 할 수 있는 모든 경우의 수를 찾아보자.
주어진 네 가지의 발음을 각 최대 1번만 사용하여 조합을 한다면
"aya" + "ye" 도 가능하고
"ye" + "woo",
"woo" + "ye" + "aya",
"ma" + "ye" + "aya" + "woo"
... 등등 모두 가능하다.

발음할 수 있는 경우의 수를 백트래킹 을 이용하여 접근하려한다.


🎯 조합할 수 있는 경우의 수? 인덱스로 접근해보자면

int[] array = {0, 1, 2, 3};

숫자 배열이 있다.
각 숫자를 1번씩만 사용해서 조합할 수 있는 모든 경우의 수를 보자.
값과 인덱스가 같지만 인덱스로 이해하자.

0
0, 1
0, 2
0, 3
0, 1, 2
0, 1, 3
0, 2, 1
0, 2, 3
...(중략)
3, 1, 2, 0
3, 1, 0, 2
...(생략)

너무 많아서 생략한다.
0 이 첫 번째 자리면서 1, 2, 3 을 조합,
1 이 첫 번째 자리면서 0, 2, 3 을 조합하는 등
경우의 수가 많다.

중요한 건 중복되지 않으면서,
1번씩 사용하여 조합하는 모든 경우의 수이다.


🎯 경우의 수를 다시 보자.

경우의 수를 마구 열거하면 경우의 수의 패턴이 보이지 않는다.
다시 n의 자리 경우의 수 로 나열해 보자면 아래와 같다.

1의 자리 경우의 수
0
1
2
3

2의 자리 경우의 수
0, 1
0, 2
0, 3
1, 0
1, 2
1, 3
2, 0
2, 1
2, 3
...(생략)

3의 자리 경우의 수
0, 1, 2
0, 1, 3
0, 2, 1
0, 2, 3
...
3, 0, 1
3, 0, 2
...(생략)

중요한건 n의 자리 경우의 수를 바라보며 접근하여야 하는데,

for (int i = 0; i < array.length; i++) {
	backTracking(i);
}

이와 같이 0 부터 마지막 인덱스 까지 매개변수로 넘겨주며
i 를 n 으로 backTracking 탐색을 실시한다.


🎯 backTracking(1) - 방문 여부

boolean[] visited = new boolean[4];

재방문(재탐색)을 안 하기 위해 boolean[] 배열을 선언한 후
false 와 true 조건을 이용하여 탐색을 할 것이다.

방문 처리를 통해 조카의 네 가지 발음을 최대 한 번씩만 사용하게 할 것이다.

배열의 사이즈는 조카가 발음할 수 있는 단어 4개로 설정했다.
length 로 해도 무관하다.


🎯 backTracking(2) - backTracking(...매개변수...)

void backTracking(StringBuilder sb, int depth, int size) {...}

🚀 backTracking 을 위해서 StringBuilder, int depth, int size 가 필요하다.

  1. StringBuilder = index 를 연달아서 문자열로 만들어 사용할 것이다.
  • ex) "012" 👉 index 0, 1, 2 를 사용할 것이다.
  • "0" 👉 index 0 을 사용할 것이다.
  • "31" 👉 index 3, 1 을 사용할 것이다.
  • "0123" 👉 index 0, 1, 2, 3 을 사용할 것이다.

조합된 경우의 수에 사용할 인덱스를 붙여서 문자열로 사용할 예정이다.

🚀 int depth = 현재까지 조합된 경우의 수의 사이즈가 된다.

  • ex) "012" 👉 depth = 3
  • "0" 👉 depth = 1
  • "31" 👉 depth = 2
  • "0123" 👉 depth = 4

🚀 int size = n의 자리 경우의 수 가 된다. (재귀를 탈출할 베이스 조건이다.)

if (size == dpeth) return;
  • ex) 조카는 4개 의 단어를 한 번씩 조합한 단어는 말할 수 있다.
  • 이 중 3개 의 단어를 조합할 수 있는 경우의 수를 찾을 때, size = 3 이 된다.
  • 이 중 2개 의 단어를 조합할 수 있는 경우의 수를 찾을 때, size = 2 가 된다.
  • 이 중 1개 의 단어를 조합할 수 있는 경우의 수를 찾을 때, size = 1 이 된다.

size 와 depth 가 같다면 재귀를 탈출한다.
size 는 n 의 경우의 수에서 n 이다.


🎯 backTracking(3) - 핵심 로직

	backTracking(StringBuilder sb, int depth, int size) {
		
        ...
        for (int i = 0; i < 4; i++) {
1️⃣            if (!visited[i]) {
2️⃣                visited[i] = true;
3️⃣                backTracking(sb.append(i), depth + 1, size);
4️⃣                sb.deleteCharAt(sb.length() - 1);
5️⃣                visited[i] = false;
            }
        }
        ...
        
	}

예시를 통해 위의 코드를 하나씩 살펴보자.

🚀 ex) size 를 4 로, 시작 depth 는 항상 0 이다.

	backTracking(StringBuilder sb = "", int depth = 0, int size = 4) {
    ...
		for (int i = 0; i < 4; i++) {
1️⃣			if (!visited[i]) { ... }    
	    }
	...
    }

1️⃣. 0 은 탐색하지 않았으므로 if 조건문 실행.

	...
2️⃣		visited[i] = true;
3️⃣      backTracking(sb.append(i), depth + 1, size);
	...

2️⃣. 0 을 방문처리(true) 하고

3️⃣. backTracking() 재귀 호출.
   StringBuilder = "0" 이 된다.
   depth 는 1 이 된다.
   size 는 그대로 4 

>>2번째 호출<<
	...
        for (int i = 0; i < 4; i++) {
1️⃣            if (!visited[i]) {
2️⃣                visited[i] = true;
3️⃣                backTracking(sb.append(i), depth + 1, size);
	...

1️⃣. 0 은 탐색했으므로 if 조건문 패스.
1️⃣. 1 은 탐색하지 않았으므로 if 조건문 실행.
2️⃣. 1 을 방문처리(true) 하고,

3️⃣. backTracking() 재귀 호출.
   StringBuilder = "01" 이 된다.
   depth 는 2 가 된다.
   size 는 그대로 4 


>>3번째 호출<<
	...
        for (int i = 0; i < 4; i++) {
1️⃣            if (!visited[i]) {
2️⃣                visited[i] = true;
3️⃣                backTracking(sb.append(i), depth + 1, size);
	...

1️⃣. 0 은 탐색했으므로 if 조건문 패스.
1️⃣. 1 은 탐색했으므로 if 조건문 패스.
1️⃣. 2 는 탐색하지 않았으므로 if 조건문 실행.
2️⃣. 2 를 방문처리(true) 하고,

3️⃣. backTracking() 재귀 호출.
   StringBuilder = "012" 가 된다.
   depth 는 3 가 된다.
   size 는 그대로 4 


>>4번째 호출<<
	...
        for (int i = 0; i < 4; i++) {
1️⃣            if (!visited[i]) {
2️⃣                visited[i] = true;
3️⃣                backTracking(sb.append(i), depth + 1, size);
	...

1️⃣. 0 은 탐색했으므로 if 조건문 패스.
1️⃣. 1 은 탐색했으므로 if 조건문 패스.
1️⃣. 2 은 탐색했으므로 if 조건문 패스.
1️⃣. 3 은 탐색하지 않았으므로 if 조건문 실행.
2️⃣. 3 을 방문처리(true) 하고,

3️⃣. backTracking() 재귀 호출.
   StringBuilder = "0123" 이 된다.
   depth 는 4 가 된다.
   size 는 그대로 4 


>>5번째 호출<<
6️⃣		if (size == depth) return;
	...
        for (int i = 0; i < 4; i++) {
1️⃣            if (!visited[i]) {
2️⃣                visited[i] = true;
3️⃣                backTracking(sb.append(i), depth + 1, size);
	...

6️⃣. 재귀 탈출 조건인 size == depth 가 성립한다.
이때, StringBuilder 의 값은 "0123" 인데

이 문자열은 우리가 사용할 인덱스가 된다.
재귀 탈출을 하면서 StringBuilder 의 값을 자료구조에 추가해준다.

자료구조에 추가하는 로직은 아래에서 설명하고 backTracking() 로직을 이어가보자.

>>6번째 호출<<
	...
        for (int i = 0; i < 4; i++) {
1️⃣            if (!visited[i]) {
2️⃣                visited[i] = true;
3️⃣                backTracking(sb.append(i), depth + 1, size);
4️⃣                sb.deleteCharAt(sb.length() - 1);
5️⃣                visited[i] = false;
	...

4️⃣. StringBuilder 의 마지막 문자를 삭제해준다. "0123" 👉 "012"
5️⃣. 3 을 방문 해제처리(false) 한다.


>>7번째 호출<<
	...
        for (int i = 0; i < 4; i++) {
1️⃣            if (!visited[i]) {
2️⃣                visited[i] = true;
3️⃣                backTracking(sb.append(i), depth + 1, size);
4️⃣                sb.deleteCharAt(sb.length() - 1);
5️⃣                visited[i] = false;
	...

4️⃣. StringBuilder 의 마지막 문자를 삭제해준다. "012" 👉 "01"
   삭제하지 않고 문자열을 .append() 하게 되면 사이즈가 초과하기 때문이다.
5️⃣. 2 를 방문 해제처리(false) 한다.

현재 3 인덱스의 방문 여부를 보자.
6번째 호출에서 방문을 해제했다. 다음 for 문을 돌 때 i = 3 이 된다.

1️⃣. 3 은 탐색하지 않았으므로 if 조건문 실행.

현재 StringBuilder 의 값은 "01" 이다.
3 은 탐색하지 않았으므로 StringBuilder = "013" 이 된다.
다음 재귀 호출을 통해 현재 방문처리 안 된 값인 2 가 추가되며
StringBuilder = "0132" 가 될 것이다.

추후 로직은 위와 같다.


🎯 backTracking(4) - SET

재귀 탈출을 하면서 StringBuilder 의 값은 우리가 사용할 인덱스가 된다.
이 인덱스를 자료구조에 추가하자.

String[] WORD = {"aya", "ye", "woo", "ma"}; // 조카가 발음 할 수 있는 단어들

		...
        if (depth == size) {
            StringBuilder input = new StringBuilder();
            for (int i = 0; i < sb.length(); i++) {
                input.append(WORD[Integer.parseInt(String.valueOf(sb.charAt(i)))]);
            }
            
            SET.add(input.toString());

            return;
        }
        ...

🚀 ex) StringBuilder = "0123" 라면,
조카가 말할 수 있는 발음을 [0] + [1] + [2] + [3] 이다.

StringBuilder = "0132" 라면,
조카가 말할 수 있는 발음을 [0] + [1] + [3] + [2] 다.

해당 발음을 조합하여 Set<String> 자료구조에 추가한다.


🎯 O(1) 상수 시간 복잡도로 찾아보자

	...
    if(SET.contains(check)) {
    	answer++;
    }
    ...

위의 backTracking 으로 구한 인덱스들을 조합해서,
Set<String> 자료 구조에 발음할 수 있는 모든 단어들을 추가하였다.
.contains() 메서드를 통해 단어를 확인해주면 O(1) 시간 복잡도로 빠르게 체크할 수 있다.


나의 생각

백-트래킹은 자주 나오는 경우의 수 문제를 풀 때 유용한 것 같다.
문자열을 가공해서 푸는 것보다 재귀 함수에 익숙해지기 위해 백-트래킹을 사용하였고
백-트래킹 + Set 자료구조를 사용하면 꽤 좋은 시간 복잡도를 얻을 수 있다고 생각하여 이를 활용하였다.

코드

import java.util.*;

class Solution {
    
    private static final String[] WORD = {"aya", "ye", "woo", "ma"};
    private static final Set<String> SET = new HashSet<>();
    private static final boolean[] visited = new boolean[4];
    
    public int solution(String[] babbling) {
        int answer = 0;
        
        for (int i = 1; i <= 4; i++) {
            backTracking(new StringBuilder(), 0, i);
        }
        
        for (String check : babbling) {
            if(SET.contains(check)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    private static void backTracking(StringBuilder sb, int depth, int size) {
        if (depth == size) {
            StringBuilder input = new StringBuilder();
            for (int i = 0; i < sb.length(); i++) {
                input.append(WORD[Integer.parseInt(String.valueOf(sb.charAt(i)))]);
            }
            
            SET.add(input.toString());

            return;
        }

        for (int i = 0; i < 4; i++) {
            if (!visited[i]) {
                visited[i] = true;
                backTracking(sb.append(i), depth + 1, size);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }
    
}

profile
lkdcode
되면 한다
이전 포스트

[백준] 10986 나머지 합

다음 포스트

[Programmers] [1차] 다트 게임

0개의 댓글