[Sliding Windows + TDD] Leetcode 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-interview-150

Longest Substring Without Repeating Characters - LeetCode

https://github.com/fineman999/algorithm_java/issues/3

3. Longest Substring Without Repeating Characters · Issue #3 · fineman999/algorithm_java

---

1. 들어가기 전

예전에 NextStep 강의 사이트에서 자바 플레이그라운드 with TDD, 클린 코드를 수강을 했었다. 강의 내용은 어떻게 하면 객체 지향적으로 코드를 작성하는지에 대한 가이드라인을 제시해준다. 강사님이 이야기해주었던 내용으로 TDD는 처음부터 잘 할 수 없다고 하셨다. TDD, 리팩토링과 관련해 5, 6년을 도전한 후에야 테스트하기 어려운 코드와 쉬운코드를 구분하고 설계하는 감을 익힐 수 있다고 하셨다. TDD 공부하는 방법으로 추천하신 방법 중 한 가지로 알고리즘을 공부할 때 TDD로 작성해보라고 하셨다. 그래서 이번에는 TDD를 적용해보자.

2. 알고리즘

문자열 s가 주어지면, 반복 문자 없이 가장 긴 부분 문자열의 길이를 찾는다.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

3. 실패한 테스트 코드 작성

class SolutionTest {

    private final Solution solution = new Solution();

    @ParameterizedTest
    @CsvSource({"abcabcbb, 3", "bbbbb, 1", "pwwkew, 3", " , 0", "dvdf, 3", "abba, 2"})
    @DisplayName("lengthOfLongestSubstring 메서드는 문자열 s 를 받아 최대 부분 문자열의 길이를 반환한다.")
    void test(String s, int expected) {

        int actual = solution.lengthOfLongestSubstring(s);

        assertThat(expected).isEqualTo(actual);
    }
}

프로덕션 코드는 컴파일 에러만 안뜨게 작성한 후 테스트 코드를 작성했다. 이제 테스트 해보자.

테스트 결과 - 실패

하나를 제외한 테스트가 모두 실패한 것을 볼 수 있다. 이제 코드를 작성해보자.

4. 프로덕션 코드 작성

public class Solution {

    private final Map<Character, Integer> storage = new LinkedHashMap<>();
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int max = 0;
        storage.clear();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (storage.containsKey(c)) {
                int index = storage.get(c);
                storage.entrySet().removeIf(entry -> entry.getValue() <= index);
            }
            storage.put(c, i);
            max = Math.max(max, storage.size());
        }
        return max;
    }
}

해당 클래스에 문자들을 담기 위해 삽입된 순서를 유지하여 순서를 보존하는 특성을 가지는 LinkedHashMap을 사용하였다.

1.  파라미터 값으로 string이 들어오면 null 체크와 s가 비어있는지 체크한다. 
   1. 만족하면 0 반환
2. 그리고 초기화를 한다. 
3. for문을 진입한다.
   1. 만약 storage에 저장되어 있으면 크기 이전에 저장된 값을 모두 제거한다.
   2. 문자와 index를 저장한다.
   3. 최대값을 비교한다.
4. 반환한다.

5. 성공한 테스트 확인

테스트 결과 - 성공

Leetcode 테스트 결과

테스트는 성공했다! 하지만 성능상 문제가 보인다. 더 좋은 방법이 있는지 찾아보자.

6. 리팩토링

public class Solution {

    /**
     * 이 클래스는 인스턴스를 만들 수 없습니다.
     */
    private Solution() {
        throw new AssertionError();
    }

    public static int lengthOfLongestSubstring(String s) {
        checkNull(s);
         Map<Character, Integer> storage = new HashMap<>();
        if (s.isEmpty()) {
            return 0;
        }

        int max = 0;
        int left = 0;
        int right = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            if (storage.containsKey(c)) {
                left = Math.max(left, storage.get(c) + 1);
            }
            storage.put(c, right);
            max = Math.max(max, right - left + 1);
            right++;
        }
        return max;
    }
    private static void checkNull(String s) {
        if (s == null) {
            throw new IllegalArgumentException("s must not be null");
        }
    }
}

조사해보니 어차피 Map안에 index를 저장할 수 있으니까 LinkedHashMap을 사용하지 않아도 되는걸 깨달았다. 그리고 연속되는 값을 확인하는 것이니까 SlidingWindow에 해당된다.  Math.max(left, storage.get(c) + 1); 같은 경우 left가 storage에 저장된 index보다 커야되기 때문에 max로 비교하게 된다. 

또한 유틸리티 클래스이기 때문에 인스턴스 생성을 방지하였다.

Leetcode 테스트 결과

단위 테스트 결과

위와 같이 10배의 성능을 향상시켰다.

7. 왜 TDD를 작성하는가?

현업에서의 개발은 정말 많은 코드와 무수히 많은 데이터베이스의 테이블들이 있다. 처음에 테스트 코드를 제대로 작성하지 않고 막 구현을 할때는 문제가 발생하지 않지만 점차 서비스가 커지고, 사람도 바뀌게 되면 문제가 발생하게 된다. 각각의 메소드나 모듈이 결합도가 증가하게 되고 하나 고치면 다른 게 문제가 발생하는 상황을 목격하게 될 것이다.

이것에 대한 테스트를 미리 작성해두고 프로덕션 코드를 작성하고 리팩토링 하는 과정에서 미리 실수를 방지함으로써 시간을 절약하게 된다. 또한 새로운 사람이 들어왔을 때 테스트 코드를 통해 어떠한 로직이 실행되는지를 알게 되서 업무에 좀 더 빠르게 대처할 수 있지 않을까라는 생각이 든다.