Computer >> 컴퓨터 >  >> 프로그래밍 >> Java

Java 재귀 함수로 부분 문자열 등장 횟수 계산하기

두 개의 문자열 str1과 str2가 주어졌을 때, 재귀 호출 과정을 이용해 문자열 str1 안에서 부분 문자열 str2가 몇 번 등장하는지 세는 것이 이 글의 목표입니다.

여기서 재귀 함수란 자신의 정의 내부에서 스스로를 다시 호출하는 함수를 의미합니다.

예를 들어 str1이 "I know that you know that i know"이고 str2가 "know"라면,

등장 횟수는 3입니다.

구체적인 예제를 통해 살펴보겠습니다.

입력

str1 = "TPisTPareTPamTP", str2 = "TP";

출력

부분 문자열의 재귀적 등장 횟수: 4

설명

부분 문자열 TP는 str1 안에 4번 등장합니다.

입력

str1 = "HiHOwAReyouHiHi", str2 = "Hi"

출력

부분 문자열의 재귀적 등장 횟수: 3

설명

부분 문자열 Hi는 str1 안에 3번 등장합니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서는 Java의 contains() 메서드를 사용해 str1 안에 str2가 존재하는지 확인합니다. contains()는 str2가 str1에 포함되어 있으면 true를 반환합니다. true인 경우, replaceFirst() 메서드를 사용해 첫 번째 등장 부분을 빈 문자열("")로 치환하여 제거하고, 반환 값에 1을 더해 카운트를 증가시킵니다.

  • 두 문자열 str1과 str2를 입력받습니다.
  • 재귀 메서드 subsrting_rec(String str, String sub)는 문자열 str과 그 부분 문자열 sub를 인자로 받아, sub가 str에 등장하는 횟수를 반환합니다.
  • str.contains(sub)가 true인지 검사합니다. (str에 sub가 포함되어 있는지 확인)
  • true라면 str.replaceFirst(sub, "")를 사용해 첫 번째 등장 부분을 빈 문자열로 치환합니다.
  • 이 작업을 subsrting_rec(String str, String sub)의 재귀 호출 안에서 반복 수행합니다.
  • 모든 재귀 호출이 종료되면 각 단계의 반환 값을 합산한 결과가 곧 전체 등장 횟수가 됩니다.
  • 최종 결과를 출력합니다.

재귀 동작 원리

예를 들어 "TPisTPareTPamTP"에서 "TP"를 찾는 경우를 생각해 보겠습니다. 첫 호출에서 "TP"를 발견하고 이를 제거하면 "isTPareTPamTP"가 되며, 카운트는 1이 됩니다. 이 과정이 문자열에 "TP"가 더 이상 없을 때까지 반복되면서 매번 1씩 더해져 최종적으로 4가 반환됩니다. 즉, 가장 깊은 재귀 호출부터 차례대로 1씩 거슬러 올라오며 합산되는 구조입니다.

예제 코드

public class recursive{
    public static void main(String args[]){
        String str1 = "TPisTPareTPamTP", str2 = "TP";
        System.out.println("Count of occurrences of a substring recursively are: "+subsrting_rec(str1, str2));
    }
    static int subsrting_rec(String str, String sub){
        if (str.contains(sub)){
            return 1 + subsrting_rec(str.replaceFirst(sub, ""), sub);
        }
        return 0;
    }
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of occurrences of a substring recursively are: 4

참고로, 이 방식은 매 재귀 호출마다 새로운 문자열 객체가 생성되므로 문자열이 매우 길거나 부분 문자열이 많이 반복되는 경우에는 성능상 비효율적일 수 있습니다. 실무에서는 indexOf()를 활용해 검색 시작 위치만 이동시키는 반복문 방식이나 StringBuilder를 함께 사용하는 것이 더 효율적인 대안이 될 수 있습니다.