99클럽 코테 스터디 35일차 TIL Flatten Nested List Iterator

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

 

 

 

queue

stack

imp

 

 

 

 

1. 문제 및 접근

 

 

 

감싸있는 거 다 빼고 정수만 반환하라 3가지 메서드

1. list형태의 nestedList가 들어오면 초기화

2. next의 경우 들어오면, 다음 정수 반환

3. hasNext 다음 수가 있음 true 아님 false

 

[[1,1],2,[1,1]] = [1,1,2,1,1]

 

 

판단 방식은 while문에서 hasNext가 true면 next를 호출

 

 

stack or queue ?

 

ide 예제로 확인하기 위해

NestedInteger인터페이스 및 클래스 구현까지

 

 

Constraints:

 

• 1 <= nestedList.length <= 500
• The values of the integers in the nested list is in the range [-10^6, 10^6].

 

 

 

 

 

 

 

2. 전체 코드

 

public class NestedIterator implements Iterator<Integer>{


    /**
     
     * isInteger():  NestedInteger가 단일 정수를 포함하고 있는지 여부를 확인합니다.
     * getInteger():  NestedInteger가 단일 정수를 포함하고 있을 때 그 정수를 반환합니다.
     * 중첩된 리스트를 포함하고 있을 경우 null을 반환합니다.
     * getList(): NestedInteger가 중첩된 리스트를 포함하고 있을 때 그 리스트를 반환합니다.
     * 단일 정수를 포함하고 있을 경우 빈 리스트를 반환합니다.
     */


    // 감싸있는 거 다 빼고 정수만 반환하라 3가지 메서드
    // 1. list형태의 nestedList가 들어오면 초기화
    // 2. next의 경우 들어오면, 다음 정수 반환
    // 3. hasNext 다음 수가 있음 true 아님 false

    //[[1,1],2,[1,1]] = [1,1,2,1,1]

    //스택으로 확인 ?

    // 판단 방식은 while문에서 hasNext가 true면 next를 호출

    private Stack<NestedInteger> stack;

    public static void main(String[] args) {
        List<NestedInteger> list =Arrays.asList(
                new NestedIntegerImpl(Arrays.asList(
                        new NestedIntegerImpl(1),
                        new NestedIntegerImpl(1)
                )), new NestedIntegerImpl(2),
                        new NestedIntegerImpl(Arrays.asList(
                                new NestedIntegerImpl(1),
                                new NestedIntegerImpl(1))

        ));

        NestedIterator i1 = new NestedIterator(list);
        List<Integer> result1 = new ArrayList<>();
        while (i1.hasNext()) {
            result1.add(i1.next());
        }
        System.out.println(result1);



    }


        public NestedIterator(List<NestedInteger> nestedList) { // 타입만 바꿔서 ㄱㄱ

            stack = new Stack<>();

            for (int i = nestedList.size() - 1; i >= 0; i--) {
                stack.push(nestedList.get(i));
            }



        }

        @Override
        public Integer next() {

            return stack.pop().getInteger();


        }

        @Override
        public boolean hasNext() {

            while (!stack.isEmpty()) {
                NestedInteger now = stack.peek();

                if(now.isInteger()) {
                    return true;
                }
                stack.pop();
                List<NestedInteger> nestedList = now.getList();
                for (int i = nestedList.size() - 1; i >= 0; i--) {
                    stack.push(nestedList.get(i));
                }

            }

            return false;

        }
    }

 

 

 

 

2-1. NestedInteger 인터페이스

 

public interface NestedInteger {

    public boolean isInteger();

    public Integer getInteger();

    public List<NestedInteger> getList();
}

 

 

 

NestInteger의 인터페이스는 3가지 메서드를 구현해야 한다.

 

 

 

1. isInteger 

 

• 단일 정수가 포함되어 있는 지 여부를 반환하는 메서드

 

2. getInteger

 

• 단일 정수를 포함하고 있을 때 그 정수를 반환, 
• 중첩된 리스트 포함할 경우 null 반환

 

