[코딩 테스트 RUN] SWEA 수업 : 1213. String

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

[SW Expert Academy] 1213. String

SW Expert Academy

 

사실 글자수 세기 자체는 꽤 많이 나온 방법이라 취향 차이다.

내가 한 방법은 바로 대상 문장의 length를 구하고, 찾는 문자를 replace로 한 뒤의 length를 구한 뒤, 그 둘을 빼고 찾는 문자의 length만큼 나누는 것이다.

그렇게 하면 개수가 나타난다.

 

 

다만, BruteForce를 사용하는 방법이 있다.

 

int count = 0;

for(int c = 0; c <= len - len2; c++){
  int i = c, j = 0;
  while(i < len && j < len2 && str.charAt(i) == find.charAt(j)){
      i++; j++;
  }
   if(j == len2) count++;
}

 

 

이것은 BruteForce의 응용이다.

 

일단 BruteForce는 아래와 같은 식을 통하여 패턴을 비교한다. 본문 문자열을 처음부터 끝까지 한칸씩 이동하여 매치하는지 확인하고, 제일 첫번째 인덱스를 반환한다.

            // M: 패턴 길이, N: 본문 길이
            public int bruteForce(String pattern, String text) {
                int M = pattern.length();
                int N = text.length();
                int i = 0; // 본문(text)의 인덱스
                int j = 0; // 패턴(pattern)의 인덱스
                while (j < M &/ i < N) {
                    if (text.charAt(i) != pattern.charAt(j)) {
                        i = i - j; j = -1; // j는 0으로 초기화 (아래에서 +1됨)
                    }
                    i += 1; j += 1;
                }
                if (j == M) { return i - M; }  // 패턴이 일치하는 시작 인덱스 반환
                    return -1; // 패턴이 본문에 없는 경우
                }

 

여기서는 일단 1. 전체 카운트를 위해서 바깥 for문이 필요하다. 즉, for문 안이 하나의 BruteForce라고 보면 좋다. 따라서 i는 0에서 시작하지 않고 c에서 시작한다. 조건 문은 보다시피 BruteForce 일반과 비슷한데, 여기서는 그냥 인덱스 반환이 아니라 카운팅이므로 일치하면 카운팅을 시키는 것. 일치하지 않을 경우에는 패턴이 맞지 않기 때문에 그냥 바로 while문을 종료시키면 된다.

 

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = 10;
        for (int test_case = 1; test_case <= T; test_case++) {
            int t = Integer.parseInt(br.readLine());
            String find = br.readLine();
            String str = br.readLine();

            int len = str.length();
            int len2 = str.replace(find, "").length();

            int count = (len - len2) / find.length();

            sb.append("#").append(test_case).append(" ").append(count).append("\n");


        }//테스트 케이스

        System.out.print(sb.toString());
    }
}

 

아래는 BruteForce를 사용하는 방법이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = 10;
        for (int test_case = 1; test_case <= T; test_case++) {
            int t = Integer.parseInt(br.readLine());
            String find = br.readLine();
            String str = br.readLine();

            int len = str.length();
            int len2 = find.length();

            int count = 0;

            for(int c = 0; c <= len - len2; c++){
                int i = c, j = 0;
                while(i < len && j < len2 && str.charAt(i) == find.charAt(j)){
                    i++; j++;
                }
                if(j == len2) count++;
            }

            sb.append("#").append(test_case).append(" ").append(count).append("\n");

        }//테스트 케이스

        System.out.print(sb.toString());
    }
}