[프로그래머스] 문자열안의 문자

마음을 다잡고 기초부터 다시 시작하는 첫째날.
코딩테스트 Lv0 입문버전을 풀어보며, 호기심으로 찾아본 삽질을 포스팅해보려 한다.

문제

난이도 : 입문
주어진 문자열 str2가 str1안에 포함되어 있는지 물어보는 문제다.

제출 및 풀이

• 첫번째로 푼 답안은 substring으로 str1을 str2사이즈로 쪼개서 탐색하도록 하였다.

class Solution {
    public int solution(String str1, String str2) {
        int answer = 2;
        int str1Len = str1.length();
        int str2Len = str2.length();
        for (int i = 0; i <= str1Len - str2Len; i++) {
            String pwd = str1.substring(i,i+str2Len);
            if(pwd.equals(str2)) {
                answer=1;
                break;
            }
        }
        return answer;
    }
}

• String의 매소드로 풀이한 답안을 확인하는데 contains()와 indexOf()의 풀이가 눈에 보였다.
• 간단하게 공식문서를 확인하면 contains는 boolean으로 리턴하며 indexOf(String a)는 int형을 리턴하게된다.

궁금증. Java 17 열어보기

Q1. contains와 indexOf의 리턴타입은 다르지만 문자열내에서 주어진 문자열이 있는지 탐색을 한다는 점에서 같다. 서로 의존적이진 않은가?
A1. 그랬다. String클래스 파일을 열어보면 리턴시 indexOf(Stirng str)을 호출하는걸 볼수 있다.

public boolean contains(CharSequence s) {
        return indexOf(s.toString()) >= 0;
    }

• String 클래스는 CharSequence 인터페이스를 구현함으로 s에는 String을 사용할 수 있다.

Q2. indexOf는 어떤 방식으로 탐색하는 걸까?
A2. byte단위(char)단위로 찾아야하는 문자열의 첫글짜의 위치를 찾은 후 나머지를 비교한다.

Step1. 인코딩 방식에 따른 indexOf 호출

public int indexOf(@NotNull String str) {
        byte coder = coder();
        if (coder == str.coder()) {
            return isLatin1() ? StringLatin1.indexOf(value, str.value)
                              : StringUTF16.indexOf(value, str.value);
        }
        if (coder == LATIN1) {  // str.coder == UTF16
            return -1;
        }
        return StringUTF16.indexOfLatin1(value, str.value);
    }

• value는 string안에 저장된 char[] 배열 이다.
• string의 내부표현은 UTF-16을 사용하게 되는데, java9부터 추가된 Compacting Strings(메모리 절약을 위한)기능을 사용하기 위해 coder를 사용한다.

Step2. str(str2)가 빈 배열이거나, value(str1)보다 길이가 긴경우 포함할 수 없음으로 검사 후 indexOfUnsafe를 호출한다.

@IntrinsicCandidate
    public static int indexOf(byte[] value, byte[] str) {
        if (str.length == 0) {
            return 0;
        }
        if (value.length < str.length) {
            return -1;
        }
        return indexOfUnsafe(value, length(value), str, length(str), 0);
    }

• 어노테이션은 이해가 잘안되서 패스..

Step3. 첫번째 글자가 있는지 확인 후 나머지 문자를 비교한다.

• 전달된 인자는 valueCount는 value의 length이며 formIndex는 0이다.

private static int indexOfUnsafe(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {
        assert fromIndex >= 0;
        assert strCount > 0;
        assert strCount <= length(str);
        assert valueCount >= strCount;
        char first = getChar(str, 0);
        int max = (valueCount - strCount);
        for (int i = fromIndex; i <= max; i++) {
            // Look for first character.
            if (getChar(value, i) != first) {
                while (++i <= max && getChar(value, i) != first);
            }
            // Found first character, now look at the rest of value
            if (i <= max) {
                int j = i + 1;
                int end = j + strCount - 1;
                for (int k = 1; j < end && getChar(value, j) == getChar(str, k); j++, k++);
                if (j == end) {
                    // Found whole string.
                    return i;
                }
            }
        }
        return -1;
    }

• assert fromIndex >- 0;은 fromIndex가 0보다 크거나 같지 않다면 AssertionError를 던지게 된다.
• assert 부분은 컴파일시 사용되고 런타임에선 무시된다. (명시적으로 런타임에도 살려둘 수 있다.)

Q3. 나는 substring으로 같은크기로 잘라내어 equals를 사용하였는데 어떤 순서로 비교되었을까?
A3. equals는 잘라진 문자열 끼리 첫문자부터 끝까지 비교한다. 다른 문자가 보이면 false를 리턴하고 종료된다.

    @IntrinsicCandidate
    public static boolean equals(byte[] value, byte[] other) {
        if (value.length == other.length) {
            for (int i = 0; i < value.length; i++) {
                if (value[i] != other[i]) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

결론

• String에서 contains는 indexOf()를 사용하여 문자열을 탐색한다.
• 내코드에서는 substring으로 문자열을 잘라서 같은지 비교하였는데. 제공되는 메소드로 찾는게 가장 효율적인것 같다.
• substring과 equals를 사용해야 한다면, 첫문자 위치를 찾은 후 substirng으로 두번째 부터 잘라서 사용할 까 생각했는데.. 기능이 중복될것 같다. 복잡하게 생각하지말고 indexOf()사용하자 ㅎㅎ