[leetcode] 763. Partition Labels

https://leetcode.com/problems/partition-labels/

방법1 : 통과는 했는데... 효율은 별로

이중 for 문을 돌면서 문자 덩어리들을의 시작점-끝점을 left-right 로 정의를 했음, 그리고 나서 덩어리가 넘어간다는걸 어떻게 판단했냐면 현재 i 위치가 right 를 넘어설 때, 즉 이전의 덩어리 범위를 벗어난 인덱스를 가리킬 때 덩어리의 길이를 ans에 추가해주고 left,right 을 i로 초기화 해줬다.

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        
        int left = 0;
        int right = 0;
        
        for(int i = 0 ; i<= s.length() ; i++){
            
            if(right < i){
                ans.add(right - left + 1);
                left = i;
                right = i;
            }
            
            if(i == s.length()) break;
            
            for(int j = i+1 ; j < s.length() ; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(right < j) right = j;
                }
            }
        }
        
        
        return ans;
    }
} 

방법2 : 해쉬맵을 이용

discussion 을 보고 "아~ 이렇게하면 이중 포문을 돌 필요가 없네" 라고 이마를 탁! 쳤다. 포문을 한번 돌면서 해쉬맵에 "문자" : "마지막으로 발생한 인덱스" 를 한번 저장해 둔다..!!

그후에 다시 포문을 돌면서 해쉬맵에서 해당 문자의 마지막 인덱스를 계속 가져온다. 그리고 똑같이 현재 i 인덱스가 right 와 같아질 때 ans 에 길이들을 추가해주고 left, right 값을 초기화 해준다.

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        
        for(int i= 0 ; i< s.length() ; i++){
            map.put(s.charAt(i) , i);
        }
        
        int left = 0;
        int right = 0;
        for(int i = 0 ; i< s.length() ; i++){
            
            if(right < map.get(s.charAt(i))){
                right = map.get(s.charAt(i));
            }
            
            if(i == right){
                ans.add(right - left + 1);
                left=i+1;
            }
        }
        
        return ans;
    }
} 

일단 기존보다 많이 개선한듯..! 근데 이거보다도 더 효율적이게 짜는게 있나보네;;