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;
    }
}