Skip to main content

38. [Java] 원하는 문자열 찾기

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

  • 알파벳으로 이루어진 문자열 myString과 pat이 주어진다.
  • myString의 연속된 부분 문자열 중 pat이 존재하면 1을 그렇지 않으면 0을 return
    • 단, 알파벳 대문자와 소문자는 구분하지 않음
  • 1 ≤ myString의 길이 ≤ 100,000
  • 1 ≤ pat의 길이 ≤ 300
  • myString과 pat은 모두 알파벳으로 이루어진 문자열

정답코드

class Solution {
    public int solution(String myString, String pat) {
        myString = myString.toLowerCase();  // 모두 소문자로
        pat = pat.toLowerCase();            // 모두 소문자로
        
        return myString.contains(pat) ? 1 : 0;
    }
}

이번 문제처럼, myString 안에 pat이 연속된 부분 문자열로 존재하는지를 판단하는 경우 contains() 메서드 한 줄로 처리가 가능하다. 추가적으로 이 문제는 대소문자를 구분하지 않고 비교해야 하므로, toLowerCase() 또는 toUpperCase()를 사용하여 두 문자열을 같은 케이스로 통일시켜주면 된다.

✅ String.contains()

자바에서 String.contains() 메서드는 문자열 안에 특정 부분 문자열(substring) 이 포함되어 있는지를 검사하는 데 사용된다. 이 메서드는 boolean 값을 반환하며, 찾는 부분 문자열이 존재하면 true, 없으면 false를 반환한다.

대소문자를 구분하며, 포함 여부만 판단하기 때문에 검색할 위치나 횟수를 따로 지정할 수는 없다. 내부적으로는 indexOf()를 호출해 -1이 아닌 경우 true를 반환하는 구조다. if (문자열.contains(부분문자열)) 형태로 조건을 검사할 수도 있다.

boolean contains(CharSequence sequence)
  • sequence : 찾고자 하는 문자열 (예: "abc", "Hello" 등)
  • CharSequence 타입이므로 String을 바로 넘길 수 있다.

내가 푼 코드 - ✅ 슬라이딩 윈도우 방식으로 부분 문자열 비교하기

아래는 내가 직접 구현한 방법이다. 이 방식은 메서드를 모르더라도 문자열 비교 문제를 직접 구현할 수 있게 해준다.

class Solution {
    public int solution(String myString, String pat) {
        myString = myString.toLowerCase();  // 모두 소문자로
        pat = pat.toLowerCase();            // 모두 소문자로
        int len = pat.length();
        for(int i = 0; i <= myString.length() - len; i++) {
            String str = myString.substring(i,i + len);
            if (str.equals(pat)) return 1;
        }
        return 0;
    }
}

이 코드는 contains() 메서드를 사용하지 않고, 직접 myString을 순회하면서 pat과 길이가 같은 부분 문자열을 하나씩 잘라(substring) 비교하는 방식이다. 이른바 슬라이딩 윈도우 기법을 활용한 것이다.

  • 두 문자열이 동일하려면 길이도 같아야 하므로, 먼저 pat.length()를 len 변수에 저장한다.
  • 그 후 myString에서 길이 len만큼 잘라가며 모든 가능한 부분 문자열을 만들어 pat과 비교한다.
  • 만약 일치하는 부분 문자열이 하나라도 있다면 즉시 1을 반환하고 종료한다.
  • 이 때 주의사항은 인덱스 범위이다.

오답

class Solution {
    public int solution(String myString, String pat) {
        myString = myString.toLowerCase();  // 모두 소문자로
        pat = pat.toLowerCase();            // 모두 소문자로
        int len = pat.length();
        for(int i = 0; i < myString.length(); i++) { // ❌
            String str = myString.substring(i, len); // ❌
            if (str.equals(pat)) return 1;
        }
        return 0;
    }
}

image.png

반복문 인덱스 범위

가장 중요한 포인트 중 하나는 substring의 인덱스 범위다. substring(i, i + len)을 사용할 때, i + len이 myString.length()를 초과하게 되면 StringIndexOutOfBoundsException이 발생하므로, 반복문의 조건은 i <= myString.length() - len 으로 설정해야 한다.

for(int i = 0; i < myString.length(); i++) { // ❌
for(int i = 0; i <= myString.length() - len; i++) { // ✔️

< 대신 <=를 쓰는 이유

부분 문자열을 추출할 때 myString.substring(i, i + len)를 사용한다. 이때 중요한 것은 i + len이 myString.length()를 초과하면 안 된다는 점이다. 즉, 마지막 부분 문자열이 myString의 끝까지 도달할 수 있어야 하므로, i는 myString.length() - len까지는 포함되어야 한다.

예를 들어:

  • myString = "abcde", pat = "de" → pat.length() = 2
  • 마지막으로 비교할 수 있는 부분 문자열은 i = 3일 때 "de" (substring(3, 5))
  • 이때 myString.length() - len = 5 - 2 = 3 → i <= 3까지 돌아야 "de"까지 검사할 수 있음
  • 만약 반복 조건을 i < myString.length() - len으로 하면 i = 3은 포함되지 않기 때문에 마지막 부분문자열인 "de"는 검사하지 못하고 정답을 놓칠 수 있다.

substring 인덱스 범위 

String str = myString.substring(i, len); // ❌
String str = myString.substring(i, i + len); // ✔️

substring의 두 번째 인자는 끝 인덱스(Exclusive)인데, 여기서는 len을 고정해서 myString의 인덱스 i부터 len까지 자르려다 보니
i가 1 이상일 때 인덱스 범위가 틀려서 StringIndexOutOfBoundsException이 발생한다. substring(i, i + len) 으로 고쳐서 해결했다.
즉, 시작 인덱스 i부터 길이 len만큼 자르는 것이다.


Back to top