387.First Unique Character in a String
문제
- 문자열이 주어지면, 처음으로 반복되지 않은 문자의 인덱스를 찾아라. 반복되지않는 문자가 없다면 -1을 리턴하기
Examples:
s = "leetcode"
return 0.
s = "loveleetcode"
return 2
Note
- 문자열은 모두 소문자라고 가정합니다.
Solution 1. 앞에서부터 비교하기
1번 문자가 다음번째랑 같은지 안같으면 다음과 같은지 비교하다 같으면 2번 문자부터 순차적으로 비교하기
1......n
2.....n
3...n
Solution 2. Map활용하기
문자를 Key, 갯수를 Value로 만들기 ( 1...n )
문자열의 앞의 문자부터 순서대로 Map의 키로 전달해 Value를 확인하여 1인 문자가 나오면 해당 인덱스를 반환한다.
( 1...n )
1번의 방법은 너무 많은 반복이 일어날 수 있다. 맨 마지막의 문자가 1번 쓰였을 경우 n번, n-1번, n-2번, ...., 2번, 1번의 경우까지 확인하는 경우도 있어 좋은 방법이라고 생각되지는 않는다.
2번의 경우는 문자열을 처음부터 끝까지 2번만 움직여보면 확인할 수 있는 방법이다.
처음에는 Map에 해당 문자별 갯수가 몇개인지 넣어두고
두번째는 문자열의 순서에 맞게 해당 문자의 갯수가 몇개인지 확인하여 해당 문자의 인덱스를 찾으면 된다.
Tip
Map.getOrDefault(key, defaultValue)
- Key에 아무 값도 할당하지 않을 경우 defaultValue로 설정한 값을 리턴해주는 메서드이다.
아무 값도 할당하지 않았을 때 map[key]를 사용하면 null을 반환하므로 위의 메서드를 활용하면 좋다.
Code
Reference
'Algorightm' 카테고리의 다른 글
[Kotlin] 344.ReverseString [LeetCode] (0) | 2020.04.28 |
---|---|
[Level1] 완주하지 못한 선수 (0) | 2019.10.24 |
Hash Algorithm (0) | 2019.10.14 |
시간복잡도를 알아보자 (0) | 2019.07.17 |