오늘의 학습 키워드
Stack
Queue
알고리즘 문제
LeetCode Medium. 341. Flatten Nested List Iterator
공부한 내용
Queue, 재귀 함수를 활용
오늘의 회고
- 갈수록 문제 해결 시간이 빨라지고, 스스로 해결할 수 있는 문제도 많아져서 좋다.
- 처음에 재귀 함수를 만들어서 푸는 문제가 이해가 되지도 않고 어려웠는데, 이제는 어떤 느낌인지 조금은 감이 오는 것 같다. => 어떤느낌? 배열/리스트, 큐/스택 자료구조를 사용하면서 같은 Format의 형태를 탐색해야 한다거나 등등.
처음 시도
- 주어진 nestedList를 보면 숫자와 숫자로 된 리스트가 섞여있는데, 차례대로 숫자 배열로 반환하는 게 목표였다.
- nestedList 형태를 봤을 때, NestedInteger 타입으로 되어 있고, NestedInteger는 숫자 또는 리스트 형태로 된 걸 확인했을 때, 아! 반복해서 nestedList를 순서대로 꺼내서 Integer로 된 큐에 담아야 겠다고 생각했다.
- 같은 형태의 반복, Integer를 담을 큐, 순서대로 반복 => DFS 방식으로 풀면 좋겠다!
해결
- 주어진 nestedList를 순서대로 꺼내서 Integer 타입이면 바로 Queue에 넣고, List 타입이면 다시 순서대로 꺼내서 Queue에 넣는 것을 반복하는 재귀 함수를 사용한 DFS 방식으로 풀었다.
문제 풀이
내가 푼 풀이 (Queue + DFS 방식)
/**
* // 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.*;
public class NestedIterator implements Iterator<Integer> {
private Queue<Integer> queue;
public NestedIterator(List<NestedInteger> nestedList) {
this.queue = new LinkedList<>();
reculsive(nestedList);
}
public void reculsive(List<NestedInteger> list) {
for (int i = 0; i < list.size(); i++) {
if (!list.get(i).isInteger()) {
reculsive(list.get(i).getList());
} else {
queue.offer(list.get(i).getInteger());
}
}
}
@Override
public Integer next() {
return queue.poll();
}
@Override
public boolean hasNext() {
return !queue.isEmpty();
}
}
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*/
다른 풀이 (Stack + DFS 방식)
/**
* // 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 LinkedList<NestedInteger> stack; // Stack to keep track of NestedInteger objects
public NestedIterator(List<NestedInteger> nestedList) {
stack = new LinkedList<>();
// Push nestedList elements in reverse order onto the stack
for (int i = nestedList.size() - 1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return stack.pop().getInteger(); // Return the integer from the top of the stack
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
NestedInteger curr = stack.peek();
if (curr.isInteger()) {
return true; // Found an integer
}
// Flatten nested list
stack.pop(); // Remove the list
for (int i = curr.getList().size() - 1; i >= 0; i--) {
stack.push(curr.getList().get(i)); // Push its elements in reverse order
}
}
return false; // No more integers
}
}
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*/