[LeetCode] First unique character in a string

🧑‍💻 언어 및 제출 결과

• 사용 언어: JavaScript
• 통과 여부: ✅

🧠 풀이 설명

실패

• indexOf와 filter를 같이 사용했을 땐 O(n²) 이라 긴 문자열일 경우엔 타임 아웃

  const firstUniqChar = (s) => [...s].findIndex((char, _, arr) => arr.filter(c => c === char).length === 1);

성공

• indexOf 와 lastIndexOf를 사용 해 시간 복잡도를 줄여봄
• 첫 번째 위치와 마지막 위치가 같다면 그 문자는 유니크한 값임
• 예시

  [...s]로 ['l','e','e','t','c','o','d','e'] 배열 생성

findIndex가 각 문자를 순회:
index 0: 'l' → indexOf('l')=0, lastIndexOf('l')=0 → 0===0 → true → 0 반환

만약 "loveleetcode"였다면:
index 0: 'l' → indexOf('l')=0, lastIndexOf('l')=4 → 0≠4 → false → 다음으로
index 1: 'o' → indexOf('o')=1, lastIndexOf('o')=9 → 1≠9 → false → 다음으로
index 2: 'v' → indexOf('v')=2, lastIndexOf('v')=2 → 2===2 → true → 2 반환

 

전체 코드

const firstUniqChar = s => [...s].findIndex(c => s.indexOf(c) === s.lastIndexOf(c));

📊 시간/공간 복잡도

• 시간 복잡도: O(n²)- findIndex O(n) × indexOf/lastIndexOf O(n)
• 공간 복잡도: O(n) - 문자열을 배열로 변환

📝 추가 설명 (선택)

궁금하실진 모르겠지만 실패 케이스와 성공 케이스가 둘 다 O(n²)인데 타임 아웃이 아닌 이유를 간략히 설명하겠읍니다.

filter의 동작 방식

• filter는 뭐가 됐던 눈이 오나 비가 오나 무조건 전체 배열을 끝까지 순회합니다.
• 그래서 유니크한 값이 있는지 확인하고 걸러주기 위해 끝까지 훑어 본 뒤 값을 반환합니다.
• 실제 연산: n × n = n² (항상)indexOf/lastIndexOf의 동작 방식
• indexOf는 앞에서 부터 찾으면 즉시 중단,
• lastIndexOf는 뒤에서부터 찾으면 즉시 중단
• 이기 때문에 문자가 길어도 찾는다면 findIndex가 즉시 중단 됩니다