https://leetcode.com/problems/longest-substring-without-repeating-characters
평가
결과 : 2번 실패 후 성공
풀이시간 : 첫 풀이 14분, 이후 디버깅 12분
문제 제약조건을 제대로 읽지 않아서 틀렸습니다. 문자열에는 알파벳만 가능하다 생각했는데 공백 등의 문자열이 포함되는 걸 확인하지 못했습니다.
그리고 리트코드는 어떤 예시에서 정답이 틀렸는지 보여주는데 그걸 의식적으로 보지 않아야겠습니다. 오류를 보면 사실 어디서 틀렸는지를 알 수 있어 안보는 게 맞다고 생각합니다.
아이디어
문제는 아래와 같은 순서로 풀었습니다.
- 문자열을 순회합니다.
- 만약 해당 문자가 처음 나온 문자라면 문자열에 추가합니다.
- 만약 이미 나온 문자라면, 해당 문자열의 시작부터 그 문자가 있던 곳까지 문자열에서 제거합니다.
해당 문자가 나왔는지 검사하기 위해 Map 자료구조를 사용했습니다.
Map<Character, Integer> 를 사용해 문자열과 해당 문자열의 Index를 저장합니다.
추후 검사할 문자가 visited.containsKey && visited.get(문자) != -1 조건에서 true라면, 정답 문자열에 포함되어 있다는 의미입니다.
문자열이 존재한다면, 정답 문자열에서 기존 문자까지를 잘라냅니다.
말로 설명하면 복잡하니 그림으로 설명하겠습니다.
그림 설명
d를 바라보는 시점에서 visited에는 다음과 같은 값들이 들어갑니다.
즉, 지금까지 정답 문자열은 abc(길이 3)입니다.
여기에서 d가 추가되면서 문자열(visited)을 갱신합니다.
정답 문자열은 abcd(길이 4)가 됩니다.
다음 문자 b를 선택되었을 때 상황을 살펴보겠습니다. b는 visited에 1이라는 인덱스로 값이 저장되어있습니다.
4번째 인덱스에 위치한 b를 정답 문자열에 넣기 위해서는 기존 문자열에서 b를 없애야 합니다.
즉, 정답 문자열의 시작부터 b가 나온 위치까지 잘라내야 합니다.
기존에 b의 위치가 1이었으니, 문자열의 시작이었던 0부터 1까지 visited를 초기화시켜주고, 문자열의 길이를 갱신합니다.
임시로 정답 문자열은 cd(길이 2)가 됩니다.
cd라는 정답 문자열에 b라는 문자를 추가하는 과정을 거칩니다.
정답 문자열은 cdb(길이 3)이 됩니다.
계속 이런 과정을 거치면 O(N) 의 시간복잡도로 최대 문자열의 길이를 찾을 수 있습니다.
수도코드
수도코드는 없습니다. 처음 잘못된 방식으로 수도코드를 만들었습니다. 이후 디버깅을 통해 문제를 다시 풀어 수도코드가 존재하지 않습니다.
따라서 풀이는 코드에다가 적어두겠습니다.
class Solution {
public int lengthOfLongestSubstring(String s) {
// 특정 문자가 몇 번째 인덱스에서 나왔는지 기록합니다.
// 예를 들어 abc라는 문자열이 있다면 c -> 2 라는 값이 기록됩니다.
Map<Character, Integer> visited = new HashMap<>();
int maxLength = 0;
int idx = -1;
// 정답 문자열의 시작을 기록한다
int startIdx = 0;
// 정답 문자열의 길이를 기록한다
int length = 0;
char[] chars = s.toCharArray();
for(char each: chars) {
idx++;
// 정답문자열 안에 each 문자가 존재한다면
if (visited.containsKey(each) && visited.get(each) != -1) {
// 몇 번째 인덱스에 위치하는지 확인한다
// 정답 문자열의 처음부터 해당 문자열까지 연결을 끊는다.
int prev = visited.get(each);
for(int i = startIdx; i <= prev; i++) {
visited.put(chars[i], -1); // 초기화
}
// 정답 문자열의 길이와 시작 지점의 위치를 갱신한다
length -= (prev - startIdx + 1);
startIdx = prev + 1;
}
// each가 추가된 정답 문자열의 길이를 갱신하고, 문자열에 each를 넣는다
length++;
visited.put(each, idx);
// 만들 수 있는 가장 긴 길이를 찾는다
maxLength = Math.max(maxLength, length);
}
return maxLength;
}
}