[최적화 및 문제풀이] 문자열 순열 찾기 문제

문자열 b에서 문자열 s의 모든 순열을 찾는 문제는 자주 등장하는 문제 중 하나입니다. 이 문제를 해결하기 위해 Brute Force 방법을 사용할 수도 있지만, 이는 매우 비효율적입니다. 이번 글에서는 Brute Force 접근법을 알아보고, 이를 최적화된 O(B) 시간 복잡도의 알고리즘으로 변환하는 과정을 자세히 설명하겠습니다.

 

 

목차

 

 

문자열 순열 찾기 문제

문제: 길이가 작은 문자열 s와 길이가 긴 문자열 b가 주어졌을 때, 문자열 b안에 존재하는 문자열 s의 모든 순열을 찾는 알고리즘을 설계하시오. (각 순열의 위치를 출력하면 된다)

 

Brute Force 접근 (O(S! * B))

Brute Force 접근법은 문제를 해결하는 가장 직관적인 방법으로, 다음과 같은 단계로 진행됩니다.

• 문자열 s의 모든 순열 생성
  먼저, 문자열 s의 모든 가능한 순열을 생성합니다. 문자열 s의 길이가 S라면, 순열의 개수는 S!개가 됩니다.
  
  
• 각 순열을 문자열 b에서 검색
  생성된 각 순열에 대해 문자열 b에서 해당 순열이 존재하는지 확인합니다. 이 과정에서 부분 문자열 비교는 O(B) 시간 복잡도를 가집니다.

    private static void generatePermutations(String prefix, String str, Set<String> permutations) {
        int n = str.length();
        if (n == 0) {
            permutations.add(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                generatePermutations(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), permutations);
            }
        }
    }
    
    public static List<Integer> findPermutations(String s, String b) {
        List<Integer> result = new ArrayList<>();
        Set<String> permutations = new HashSet<>();
        
        generatePermutations("", s, permutations);
        for (String perm : permutations) {
            for (int i = 0; i <= b.length() - s.length(); i++) {
                if (b.substring(i, i + s.length()).equals(perm)) {
                    result.add(i);
                }
            }
        }
        
        return result;
    }

 

시간 복잡도

• 순열 생성의 시간 복잡도: O(S!)
• 각 순열을 b에서 찾는 시간 복잡도: O(B)

따라서, 전체 알고리즘의 시간 복잡도는 O(S! * B)입니다. 이 접근법은 s의 길이가 작을 때는 작동하지만, S가 조금만 커져도 매우 비효율적입니다.

 

슬라이딩 윈도우와 해시맵을 이용한 최적화 접근 O(B * S)

Brute Force 접근법은 매우 비효율적이기 때문에, 우리는 이를 최적화할 방법을 모색해야 합니다. 이 과정에서 슬라이딩 윈도우와 해시맵을 사용하여 시간 복잡도를 O(B * S)로 줄일 수 있습니다.

 

해시맵을 사용한 문자 빈도 비교

Brute Force 방법의 핵심 문제는 모든 순열을 생성하고 각각을 검색하는 데 너무 많은 시간이 소요된다는 점입니다. 이를 해결하기 위해, 문자열 s와 동일한 길이의 부분 문자열을 슬라이딩 윈도우 방식으로 탐색하며, 문자열 s와 비교할 수 있는 더 효율적인 방법이 필요합니다.

 

먼저, 문자열 s의 각 문자의 빈도를 계산하여 해시맵 또는 배열에 저장합니다.

		Map<Character, Integer> sCount = new HashMap<>();
		for (char c : s.toCharArray()) {
			sCount.put(c, sCount.getOrDefault(c, 0) + 1);
		}

 

슬라이딩 윈도우로 탐색

