[Java] 3. Longest Substring Without Repeating Characters

문제 파악

 

문자열 s가 주어진다.

 

문자가 반복되지 않는 가장 긴 부분 문자열을 반환해야한다.

---

풀이

 

1️⃣ Queue 를 이용한 풀이

💡 떠오른 Idea

문자열을 순회하면서, Queue에 문자를 입력한다.

단, 입력하기 전, 입력하려는 문자가 Queue에 이미 존재한다면 그 문자를 제거하고 입력한다.

 

만약 pwwkew 문자열인 경우

 

첫 p는 큐에 없으므로 큐에 입력한다. 

 

Queue = [ p ]

 

두번째 w로 아직 큐에 없으므로 큐에 입력한다.

 

Queue = [ p, w ]

 

세번째 w는 이미 큐에 존재하는 문자이므로 큐에 문자 w가 없어질때까지 pop 한다. 그리고 입력한다.

 

Queue = [ w ]

 

...

 

이런식으로 진행되면서 중복되는 문자가 없는 부분 문자열이 큐에 갱신된다.

 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        Queue<Character> q = new LinkedList<>();
        char[] split = s.toCharArray();
        int N = split.length;
        for (int i = 0; i < N; i++) {
            if (q.contains(split[i])) {
                while (!q.isEmpty() && q.peek() != split[i]) {
                    q.poll();
                }
                q.poll();
                q.offer(split[i]);
            } else {
                q.offer(split[i]);
            }
            ans = Math.max(ans, q.size());
        }

        return ans;
    }
}

 

 

결과

 

결과는 통과했지만, 큐의 contains() 메서드의 경우 큐는 LinkedList 이기 때문에

 

특정 원소를 찾을때 원소들을 순회해서 찾아야 하므로, 위 코드는 시간복잡도가 최대 O(N^2) 이다.

 

따라서, 더 빠른 다른 방법을 고민해보았다.

 

 

2️⃣ set을 이용한 풀이

 

해결 방법은 방법 1과 유사하다. 단, set 자료구조를 사용해서 contains 시간 복잡도를 O(1) 로 사용할 수 있다.

 

포인터를 통해서, 제거해야할 원소를 체크할 수 있도록 구현하였다.

 

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;

        char[] split = s.toCharArray();
        int N = split.length;
        int pointer = 0;
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            char target = split[i];
            if (set.contains(target)) {
                while (split[pointer] != target) {
                    set.remove(split[pointer++]);
                }
                set.remove(split[pointer++]);
                set.add(target);
            } else {
                set.add(target);
            }
            ans = Math.max(ans, set.size());
        }

        return ans;
    }
}

 

결과

이전 방법보다는 약간 시간을 단축할 수 있었다.

 

---

📖 회고

 

자료 구조를 사용할 때, 더 낮은 시간 복잡도를 가진 자료구조로 해결할 수 있는지 확인해보고 활용하여 효율적인 코드를 짤 수 있도록 해야겠다는 생각이 들었다.