[Programmers] Lv0 문자열안에 문자열 Java

문제 출처

[프로그래머스 코딩 테스트 연습]

https://school.programmers.co.kr/learn/courses/30/lessons/120908

프로그래머스

 

문제 풀이

• Str1에 Str2가 있는지 확인하는 문제이므로 문자열 검색 알고리즘을 사용하면 된다.
• 보이어 무어법을 공부하고자 보이어 무어법으로 풀었다.
• 보이어 무어법의 시간 복잡도는 브루트 포스법과 KMP법 보다 알고리즘 시간이 더 빠르다.
• n = 택스트 길이, m 은 패턴의 길이일때 최악의 경우 O(n)이고 평균 O(n / m)이다. 
• 보이어 무어법으로 했을때 Str1가 “ABEFCDEF”, Str2가 “DEF” 일경우 Skip Table과 각 Step별 알고리즘은 다음과 같다.

 

Skip Table

글자	D	E	F	나머지
건너뛰기 횟수	2	1	0	Str2.length

• 오른쪽에서 왼쪽으로 갈 수록 1씩 증가하지만 같은 글자는 가장 우측에 있는 거를 따른다.
  • AFF ⇒ 2, 0, 0 → (A, 2), (F, 0,) (나머지, 3)

 

Step1 (index : 2 → 2 → 3)  

알고리즘 Step 1 그림 설명

1. 검사 시작 index 위치는 str2.length - 1 이다.
   
   
2. ㅁ 박스 친 각 자리를 오른쪽에서 왼쪽으로 index를 변경(index --;)하여 index와 박스를 검사한다.
   (ABE, DEF에서 E, F 다름)
   → E, F 검사 → 박스 친 index의 검사 횟수 1회
   → 검사 후 index → 2
   
   
3. index의 Skip Table을 확인한다.
   index 2(E)의 Skip Table → 1
   
4. 2와 3의 값을 비교 후 큰 것만큼 index 이동 → index(2) + 1 → 3

 

Step2 (index : 3 → 1 → 4)

알고리즘 Step 2 그림 설명

1. ㅁ 박스 친 각 자리를 index --하여 index와 박스를 검사한다.
   (BEF, DEF에서 (F, F), (E, E) 같고 B, D 다름)
   → F~B 검사 → 박스 친 index의 검사 횟수 3회
   → 검사 후 index → 1
   
   
2. index의 Skip Table을 확인한다.
   index 1(B)의 Skip Table → 3
   
   
3. 2와 3의 값을 비교 후 큰 것만큼 index 이동 → index(1) + 3 → 4

 

Step3 (index : 4 → 4 → 7)

알고리즘 Step 3 그림 설명

1. ㅁ 박스 친 각 자리를 index --하여 index와 박스를 검사한다.
   (EFC, DEF에서 C, F 다름)
   → C, F 검사 → 박스 친 index의 검사 횟수 1회
   → 검사 후index → 4
   
   
2. index의 Skip Table을 확인한다.
   index 4(C)의 Skip Table → 3
   
   
3. 2와 3의 값을 비교 후 큰 것만큼 index 이동 → index(4) + 3 → 7

 

Step4 (index : 7 → 5 → 5 → 성공)

알고리즘 Step 4 그림 설명

1. ㅁ 박스 친 각 자리를 index --하여 index와 박스를 검사한다.
   (DEF, DEF 전부 같음)
   → D~F 검사 → 전부 같음 → index 반환 또는 검사 결과 처리

소스 코드

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public Map<Character, Integer> createSkipTable (String keyword) {
        Map<Character, Integer> skipTable = new HashMap<>();

        int count = keyword.length() - 1;
        for (char ch : keyword.toCharArray())
            skipTable.put(ch, count--);

        return skipTable;
    }

    public int solution(String str1, String str2) {

        Map<Character, Integer> skipTable = createSkipTable(str2);

        int str1Index = str2.length() - 1;

        while (str1Index < str1.length()) {
            int str2Index = str2.length() - 1;
            
            while (str1.charAt(str1Index) == str2.charAt(str2Index)) {
                if (str2Index == 0) return 1;
                str1Index--; str2Index--;
            }
            
            int str1Distance = skipTable.get(str1.charAt(str1Index)) == null? str2.length() : skipTable.get(str1.charAt(str1Index));
            int str2SearchDistance = str2.length() - str2Index;
           
            str1Index +=  Math.max(str1Distance, str2SearchDistance);
        }

        return 2;
    }
}