May LeetCoding Challenge[Day5] - First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Note: You may assume the string contain only lowercase letters.

 

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 문자열이 입력으로 주어질 때, 특정 인덱스의 문자가 중복되지 않는 문자인 지 확인하는 문제이다.

 - 문자를 카운팅하고, 해당 문자열이 몇 개 존재하는 지 확인해야 한다.

 - 문자열을 카운팅하기 가장 쉬운 자료구조인 Map을 사용했고, Map의 contains는 O(1)이다.

 - 카운팅하는 과정은 0번째 문자열부터 N번째 문자열까지 O(N) 만큼 시간복잡도가 걸린다.

 - 해당 문자가 몇 개 있는 지, 0번째 문자열부터 N번째 문자열까지 contains 하기 위해서 O(N) 큼 시간복잡도가 걸린다.

 - 우선, Map으로 해서 100퍼센트의 속도는 안 나왔지만, 문제는 풀었다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 여기까지는 없었다.

 

3. 내가 작성한 알고리즘

 

 해설: makeCountingMap() 메소드에서는 Map을 만들어준다.

 Map은 <해당 문자, 갯수>를 갖고 있는 자료구조이고, 나온 결과물을 가지고, 다시 처음 받은 문자열을 가지고, 0번째부터 n번째까지 문자를 비교하고, map에서 1개만 갖고 있는 경우 검색을 종료한다.

 

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> map = makeCountingMap(s);
        int answer = -1;
        //contains
        //O(N), 앞에서부터 검사해서 중복 없이 1개인 경우 종료
        for(int i=0; i<s.length(); i++){
            if(map.get(s.charAt(i)) == 1){
                answer = i;
                break;
            }
        }
        return answer;
    }
    
    //O(N), 몇 개가 있는 지, 카운팅
    private Map<Character, Integer> makeCountingMap(String input){
        Map<Character, Integer> map = new HashMap();
        //conting
        for(int i=0; i<input.length(); i++){
            if(map.containsKey(input.charAt(i))){
                map.put(input.charAt(i), map.get(input.charAt(i)) + 1);
            }
            else{
                map.put(input.charAt(i), 1);
            }
        }
        return map;
    }
}

 

4. 내가 작성한 알고리즘 결과

 

느...느려!

 

5. 내가 작성한 알고리즘 보완하기

 

해설: Map 자료구조를 Array로 변경한다.

 

class Solution {
    public int firstUniqChar(String s) {
        int[] arrayMap = makeCountingArrayMap(s);
        int answer = -1;
        for(int i=0; i<s.length(); i++){
            if(arrayMap[(int)s.charAt(i)] == 1){
                answer = i;
                break;   
            }
        }
        return answer;
    }
    
    private int[] makeCountingArrayMap(String input){
        int[] arrayMap = new int[150];
        for(int i=0; i<input.length(); i++){
            int index = (int)input.charAt(i);
            if(arrayMap[index] == 0){
                arrayMap[index] = 1;
            }else{
                arrayMap[index] = arrayMap[index] + 1;
            }
        }
        return arrayMap;
    }
}

 

6. 내가 작성한 알고리즘 보완한 결과

 

 Map을 Array로 변경시켰지만, 아직도 느리다는 것을 알 수 있었다. 어떻게 하면, 좋을 지 다신 전략을 생각해보기로 했다.

 

7. 내가 작성한 알고리즘을 보완하고 보완하기

 

 해설: 소문자 알파벳이 갖고 있는 아스키코드를 이용한다.

 첫 번째 루프에서는 index가 0이 나올 수 있는 것을 고려해서 arrayMap의 소문자 알파벳의 아스키코드 값에 i+1을 해준다. 만약 2번 이상 나온 경우 -1을 해준다.

 두 번째 루프에서는 한 번도 안 나온 경우 0, 2번 이상 나온 경우 -1을 고려하기 위해서, arrayMap의 값이 1이상인 인덱스를 검색한다. 그리고 그 값의 min 값을 구해서 가장 먼저 온 인덱스를 구한다.

 

class Solution {
    public int firstUniqChar(String s) {
        int answer = getAnswer(s);
        return answer;
    }
    
    private int getAnswer(String input){
        int[] arrayMap = new int[26];
        int min = 99999;
        int answer = -1;
        
        for(int i=0; i<input.length(); i++){
            int charIndex = (int)input.charAt(i) - 97;
            if(arrayMap[charIndex] == 0){
                arrayMap[charIndex] = i + 1; //index가 0이 나올 수 있는데, array의 기본값이 0
            }else{
                arrayMap[charIndex] = -1;
            }
        }
        
        for(int i=0; i<arrayMap.length; i++){
            if(arrayMap[i] > 0){
                min = Math.min(arrayMap[i], min);    
            }
        }
        
        if(min < 1 || min == 99999){
            answer = -1;
        }else{
            answer = min-1;
        }
        return answer;
    }
}

8. 흠...

 

 

9. 100프로의 전략을 보고, 알고리즘 작성하기

 

 해설 : String이 갖고 있는 lastIndex나 indexOf를 이용했다.

 indexOf 에서는 문자를 갖고 있으면서, 몇 번째에 갖고 있는 지 확인하고, 해당 인덱스가 lastIndex인 지 확인해서 결과를 return한다. indexOf나 lastIndexOf와 같은 메소드를 알고 있었지만, 시간 복잡도가 높을 것이라고 생각했다.

 하지만, 역시 느린 메소드를 놨을 리가 없다^^.

 

class Solution {
    public int firstUniqChar(String s) {
        int min = Integer.MAX_VALUE;
        for(int i=97; i<97+26; i++){//a의 아스키코드부터 z아스키코드까지
            int index = s.indexOf(i);//해당 문자를 갖고 있니? 그러면, 몇 번째에 갖고 있니?
            if(index != -1 && s.lastIndexOf(i) == index){//1개만 갖고 있는 경우
                min = Math.min(min , index);//index의 값이 가장 앞일 경우
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3320/

Explore - LeetCode