알고리즘/LeetCode

LeetCode[Java] - Longest Substring Without Repeating Characters 풀이

곤정이 2021. 4. 1. 21:46
반응형

안녕하세요. Ruk 입니다. LeetCode의 Longest Substring Without Repeating Characters 문제에 대하여 어떻게 접근하였고 풀어보았는지 풀이과정을 공유해보려 해요.

 

주어진 문자열을 입력받았을 때 해당 문자열에서 중복없이 가장 긴 문자열을 찾는 문제로 보이내요.

 

알고리즘에서 아래와 같은 조건을 걸어 보았습니다.

1. Set 인터페이스를 활용하여 중복을 체크하자.

2. 중복이 발견되면 길이를 저장 ( length비교 해야겠죠? )

3. 중복이 사라질 때 까지 Set에서 문자열 제거

 

위 조건을 구현한 코드입니다.

하지만 속도와 메모리가 너무나도 아쉽습니다.

b(n^2)의 복잡도를 가지게 되는데 while문을 사용하지 않고 최대길이를 구할 방법을 더 궁리해봐야 겠내요.

 

뭔가 좀 더 고민을 하여 코드를 최적화 시킬 수 있도록 궁리해보아야 겠내요.

안되면 leetcode가 제공하는 다른 사람의 풀이를 참고도 해보아야 겠어요.

반응형