I solved all intro problem in codesignal~

I solved all codesignal problem in intro,

next I will try graph arcade. I think graph problem is more difficult than intro.

395. Longest Substring with At Least K Repeating Characters

문제

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

풀이 사고

• k보다 적은 카운트의 경우 k위치를 기준으로 자른다음 재귀로 문제 접근
• ex ) ababcaaad k=2
  • 전체의 카운트
    • a = 5, b=2, c=1; d=1 즉 k보다 작은게 존재하면 작은 캐릭터 기준으로 자른다
    • c 와 d 를 콤마(,)로 치환
    • abab,aaa,
    • , 를 기준으로 split한후 다시 자른 String으로 반복로직 구현

Runtime: 3 ms, faster than 77.01% of Java online submissions for Longest Substring with At Least K Repeating Characters.

class Solution {
    int max;

    public int longestSubstring(String s, int k) {
        max =0;

        if(k>s.length()){return 0;}
        findMax(s, k);
        return max;
    }

    public void findMax(String s, int k){
        int arr[] = new int['z' - 'a' +1];

        // setting
        for(int i=0; i<s.length(); i++){
            int index = s.charAt(i) -'a';
            arr[index]++;
        }

        // 전부다 k보다 더 큰 수가 나오는 경우는 max값을 갱신
        if(allEqualOrBigger(arr, k)){
           max = Math.max(max, s.length());
        }else{
            char[] str= new char[s.length()];
            for(int i=0; i<s.length(); i++){
                int index = s.charAt(i) -'a';

                if(arr[index] == 0 ){
                    continue;
                }else if(arr[index] >=k){ //
                    str[i] = s.charAt(i);
                }else{
                    str[i] = ',';
                }
            }
            String[] subs = new String(str).split(",");
            for(int i=0; i<subs.length; i++){
                if(subs[i].length() <= max){
                    continue;
                }
                findMax(subs[i], k);
            }
        }
    }

    public boolean allEqualOrBigger(int arr[], int k){
        for(int i=0; i< arr.length; i++){
            if(arr[i] >0 && arr[i]<k){
                return false;
            }
        }
        return true;
    }
}

stack을 이용한 알고리즘

문제

https://leetcode.com/problems/flatten-nested-list-iterator/discuss/?orderBy=recent_activity

접근

1. 재귀로 접근을 하면 flat하게 값만 쉽게 추출할수 있을것 같았다. 사실 이렇게 되면 사이즈가 클 경우 초기화 하는 시간이 오래 걸리니 초기화 하는 시간은 최대한 줄이는 방법을 생각해보았다.
2. 그래서 Queue를 이용해서 어떻게 할 수 있나 생각해보았다. Queue로 생각을 해도 답이 안나왔음.
3. 그래서 Stack을 이용해서 답을 구함
4. 너무 Runtime에 신경쓰지 않기로함 ㅎ

최종그림

Runtime: 6 ms, faster than 42.53% of Java online submissions for Flatten Nested List Iterator.

public class NestedIterator implements Iterator<Integer> {

   Stack<NestedInteger> stack = new Stack<NestedInteger>();
    public NestedIterator(List<NestedInteger> nestedList) {
    	for(int i= nestedList.size() -1; i>=0; i--){    		
    		stack.push(nestedList.get(i));	    		
		}   	
    }

    @Override
    public Integer next() {
    	return stack.pop().getInteger();		
    }

    @Override
    public boolean hasNext() {
    	while(stack.size()>0){
    		NestedInteger nestedInteger = stack.peek();
    		if(nestedInteger.isInteger()){
    			return true;
    		}else{
    			nestedInteger = stack.pop();
    			List<NestedInteger> list = nestedInteger.getList();
    			for(int i=list.size()-1; i>=0; i--){
    				//stack.push(list.get(i));
    				if(list.get(i).isInteger()){
    	    			stack.push(list.get(i));	
    	    		}else{
    	    			if(list.get(i).getList().size()>0){
    	    				stack.push(list.get(i));
    	    			}
    	    		}
    			}
    		}
    	}
    	return false;
    }
}