3. getList

 

• 중첩된 리스트를 포함하고 있을 때 그 리스트 반환,
• 단일 정수를 포함할 경우 빈 리스트 반환

 

 

 

 

 

 

 

 

2-2. NestedInteger 구현체

 

 

public class NestedIntegerImpl implements NestedInteger {
    private Integer value;
    private List<NestedInteger> list;


    public NestedIntegerImpl(Integer value) {
        this.value = value;
        this.list = null;
    }

    public NestedIntegerImpl(List<NestedInteger> list) {
        this.value = null;
        this.list = list;
    }




    @Override
    public boolean isInteger() {
        return value != null;
    }

    @Override
    public Integer getInteger() {
        return value;
    }

    @Override
    public List<NestedInteger> getList() {
        return list;
    }

}

 

 

 

 

 

value를 담을 전역변수,

NestedInteger 타입의 list

 

 

 

 

 

생성자

 

 

1.  단일 정수만 받을 경우

• value 값 대입,
• list는 null

 

 

 

 

2.  중첩 리스트를 받을 경우

• value 값 null,
• list 값 대입

 

 

 

구현체 메서드

 

 

 

위에서 설명했으니

 

원하는 요구에 맞게 return;

 

기본적으로 isInteger로 List or 정수로 판별 해야겠다.

 

 

 

 

 

 

 

 

3.  풀이 stack

 

 

 

 

아까 만든 NestInteger 타입의 stack 선언

 

 

 

 

 

 

 

 

[[1], [2, 3], 4] 의 중첩 리스트가 들어오면 [1, 2, 3, 4]의 형태로 바꿔야 한다.

 

 

stack을 활용해서 풀어야겠다고 생각했다.

https://medium.com/@songjaeyoung92/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-javascript-stack-%EC%9D%B4%EB%9E%80-31f9bbb84897

 

 

 

 

생성자 호출 시 stack에 들어온 list를 담아줌

 

 

 

stack의 구조는 LIFO이기에 반대로 넣어준다.

 

 

 

 

ex)  stack = [5, [2, [3, 4]], 1] 

 

 

 

 

 

3-1. next()

 

 

 

 

next의 경우 들어오면, 다음 정수 반환

 

return 값으로 stack에서 꺼내준다.

 

NestedInteger 타입의 stack value

 

 

 

 

 

 

 

 

 

 

 

3-2. hasNext()

 

 

 

hasNext 다음 수가 있음 true 아님 false

 

 

 

문제의 평가 방식은 iter를 돌면서 hasNext가 true일 경우 Next를 호출할 수 있고 Next는 현재 요소 반환

 

 

 

 

stack을 돌며

 

 

• stack의 isInteger를 사용해 현재 수를 확인해서 정수라면 ?

 

       바로 return true;

 

 

• stack의 isInteger가 정수가 아니라면 ?

 

       list의 형태를 가지고 있다는 뜻

       중첩리스트를 제거하고 역순으로 다시 stack에 추가해주자

 

 

 

 

 

 

이 list를 Integer 타입으로 stack에 넣어줘야 평가 방식에서 중첩리스트만 빼고 정수만 반환 가능하다.

 

 

 

그렇다면 stack에서 list를 꺼내, 다시 역순으로 stack에 추가해주기!

 

 

 

[[3,4]] 이라면 스택에 넣고 빼려면 [[4,3]] 형태로 넣어야하는데, 정수형으로 넣어야 하니 4,3 처럼 역순으로 넣어주는 동작

 

 

모두 다 정수 형태로 반환하기 위함

 

 

 

 

 

 

 

 

 

3-4. 평가 방식을 사용해 hasNext()를 설명하겠다.

 

 

 

원래 nestedList = [1, [2, [3, 4]], 5]

현재 stack = [5, [2, [3, 4]], 1]  ,    result = [ ]

 

 

 

 

 

 

1)  it.hasNext() 판별

