LeetCode 341. Flatten Nested List Iterator 자바 문제 풀이

문제

Flatten Nested List Iterator - LeetCode

문제 해결 방법

• 이 문제는 심플하게 자료구조를 사용하여 iterator를 구현할수 있냐고 묻는 문제입니다.
• Stack, LinkedList, Array등을 사용해서 구현할수 있습니다.
• 다만 콜렉션의 List를 사용하는것은 문제에서 요구하는것과 조금 어긋나므로, List는 사용하면 안됩니다.
• nestedList를 모두 꺼내서 하나의 리스트로 작성(평면화)해야 하므로, 스택을 사용하는것이 가장 효율적입니다.

Github Link

https://github.com/eunhanlee/LeetCode_341_FlattenNestedListIterator_Solution

Stack

import java.util.*;

/**
 * 중첩된 정수 리스트를 평면화하기 위한 Iterator입니다.
 */
public class NestedIterator implements Iterator<Integer> {
    private Deque<NestedInteger> iterList;

    /**
     * 주어진 중첩된 리스트로 새로운 NestedIterator를 생성합니다.
     *
     * @param nestedList 중첩된 정수 리스트
     */
    public NestedIterator(List<NestedInteger> nestedList) {
        iterList = new ArrayDeque<>();
        flattenList(nestedList);
    }

    /**
     * 중첩된 리스트에서 다음 정수를 반환합니다.
     *
     * @return 다음 정수
     * @throws NoSuchElementException 더 이상 요소가 없는 경우 발생합니다.
     */
    @Override
    public Integer next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        return iterList.pop().getInteger();
    }

    /**
     * 중첩된 리스트에 더 많은 정수가 있는지 확인합니다.
     *
     * @return 정수가 더 있는 경우 true, 그렇지 않은 경우 false
     */
    @Override
    public boolean hasNext() {
        while (!iterList.isEmpty() && !iterList.peek().isInteger()) {
            List<NestedInteger> nestedList = iterList.pop().getList();
            flattenList(nestedList);
        }
        return !iterList.isEmpty();
    }

    /**
     * 중첩된 리스트를 역순으로 스택에 넣어 평면화합니다.
     *
     * @param nestedList 평면화할 중첩된 리스트
     */
    private void flattenList(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            iterList.push(nestedList.get(i));
        }
    }
}