99클럽 코테 스터디 29일자 TIL + iterator-for-combination

문제 출처

https://leetcode.com/problems/iterator-for-combination(leetcode)

학습 키워드

배열

시도 방법

1. 재귀적 방법을 이용해 combinationLength 길이의 조합을 모두 구한다. 이때, 중복이 없어야하고(distinct) 사전순으로 정렬을 해야하므로 이를 만족시킬 수 있는 TreeSet을 활용했다.

2. 처리한 TreeSet을 반복으로 돌리면 String[] 배열을 생성했다.

3. 전역 counter를 이용해서 next() 메서드는 배열의 counter++을 이용

4. 마지막으로 hasNext는 현재 counter가 배열의 길이보다 작은지 여부로 반환

내가 작성한 코드

class CombinationIterator {

    TreeSet<String> combMap = new TreeSet<>();  
    String[] combArr; 
    int counter = 0 ; 


    public CombinationIterator(String characters, int combinationLength) {
        
        makeCombination(characters, combinationLength , "" , 0); 
        combArr = new String[combMap.size()]; 
        int idx = 0 ; 

        for(String key : combMap) {
            combArr[idx++] = key; 
        }
    }
    
    public String next() {       
        return combArr[counter++]; 
    }
    
    public boolean hasNext() {
        return counter < combArr.length; 
    }

    private void makeCombination(String characters, int combinationLength , String now , int index) {

        //재귀 처리   
        if(now.length() == combinationLength) {
            combMap.add(now);  
            return; 
        }


        for(int i = index; i<characters.length(); i++) {         

            String sub = characters.substring(i , i+1) ; 
            int length = now.length(); 

            if(length >0 && now.substring(length-1 , length) .equals(sub)) {
                continue; 
            }
            makeCombination(characters , combinationLength , now + sub , i+1 ); 
        }
    }

}

코드설명

makeCombination(characters, combinationLength , "" , 0); 
...

private void makeCombination(String characters, int combinationLength , String now , int index) {

        //재귀 처리   
        if(now.length() == combinationLength) {
            combMap.add(now);  
            return; 
        }


        for(int i = index; i<characters.length(); i++) {         

            String sub = characters.substring(i , i+1) ; 
            int length = now.length(); 

            if(length >0 && now.substring(length-1 , length) .equals(sub)) {
                continue; 
            }
            makeCombination(characters , combinationLength , now + sub , i+1 ); 
        }
    }
    

1. 먼저 재귀를 이용해 가능한 모든 경우를 호출했다.
   재귀를 돌리면서 문자를 하나씩 추가해 길이가 같으면 TreeSet에 추가를 했다. 이때 abc 가 있으면 ab , ac , bc 가 될 수 있고, ba처럼 이전값을 참조하지 않도록 i+1을 이용해 재귀 호출시 항상 해당 문자열의 이후부터 검색할 수 있게 처리했다.
   동시에 만약 이전값과 동일한 값이 있으면 continue 처리를 했다.
   예로 abc가 있다면 aa , bb , cc 같은 케이스를 돌리지 않는 것이다.

2. TreeSet은 자동으로 중복제거및 정렬 처리되므로 별도의 정렬없이 바로 배열로 변환하였다.

출력결과

새롭게 알게된 점

없음

다음에 풀어볼 문제 - minimum-suffix-flips

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL