99클럽 코테 스터디 27일차 TIL - 스택/큐

오늘의 학습 키워드

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