[Leetcode] First Unique Character in a String #387

Question

My Solution

hashset에 s를 담은 후 replace()를 통해 특정 문자를 공백처리 한 것의 길이(num)가 s.length()보다 1 작을 경우 해당 문자의 index를 return한다.

class Solution {
    public int firstUniqChar(String s) {
        String t =s;
        Set<Character> set = new HashSet<>();
        for(int i=0;i<s.length();i++){
            set.add(s.charAt(i));
        }

        for(int j=0;j<s.length();j++){
            String ss =s;
            int num =ss.replace(String.valueOf(ss.charAt(j)), "")
                            .length();
            if(s.length()==num+1){
                return j;
            }

        }
        return -1;     

    }
}

⚠️ 문제 : 27번째 testcase에서 Time Limit Exceeded 발생

        int num =ss.replace(String.valueOf(ss.charAt(j)), "")이 오래걸리나?

contains를 사용 못함 → T/F를 반환해 주지 문자 몇개가 포함되어있는지 알려주지 않으니까

겹치는 문자의 개수를 어떻게 찾는지가 관건

---

Solution (1)

출처 : AMAZON CODING INTERVIEW QUESTION - FIRST UNIQUE CHARACTER IN A STRING (LeetCode)

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> map = new HashMap<Character, Integer>();

        //iterate to string
        for(int i=0;i<s.length();i++){
            char current = s.charAt(i);
            // HashMap에 String 다 넣고 확인x 넣으면서 기존에 있는지 확인하는것
            if(!map.containsKey(current) ){
                map.put(current,i);}
            else{
                //invalidate the character ->not unique
                //put it in negative one -> not valid, unique
                //why using negative one? not a valid index in java -> see ah not valid
                map.put(current,-1);
            } 
        }

        int min = Integer.MAX_VALUE;
        for(char c: map.keySet()){
            //if c is smaller than min and valid
            if(map.get(c)>-1 && map.get(c)<min){
                min = map.get(c);
            }
        }
        // if min == integer.max_value true = return -1, ! return min   
        return min == Integer.MAX_VALUE ?-1 : min;    

    }
}

1. HashMap<Character, Integer>
2. key 의 자료형, value의 자료형
3. iterate to string 하는 동안 기존에 들어간 key와 current key를 비교
4. → 1일차 푼 HashSet에서는 iterate 다 한 다음에 새로 for문 만들어서 문자 하나씩 비교했는데… 차이가 있음
5. map이 current key 포함하면 unique하지 않아짐 → value -1를 넣음
6. current key 포함 x unique → value 해당 index = i를 넣음
7. 최소 index를 찾기 (min값과 index 비교)map.keySet() map에 있는 모든 key 꺼냄
8. map.get(key) key의 value 가져옴
9. min = Integer.MAX_VALUE; (정수의 최댓값 나타냄 → 2^31)
10. min==Integer.MAX_VALUE이면 return -1, 아니면 return min

---

Solution(2)

출처 : by kevin 유튜브 댓글

1. String str을 charArray[]에 아스키코드로 인덱싱 해서 넣음→ 중복되는게 있으면 해당 문자의 인덱스 value가 1보다 커질 것
2. freqTable[c-’a’]++;
3. 배열의 값이 1이면 unique / 아니면 누적시켜서 return -1;

---

FeedBack / Comment

[Java] HashMap, HashSet 이란? - (5) HashMap과 HashSet의 차이

1. Set vs Map
   • Set
     • 데이터를 모은 집합
     • 데이터들간 순서 x
     • 중복 데이터 포함 x
   • Map
     • key-value로 데이터 저장
     • key를 이용해 value 얻음 → 검색 개념 강함
     • key unique, value 중복 가능
     • 데이터들간 순서 x
2. HashSet vs HashMap ?
   • 둘다 데이터 접근에 O(1)을 보장
   • HashSet
     • implements Set interface
     • entitiy mapping → 중복 허용 x
     • 단하나의 Null
   • HashMap
     • implements Map interface
     • key-value mapping → value 중복 허용
     • key null 1개만 / value null 여러개
     • Uniqueness 유지에 Set보다 선호

• 3. why HashMap?
  • unique한 단어를 찾는 문제
  • index를 알고, 찾아야 하는 문제
  • 더 알아보기

 

---

Related Concept

HashMap

• Map interface를 구현
• Map의 특징 :
  1. key- value 구성된 entity 저장
  2. key 중복저장 x, value 중복 저장 o

HashMap 사용법

• HashMap<Key자료형, Value 자료형> map = new HashMap<>();
• map.put(key, value) : 값 추가
• map.get(key) : key에 해당하는 value 값 가져옴
• map.keySet() : map의 모든 key값 가져옴
• map.containsKey(key) : map에 해당 key가 있는지 확인
• map.containsValue(value) : map에 해당 value가 있는지 확인