[LeetCode] 341. Flatten Nested List Iterator

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

Flatten Nested List Iterator - LeetCode

341. Flatten Nested List Iterator

문제 유형 : 재귀, 배열

문제 난이도 : Medium

 

문제

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

 

당신은 nestedList라는 네스트리스트 배열을 받습니다. 네스트리스트의 요소는 정수이거나, 네스트리스트입니다.

이러한 네스트리르스틑 한 줄로 만들도록 구현하시오.

 

생성자, 다음 요소를 출력하는 next, 다음 요소가 있는지 확인하는 hasNext를 구현해야 합니다.

 

풀이

생성자에서 재귀함수를 통해서 한 줄로 만드는 작업을 해주고, 

next에서는 다음 인덱스를 출력, hasNext는 인덱스가 범위 안에 있는지만 확인시켜주면 된다.

 

코드

C++

 

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

class NestedIterator {
    vector<int> flattened;
    int index;

    vector<int> flatten(vector<NestedInteger> nested) {
        vector<int> result;
        for(const auto &n : nested) {
        //요소가 배열이 아닌 정수라면:
            if(n.isInteger()) {
                result.push_back(n.getInteger());
            //배열이라면:
            } else {
                auto subList = flatten(n.getList());
                result.insert(result.end(), subList.begin(), subList.end());
            }
        }
        return result;
    }
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        flattened = flatten(nestedList);
         index = 0;
    }
    
    int next() {
        return flattened[index++];
    }
    
    bool hasNext() {
        return index < flattened.size();
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */