[JAVA]BOJ 1543

문제

import java.util.Scanner;

public class BOJ1543 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String key = sc.nextLine();
        int i, j, k, result = 0;

        for(i=0;i<str.length();i++){
            j = i;
            for(k=0;k<key.length();k++){
                if(j == str.length()) // key는 남아있는데 str이 끝난 경우, 이 조건이 없으면 에러남
                    break;
                else if(str.charAt(j) == key.charAt(k)) // 같으면 다음글자 비교
                    j++;
                else // 다르면 끝
                    break;
            }
            if(k == key.length()){ // str에 key가 있다면
                result++;
                i = j - 1; // 반복문에서 i++되므로 -1해주어야 함
            }
        }
        System.out.println(result);
    }
}

코드에서 큰 논리는 이렇다.

1. str의 첫 글자부터 끝까지 확인한다.

2. str의 지금 글자부터 key의 글자를 각각 비교한다.

3-1. str에 key가 있으면,  str속의 key이후 위치부터 2를 반복한다.

3-2. key가 없으면 str의 다음 글자부터 2를 반복한다. 

이게 무슨소리냐.. 

str: abbccc    key: bb 인 경우

 a  b  b  c  c  c           b b

[0][1][2][3][4][5]        [0][1]

1. str을 끝까지 확인할거다. 2. 첫글자를 비교해보자. str의 [0]a 와 key의 [0]b는 다르다.

그래서 3-2가 적용된다. str의 다음글자인 [1]b로 넘어간다. 그리고 다시 2로 돌아간다.

2. str의 [1]b와 key의 [0]b를 비교한다. 같다 -> 다음 글자도 key와 같은지 비교 -> [2]b 와 [1]b가 같다 -> str안에 key가 있다!

3-1. key가 있으므로 str속의 key이후 위치, 즉 [3]c부터 다시 2(str과 key가 같은지)를 반복한다.

 

<변수 설명>

i: str을 끝까지 확인하는 용도, 직접움직이지 않음

j: str의 i로부터 움직여서 key와 비교하는 변수

k: key를 움직이는 변수

 

주어진 예제 외에 신경써야할 반례는 

aabb ab               1

abababc ababc   1

aa aa                   1

정도가 있다. 특히 나는 2번째의 abababc ababc 처럼 중간에 달라지는 경우를 예상하지 못해서 시간을 꽤 썼다. 3-1을 구현하지 않았었다. 

---

다른 풀이법: indexOf 함수 이용

str.indexOf(key, startIdx);  : str 문자열의 startIdx부터 처음으로 등장하는 key문자열을 찾는다. 찾았다면 일치하는 시작 인덱스를 반환한다. 찾지 못했다면 -1을 반환한다.

int startIdx = 0; // 시작점
while(true){
    int findIdx = str.indexOf(key, startIdx);
    if(findIdx < 0) // 찾지 못했다면
        break;
    result++; // 찾았다면 있으므로 개수 증가
    startIdx = findIdx + key.length(); // 다음 위치(key이후)부터 탐색
}
System.out.println(result);

---

또 다른 방법: replace 함수 사용

원리는 str: aabaab , key: aa를 입력받았을때, key인 aa를 모두 지우면 bb만 남는다. str의 글자수는 6글자에서 2글자로 남는다. 즉, 4(사라진 글자의 수) / 2(key의 크기) = 2, 2번 나온다는 이야기다.

String replaced = str.replace(key, ""); // key와 같으면 ""으로 변환
result = (str.length() - replaced.length()) / key.length();
System.out.println(result);

replaced는 변환된 문자열이다.