![리트코드 - 3. Longest Substring Without Repeating Characters](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FvgrkK%2FbtssgF24ctY%2FM0BsAkKKJakXV9chH7xyt0%2Fimg.png)
리트코드 - 3. Longest Substring Without Repeating Characters
문제 설명
주어진 문자열 s에서 반복되지 않는 문자로 이루어진 가장 긴 부분 문자열의 길이를 찾아야 합니다.
의사코드
최대값 = MIN_VALUE; 오른쪽 포인터 = 1; if 문자열 길이 = 0 0 리턴 반복문 시작 [문자열 길이만큼 순회] map 생성 c = 반복문의 처음값 map(key = c, value에는 +1) 대입 right = 시작값 + 1 반복문 시작 (오른쪽 <= 문자열 길이 -1) c3 = right 번째 문자열 map(key = c3, value +1) 대입 right +1 if value가 2면 첫번째 key가 있던 인덱스로 이동 if max보다 map 크기가 크면 max에 map 크기 대입 break; 반복문 종료 if max보다 map 크기가 크면 max에 map 크기 대입 반복문 종료 max를 리턴 |
풀이코드
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
int max = Integer.MIN_VALUE;
int right = 1;
// 문자열 길이 0
if (s.length() == 0) {
return 0;
}
for (int i = 0; i < s.length(); i++) {
Map<Character, Integer> map = new HashMap<>();
char c = s.charAt(i);
map.put(c, 1);
right = i + 1;
while (right <= s.length() - 1) {
char c3 = s.charAt(right);
map.put(c3, map.getOrDefault(c3, 0) + 1);
right++;
if (map.get(c3) == 2) {
i = s.indexOf(c3, i);
if (max < map.size()) {
max = map.size();
}
break;
}
}
// i부터 문자열 끝까지 중복이 없을때
if (max < map.size()) {
max = map.size();
}
}
return max;
}
}
코드설명
슬라이드 윈도우 기법을 떠올렸지만 실제로는 이 기법을 사용하여 구현하지 못했다.
string을 순회하는데 처음 순회할때 map을 만들어 문자열을 key 값으로 저장한다.
그리고 right 포인터를 하나씩 오른쪽으로 옮기며 다시 반복하여 저장하는데 value가 2개가 되는 순간 반복문을 종료한다.
이 때 max값보다 크기가 크면 값을 저장한다.
또, value가 2개가 된 key값의 처음 인덱스도 저장하여 그 다음 위치부터 다시 반복문을 시작한다.
예외처리는 두 곳이 있는데 처음 부분에 s의 길이가 0인 경우 0을 리턴하도록 만들었고,
특정 인덱스부터 끝까지 순회할 때 value가 모두 1인 경우도 추가해주었다.
런타임 111ms 로 간신히 통과했다고 봐도 무방한 코드였따.
시간복잡도 - O(n^2) (배열 n만큼에서 최대 배열 n-1개를 순회함)
공간복잡도 - O(n) (하나도 문자열이 겹치지 않으면 n만큼 사용)
문제를 풀며 생각한 흐름과 배운 점
문제를 푸는데 거진 2시간을 넘게 쓰고, 게다가 효율이 좋지 못한 코드를 구현했다.
첫번째 생각
처음에는 아래와 같은 코드로 작성했었다.
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
int right = 1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < s.length(); i++) {
Map<Character, Integer> map = new HashMap<>();
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
while (right < s.length() - 1) {
char c2 = s.charAt(right);
int length = right - i;
map.put(c2, map.getOrDefault(c2, 0) + 1);
right++;
if (map.get(c2) == 2 && max < length) {
max = length;
}
}
}
if (max == Integer.MIN_VALUE) {
return 1;
}
return max;
}
}
하지만 예외사항이 너무 많은 스파게티 코드였다.
실제로도 테스트케이스를 통과하지 못했다.
map을 이용하여 중복값을 확인하거나, 혹은 string 자체를 chatAt으로 확인하는 방법 두가지를 떠올렸는데 후자의 경우 반복문 안에 반복문이 들어간다고 판단해서 map을 이용한 방식을 구현하려했다.
하지만 결국 작성한 코드도 반복문 안에 반복문이었고, 그마저도 제대로 된 코드가 아니었다.
두번째 생각
슬라이드 윈도우 기법을 다시 적용해보고자 이번에는 i를 건드려 보기로 했다.
중복값이 나왔던 문자열이 있다면 그 문자열의 인덱스를 i로 정하면 될 것 같았다.
하지만 여기서 두가지 오류가 있었는데 첫번째는 인덱스를 지정하는 방식이었다.
if (map.get(c2) == 2) {
i = s.indexOf(c2);
}
단순하게 이런 코드를 짰었는데, "abcdebcbb" 와 같은 테스트 케이스에서 오류가 발생했다.
끝에서 두번째 b를 처리할 때 위 코드대로 하면 b의 처음 인덱스가 i=1 인 부분에 있기 때문에 다시 앞으로 돌아가게 된다.
두번째는 map에 있는 요소를 지우기가 어렵다.
슬라이드 윈도우 기법은 관심사를 이동시키며 앞에 요소를 제거해야 하는데 이게 상당히 껄끄러웠다.
위 문자열에선 "abcdeb" 에서 중복이 발생하여 인덱스를 c로 옮길때 기존에 담긴 key = a 인 value를 지워야한다.
마찬가지로 다시 진행하다가 "cdebcb" 부분에서는 key =c, key = d, key = e부분 value를 모두 지워야한다.
위 부분을 해결하지 못하여 map을 새로 만들어 저장하는 방식으로 구현했고, 다소 아쉬운 코드가 되었다.
다른코드
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int maxLength = 0;
Map<Character, Integer> map = new HashMap<>();
int left = 0;
for (int right = 0; right < n; right++) {
char c = s.charAt(right);
if (!map.containsKey(c) || map.get(c) < left) {
map.put(c, right);
maxLength = Math.max(maxLength, right - left + 1);
} else {
left = map.get(c) + 1;
map.put(c, right);
}
}
return maxLength;
}
}
이 코드는 Map을 사용하고 있지만, value부분에 인덱스를 저장한다.
map이 key를 가지고 있지 않거나 key값이 left보다 왼쪽에 있는 경우 map에 추가하고 length를 업데이트 한다.
만약 map이 key를 가지고 있으면 중복이 발생한 인덱스 바로 뒤로 left를 업데이트해주고, key 인덱스를 right로 업데이트 해준다.
map을 인덱스로 사용한다는 아이디어가 키포인트였던 것 같다.
정리
for문 내에서 두개의 포인터를 다루는데 조금 더 익숙해져야 되겠다.
'CS > 코딩테스트' 카테고리의 다른 글
리트코드 - 2. Add Two Numbers (0) | 2023.08.29 |
---|---|
리트코드 - 141. Linked List Cycle (0) | 2023.08.28 |
리트코드 - 209. Minimum Size Subarray Sum (0) | 2023.08.28 |
리트코드 - 167. Two Sum II - Input Array Is Sorted (0) | 2023.08.27 |
리트코드 - 125. Valid Palindrome (0) | 2023.08.26 |
남에게 설명할 때 비로소 자신의 지식이 된다.
포스팅이 도움되셨다면 하트❤️ 또는 구독👍🏻 부탁드립니다!! 잘못된 정보가 있다면 댓글로 알려주세요.