• stack[last] = 1,  정수형이니 true 반환

 

 

1)1  it.next() 호출

• stack[last] = 1,  제거 후 result에 추가
• stack = [5, [2, [3, 4]] ,   result = [1]

 

 

2) it.hasNext() 판별

• stack[last] = [2, [3, 4]], list 타입이니 stack에서 [2, [3, 4]]을 제거  index 1 = 2, index 2 = [3,4] 
• 아까 뽑아둔 now에서 now.getList()
• 다시 역순으로 stack에 추가
• stack = [5] 만 있다가 다시   -> stack = [5, [3,4], 2] 추가됨
• (감싸고 있는 중첩 리스트 하나를 벗긴 셈이다 두개의 리스트니까)

 

 

2)1 it.next() 호출

• stack[last] = 2 제거 후 result에 추가
• stack =[5, [3, 4]] ,   result = [1, 2]

 

 

3) it.hasNext() 판별

• stack[last] = [3, 4], list 타입이니 stack에서 [3, 4]을 제거  
• 아까 뽑아둔 now에서 now.getList()
• 다시 역순으로 stack에 추가
• stack = [5] 만 있다가 다시   -> stack = [5, 4, 3] 추가됨

 

 

3)1 it.next() 호출

• stack[last] = 3제거 후 result에 추가
• stack =[5, 4] ,   result = [1, 2, 3]

 

 

 

4) it.hasNext() 판별

• stack[last] = 3  정수형이니 true 반환

 

 

4)1 it.next() 호출

• stack[last] = 4제거 후 result에 추가
• stack =[5] ,   result = [1, 2, 3, 4]

 

 

5) it.hasNext() 판별

• stack[last] = 5  정수형이니 true 반환

 

 

5)1 it.next() 호출

• stack[last] = 5제거 후 result에 추가
• stack =[] ,   result = [1, 2, 3, 4, 5]

 

6)  it.hasNext() 판별

• stack[last] = []  비어 있으니, false 반환 후 끝

 

 

 

 

 

최종 result = [1, 2, 3, 4, 5]

 

 

 

 

 

 

 

 

 

4. 마무리

 

 

사실 이런 문제를 접하면 stack으로 풀까 ? queue로 풀까 바로 떠오르지 않는다.

 

 

 

4-1. stack vs queue

 

 

 

 

 

 

 

둘다 구현이 가능해서.. 그래도 이런 문제는 stack을 고르자!

 

 

 

핵심은

 

queue는 간단한 구현이 가능하고 메모리 사용만 크게 문제가 되지 않는다면, 직관적이라 구현하기 쉽다. 재귀

stack은 구현이 조금 복잡하지만 ,메모리적으로 효율적일 수가 있다. 반복문

 

 

queue가 메모리 사용량이 많은 이유는 FIFO 구조 상 요소를 앞에서 부터 하나 씩 추가하고 빼기 때문에 중간 상태에서 중첩된

리스트들이 각 queue에 저장되어 기록되기 때문에 탐색에도 불리..

 

 

즉 중간과정에서 stack은 뒤에 하나만 빼면 되는데, queue는 queue로 된 형태의 queue를 빼고 추가해줘야 한다

머리로는 이해되지만 한번 또 따로 구현해서 실험 해봐야겠다!

 

 

 

 

 

 

 

 

 

여튼 리스트의 형태를 유지할 때 어떤 걸 먼저 쓸까의 고민이 들지 않도록 자료구조를 좀 더 숙지해야겠다..

당연히 효율적인 stack을 고르는 게 맞다고 보인다..

 

 

오랜만에 구현 하는 것까지 하니까 살짝 헷갈렸지만 , leetcode는 불편하고 불친절하지만 이런 구현의 문제가 있어서

색다로워서 좋네..

ide없이 하려니까 테스트하려니 어려워서 직접 구현한 거지만 핑계대자면 구현도 해보고 좋다.

ide 없이도 쭉 해결할 수 있을 때 까지 파이띵!