Today's Algorithm(2018-10-02)

LeetCode 3

가장 처음에 든 생각은 어떤 것을 선택할 것인가?입니다. 그리고 그것을 어떻게 선택할 것인가?입니다. 만약 모든 경우를 고려한다고 한다면 어떻게 선택할 수 있을까요?

지금 가장 먼저 든 생각은 아래와 같습니다.

1. 한 글자씩 탐색하면서 char 타입으로 ArrayList에 넣는다.
2. 다음 글자가 만약 ArrayList 안에 값이 들어있다면 기존 최고 길이와 ArrayList크기를 비교하여 더 큰 것으로 교체한다. 이후 ArrayList안 값을 초기화하고 그 글자부터 다시 시작한다.

 

이렇게 하면 문제에서 주어진 테스트 케이스의 경우 통과를 하지만 아래와 같은 경우 통과하지 못하였습니다.

Input : "dvdf"
Output : 2
Expected : 3

저의 경우 "dv" 이후 "d"에서 다시 시작하여 최종 "df"의 길이를 출력했지만 실제 답은 "vdf" 를 요구하기 때문입니다. 만약 시작 시점을 기존 같은 것 이후의 시점부터 다시 시작한다면 정상적으로 작동할까요? 그렇게 된다면 "bbbbb" 의 경우엔 무한 반복이 되지 않을까요?

 

우선 통과하지 못한 케이스 바탕으로 보완하였을 때 아래와 같은 코드가 나오는데요.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] cArray = s.toCharArray();
        List<Character> cList = new ArrayList<>();
        int answer = 0;

        for (int i = 0; i < cArray.length; i++) {
            char c = cArray[i];
            if(cList.contains(c)) {
                answer = Math.max(answer, cList.size());
                int index = cList.indexOf(c);
                for(int j = 0; j <= index; j++) {
                    cList.remove(0);
                }
                cList.add(c);
//                i = index + 1;
                continue;
            }
            cList.add(c);

        }
        answer = Math.max(answer, cList.size());

        return answer;
    }
}

제 의도는 주석처리한 부분까지 생각한 것이었는데 왜 주석처리 하였을 때 정상적으로 작동하는 것일까요? 정말 틀알맞(틀린줄 알았는데 맞았네?!)이네요. 조금 더 생각하보니 제가 잘못 생각했었네요. i = index; 부분이 없어야하는 이유는 아래와 같습니다.

• 안의 for문에서 반복되는 char이전의 값만 지워주기 때문 굳이 인덱스 바꿔줄 필요없다.
• 만약 주석 풀어준게 정상적으로 작동하려면 일부만 지워주는 것이 아니라 반복되는 것이 나올 때 clear()한 다음에 하면 될 것이라 생각했지만 무한 반복이 출력되네요.
• 반복문에서 인덱스 i값을 변경시키는 것은 버그 발생 위험이 높으므로 최대한 바꾸지 않는 방법으로 생각해보는게 좋을 것 같습니다.

 

다른 풀이를 살펴보면 HashMap을 사용한 것도 있네요. 저의 코드랑 비슷하지만 제가 일일이 지워준 것과 다르게 인덱스만 이동하였고 이를 통해 복잡도도 줄였습니다.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}