99클럽 코테 스터디 35일자 TIL +flatten-nested-list-iterator

이월(0216tw)·2024년 6월 23일

99클럽 TIL 개발자취업 기능개발 미들러 스택 자바 코딩테스트 코딩테스트준비 큐 항해99

99클럽/알고리즘풀이

목록 보기

33/38

문제 출처

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

학습 키워드

큐/스택

시도 방법

이 문제는 중첩되어 있는 리스트를 평탄화(flat) 하는 것이다.
즉, 여러 차원의 배열을 1차원의 배열로 만드는 것과 같다.

리스트의 해당 값이 정수인지 리스트인지는 isInteger() 메서드로 판단이 가능했고, 정수라면 getInteger() 메서드를 이용해 바로 정답을 저장하는 result (ArrayList형태) 에 추가했다.
리스트라면 getList() 한 정보를 다시 재귀 호출함으로써 평탄화처리를 했다.

마지막으로 next() , hasNext()를 구현해야했는데 이 부분을 단순화했다. flat이라는 메서드를 통해 이미 평탄화된 완료된 ArrayList 를 대상으로 현재 포인터가 ArrayList의 size를 넘기지 않으면 hasNext를 true로 표현했다.

next()는 pointer에 해당하는 리스트 값 호출과 동시에 ++ 처리했다.

내가 작성한 코드

/**
 * // 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> {

    List<Integer> result; 
    int pointer ; 

    public NestedIterator(List<NestedInteger> nestedList) {
        result = new ArrayList<>(); 
        flat(nestedList); 
        this.pointer = 0 ; 
    }

    public void flat(List<NestedInteger> nestedList) {
        
        for(int i = 0 ; i<nestedList.size(); i++) {
            
            if(nestedList.get(i).isInteger()) {
                result.add(nestedList.get(i).getInteger()); 
            } else {
                 flat(nestedList.get(i).getList()); 
            }
        } 
    }



    @Override
    public Integer next() {        
        return result.get(pointer++) ; 
    }

    @Override
    public boolean hasNext() {
        if(pointer == result.size()) return false ;         
        return true; 
    }
}

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

코드설명

아래 핵심코드만 설명하면 될 것 같다.

 public void flat(List<NestedInteger> nestedList) {
        
    for(int i = 0 ; i<nestedList.size(); i++) {
            
        if(nestedList.get(i).isInteger()) {
                result.add(nestedList.get(i).getInteger()); 
        } else {
             flat(nestedList.get(i).getList()); 
        }
    } 
}