3. Longest Substring Without Repeating Characters

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

팀 알고리즘 레포지토리 주소

문제 출처

[문제 설명]

문자열의 일부를 뽑았을 때, 반복되는 문자가 하나도 없는 문자열 중에서 최대 길이인 문자열의 길이를 반환하시오.

예를 들어, abcabcbb면 abca면 a가 2번 반복되므로 성립하지 않습니다.

따라서 abc의 길이인 3이 정답입니다.

bbbb에서는 b만 계속 반복되므로, b를 1번 뽑아야 반복되는 문자가 없는 최대 길이가 됩니다.

 

[처음 생각한 접근 방법]

Queue와 Set을 동시에 이용하려고 했습니다.

Set에 넣었을 때 같은 문자인 경우 false를 반환하게 되고,

같은 문자가 있는 경우, 큐에 FIFO 성질을 이용해서 같은 문자가 나올 때까지 요소를 하나씩 뽑습니다.

주어진 문자열 bcaabc가 있을 때

b,c,a 순서로 queue에 들어갔을 때

이 상태에서 다음 a를 넣으면 queue에는 a가 들어가지만 set엔 a가 이미 있기 있기 때문에 들어가지 않습니다.

(현재 queue : b,c,a,a & set : b,a,c)

그러면 queue에서 a가 나올 때까지 poll을 합니다.

queue는 FIFO이므로 b가 나오고, c가 나오고, a가 나옵니다.

a가 나왔으므로 이제 반복되는 문자가 없으니, 다시 문자열을 만들기 시작합니다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        Queue<Character> queue = new LinkedList<>();
        int length = 0;

        for (char c : s.toCharArray()) {
            queue.offer(c);

            if (!set.add(c)) {
                //set은 중복되는 게 없으므로,
                //set의 사이즈가 길이가 됨.
                if (set.size() > length) length = set.size();

                //이미 들어간 문자가 나올 때까지 poll
                while (!queue.isEmpty()) {
                    char temp = queue.poll();
                    //새로 문자열을 만들어야하므로 set에서도 지움.
                    set.remove(temp);
                    //이미 들어간 문자가 나오면, 중복 되는 문자가 없으므로 break.
                    if (temp == c) break;
                }
                //queue에는 중복된 문자가 들어가있으므로,
                //set에도 넣어줌.
                set.add(c);
            } else {
                //같은 문자가 없으므로 queue의 크기가
                //최대 문자열의 크기임.
                if (queue.size() > length ) length = queue.size();
            }
        }

        return length;
    }
}

 

[리트코드 답안]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Queue<Character> queue = new LinkedList<>();
        int res = 0;
        for (char c : s.toCharArray()) {
            //반복된 문자가 빠져나올 때까지
            //poll로 요소들을 내보냄.
            while (queue.contains(c)) {
                queue.poll();
            }
            queue.offer(c);
            res = Math.max(res, queue.size());
        }
        return res;
    }
}    

느낀점

코드가 매우 간단, 처음에 풀려고 했던 방식이랑 비슷한 거 같다.

내가 이 방법으로 안 푼 이유는 contains를 사용하면, Queue에 자료들을 전부 linear Search해야하므로, 이 방법을 사용 안하고 Set을 이용했는데, 매우 간단하고 좋은 코드인 거 같다.

그리고 Math.max 이 메서드 자주 보는데 자주 깜빡하는 게 아쉽다.

쓸 모 없는 if else문을 줄일 수 있어 보여서 굉장히 좋아보입니다.

 

[내 답안 수정하기]]

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        Queue<Character> queue = new LinkedList<>();
        int length = 0;

        for (char c : s.toCharArray()) {
            queue.offer(c);

            if (!set.add(c)) {
                length = Math.max(set.size(),length);

                while (!queue.isEmpty()) {
                    char temp = queue.poll();
                    set.remove(temp);
                    if (temp == c) break;
                }

                set.add(c);
            } else {
                length = Math.max(queue.size(), length);
            }
        }

        return length;
    }
}

Math.max 빼고는 딱히 추가 사항은 없습니다.