문자열 b에서 s의 길이와 동일한 크기의 윈도우를 슬라이딩하며, 각 윈도우에서 s와 동일한 문자의 빈도를 가지는지 확인합니다.

		Map<Character, Integer> bCount = new HashMap<>();
		int windowSize = s.length();

		for (int i = 0; i < b.length(); i++) {
			char c = b.charAt(i);
			bCount.put(c, bCount.getOrDefault(c, 0) + 1);

			if (i >= windowSize) {
				char leftChar = b.charAt(i - windowSize);
				if (bCount.get(leftChar) == 1) {
					bCount.remove(leftChar);
				} else {
					bCount.put(leftChar, bCount.get(leftChar) - 1);
				}
			}
			if (bCount.equals(sCount)) {
				result.add(i - windowSize + 1);
			}
		}

 

시간 복잡도 분석

• sCount 해시맵 초기화
  이 단계에서는 문자열 s의 각 문자의 빈도를 계산하여 sCount 해시맵에 저장합니다. 이 작업의 시간 복잡도는 O(S)입니다. 여기서 S는 문자열 s의 길이입니다.
• 주 반복문
  b 문자열의 길이를 B라고 할 때, 주 반복문은 B번 실행됩니다. 
• 해시맵 비교
  bCount와 sCount가 같은지 비교하는 작업이 있습니다. 해시맵의 비교는 최악의 경우 해시맵의 모든 엔트리를 비교해야 하므로, 이 작업의 시간 복잡도는 O(S)입니다. 여기서 S는 해시맵의 크기, 즉 문자열 s의 길이입니다.

이 코드의 전체 시간 복잡도는 O(B * S)입니다. 여기서 B는 문자열 b의 길이, S는 문자열 s의 길이입니다.

 

슬라이딩 윈도우와 고정 크기 카운터를 사용한 최적화 접근 O(B)

슬라이딩 윈도우(Sliding Window)와 고정 크기 카운터(Fixed-size Counter)를 사용하여 최적화를 진행할 수 있습니다. 이 방법은 문자 빈도를 비교할 때, 비교 작업을 효율적으로 처리하여 O(B) 시간 복잡도를 달성합니다.

    public static List<Integer> findPermutations(String s, String b) {
        List<Integer> result = new ArrayList<>();
        int sLen = s.length();
        int bLen = b.length();
        
        if (sLen > bLen) {
            return result;
        }
        
        int[] sCount = new int[26];
        int[] windowCount = new int[26];
        
        for (int i = 0; i < sLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            windowCount[b.charAt(i) - 'a']++;
        }
        
        int matches = 0;
        for (int i = 0; i < 26; i++) {
            if (sCount[i] == windowCount[i]) {
                matches++;
            }
        }
        
        for (int i = sLen; i < bLen; i++) {
            if (matches == 26) {
                result.add(i - sLen);
            }
            
            int rightIndex = b.charAt(i) - 'a';
            windowCount[rightIndex]++;
            if (windowCount[rightIndex] == sCount[rightIndex]) {
                matches++;
            } else if (windowCount[rightIndex] == sCount[rightIndex] + 1) {
                matches--;
            }
            
            int leftIndex = b.charAt(i - sLen) - 'a';
            windowCount[leftIndex]--;
            if (windowCount[leftIndex] == sCount[leftIndex]) {
                matches++;
            } else if (windowCount[leftIndex] == sCount[leftIndex] - 1) {
                matches--;
            }
        }
        
        if (matches == 26) {
            result.add(bLen - sLen);
        }
        
        return result;
    }

• 고정 크기 배열: 문자열 s와 길이가 같은 윈도우 내의 문자 빈도를 추적하기 위해 크기가 26인 배열(영문 소문자 가정)을 사용합니다.
• 슬라이딩 윈도우: 문자열 b를 순회하면서 길이가 s와 같은 윈도우를 이동시킵니다.
• 동적 비교: 각 윈도우에서 문자 빈도가 s의 문자 빈도와 일치하는지 효율적으로 비교합니다.

알고리즘 동작 도식화

 

시간 복잡도 분석

• 초기화: O(S) (문자열 s의 길이만큼 문자 빈도 배열을 초기화)
• 슬라이딩 윈도우: O(B) (문자열 b의 각 문자에 대해 최대 O(1) 시간 복잡도로 윈도우를 업데이트 및 비교)

따라서, 전체 알고리즘의 시간 복잡도는 O(B)입니다.