[LeetCode] Java - First Unique Character in a String

5월에 5일차 입니다.

이번 문제는 다양한 방법이 있는 것 같아요.

난이도는 Easy 입니다.

한번 문제를 보고 풀어보시죠. 

 

1. 문제

 

문제를 보면 중복이 되지 않는 알파벳의 위치가 최소인 지점을 찾아라. 입니다.

첫번째 예시에서 leetcode의 l의 위치가 0이면서 중복이 되지 않기 때문에 답은 0이 되죠.

두번째 예시에서 loveleetcode의 v의 위치가 2이면서 중복이 되지 않기 때문에 답은 2가 됩니다.

 

이렇게 위치를 찾아내면 됩니다.

 

2. 풀이

 

풀이방법1

class Solution {
    public int firstUniqChar(String s) {
        
        // 초기 세팅
        int[] alpa = new int[26];
        Arrays.fill(alpa, -1);
        
        // 알파벳의 위치를 파악하고 중복이면 MAX 값을 넣어준다.
        for(int i=0; i<s.length(); i++){
            int n = s.charAt(i) - 'a';
            if(alpa[n] == -1){
                alpa[n] = i; 
            }else if(alpa[n] > -1){
                alpa[n] = Integer.MAX_VALUE;
            }
        }
        // 존재하는 알파벳 중에 최소 값을 찾는다.
        int min = Integer.MAX_VALUE;
        for(int i=0; i<26 ; i++){
            if(alpa[i] != -1) min = Math.min(min, alpa[i]);
        }
        
        // 만약, 1개인 알파벳이 존재하지않으면 -1 출력.
        if(min == Integer.MAX_VALUE) min = -1;
        return min;
    }
}

첫번째 풀이 방법은 이전 String과 char를 사용해서 풀었던 문제랑 비슷합니다.

알파벳 만큼의 배열을 선언하고 그 배열 위치 정보 또는 중복 정보를 함께 저장한 후 마지막에 위치의 min 값을 가져 옵니다.

 

입력으로 받는 s의 길이 + 알파벳의 26번 정도 복잡도가 들어갑니다. 

O(n) 이고 S의 길이만큼 시간복잡도가 걸린다고 할 수 있겠네요.

 

풀이방법2

class Solution {
    public int firstUniqChar(String s) {
                
            int res = Integer.MAX_VALUE;

            for(char c = 'a'; c <= 'z'; c++){
                int index = s.indexOf(c);

                if(index != -1 && index == s.lastIndexOf(c))
                    res = Math.min(res, index);
            }

            return res == Integer.MAX_VALUE ? -1 : res;
    }
}

이 방법은 이 문제를 가장 잘 이해 했다고 표현해야 할 것 같습니다.

java에서 사용할 수 있는 String의 함수들을 알맞게 사용하는 방법입니다.

 

char의 a~z까지 for문으로 돌리면서 처음 나오는 index 값과 마지막의 index 값이 같으면 1개만 존재한다고 볼 수 있죠. 그래서 같은 값이라면 업데이트 해주고 결과를 가져옵니다.

 

loveleetcode로 예를 들어보면 

첫번재 l는 indexOf로 했을때 0이 나오고 lastIndexOf로 했을때는 4가 나옵니다.

세번째 v는 indexOf로 했을때 2가 나오고 lastIndexOf로 했을때도 2가 나오게 되죠.

 

이렇게 간단히 알파벳의 수만큼만 for을 돌려서 답을 얻어 낼 수 있습니다.

참 쉽죠?