99클럽 코테 스터디 35일차 TIL + 스택/큐(Flatten Nested List Iterator)

오늘의 과제

리트코드 medium으로 분류된 Flatten Nested List Iterator 입니다.

 

이번 유형은 스택/큐 입니다.

문제

https://leetcode.com/problems/flatten-nested-list-iterator/description/

 

 

먼저 문제 요구사항 요약입니다.

 

중첩 가능한 리스트가 주어집니다. 다음 요소를 반환하는 next(), 다음 요소가 있는지를 반한하는 hasNext() 함수를 구현하면 됩니다.

 

일단 문제의 힌트에 맞게 스택/큐를 사용하여 접근했습니다. 처음 주어지는 nestedList내 요소가 숫자인지, 중첩 List인지 알 수 없기 때문에 일단은 스택에 모두 넣어놓고 숫자면 pop, 아니면 해당 리스트 내 요소를 push하는 방법으로 풀이를 진행했습니다.

 

먼저 Stack의 초기화입니다. Stack을 사용한 이유는 단순 평탄화만 진행해야지 순서가 바뀌면 안되기 때문에 사용했습니다.

private Stack<NestedInteger> stack;

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

 

next()의 경우엔 호출 전 hasNext()를 통해 값이 있는지 여부를 확인할 것이기 때문에 그냥 stack의 값을 Integer 형태로 반환해줍니다.

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

 

 

hasNext()입니다. 처음 서술했듯 중요 로직은 현재 요소가 List인지, Integer인지를 판별하고 Integer의 경우 next()에서 꺼낼 수 있게 treu를 반환, 중첩된 List라면 내부 요소를 다시 Stack에 넣고 false를 반환합니다.

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

 

 

코드입니다.

import java.util.*;

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    private Stack<NestedInteger> stack;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        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.isEmpty()) {
            NestedInteger current = stack.peek();
            if (current.isInteger()) {
                return true;
            } else {
                stack.pop();
                List<NestedInteger> nestedList = current.getList();
                for (int i = nestedList.size() - 1; i >= 0; i--) {
                    stack.push(nestedList.get(i));
                }
            }
        }
        return false;
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

 

 

배운 점

더 효율적인 코드를 찾아보니 재귀로 풀이를 진행했습니다. 핵심 로직은 단순 List만 사용하고 Integer의 경우엔 값을 반환하고 또 다른 List의 경우엔 다시 재귀로 호출하여 값을 넣는 형식인데 스택을 쓰는 형태와 로직이 거의 동일한데도 시간 복잡도나 공간 복잡도에서 모두 더 좋은 결과를 나타내고 있습니다.

 

사실 이미 서버 자산들이 차고 넘치는 상황에서 조금의 공간 복잡도나 시간 복잡도가 크게 영향을 줄 것 같지는 않기 때문에 조금 더 복잡하지만 빠른 코드보다는 누가봐도 이해하기 편한 코드가 더 좋지 않을까? 라는 생각을 조심스럽게 해봅니다.

 

 

 

오늘의 한줄평

사실 개발자는 쓰는 시간보다는 읽는 시간이 월등히 많다.