99클럽 코테 스터디 35일차 TIL + [LeetCode] 341. Flatten Nested List Iterator/스택/큐/JAVA풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

[LeetCode] 341. Flatten Nested List Iterator/스택/큐/JAVA풀이

 

 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

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

 

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.

 

 

코드

---

/**
 * // 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();
 * }
 */

import java.util.*;

/*IsInteger()는 리스트가 하나의 정수만 가지고 있는지 반환
getInteger는 리스트가 하나의 정수만 가지고 있을 때 그 정수를 반환, 리스트 hold 시 null반환
getList는 리스트가 nestedList 가지고 잇을 때 그 리스트를 반환 


*/
public class NestedIterator implements Iterator<Integer> {

    public NestedIterator(List<NestedInteger> nestedList) {//
        addInteger(nestedList);
    }

    private Queue<Integer> q=new ArrayDeque<>(); //큐 선언

    private void addInteger(List<NestedInteger> nestedList){

        for(NestedInteger ne: nestedList){
            if(ne.isInteger()) //ne가 정수면 큐에 넣어줌
                q.offer(ne.getInteger());
            else //ne가 리스트면 ne에 대해 addInteger
                addInteger(ne.getList());    
            
        }

    }

    //만들어진 q에 대하여 아래 두 메서드로 res를 생성할 수 있게 코드 작성. 
    @Override
    public Integer next() { //q의 처음 원소 반환 및 삭제
        return q.poll();
    }

    @Override
    public boolean hasNext() { //q가 비지 않았는지 검사
        return !q.isEmpty();
    }
}

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

 

 

슈도코드를 보았을 때, 

res가 생성되게 메서드를 작성해준다. 

따라서 큐를 만들어 nestedList를 flatten하게 저장해주고, q의 내용물을 next()와 hasNext()메서드로 res에 저장하게 코드를 작성했다. 

 

3. 오늘의 회고

---

 

• 큐를 이용해 풀었다.
• 리트코드에는 주어진 함수와 메서드를 채우는 문제가 있는데, 퍼즐같아서 재미있다. 
• 이번주가 스터디 마지막이다. 파이팅!