384. Shuffle an Array

문제

https://leetcode.com/problems/shuffle-an-array/

코드

import java.util.*;

class Solution {

    private List<Integer> prevRes;
    private List<Integer> res;
    private List<Integer> resIdx;
    private int[] nums;
    private boolean visit[];
    private boolean isSet = false;
    private boolean isEnd = false;


    public Solution(int[] nums) {
        this.nums = nums;
        this.res = new ArrayList<>();
        this.resIdx = new ArrayList<>();
        this.visit = new boolean[nums.length];

        for(int i=0; i<nums.length; i++){
            resIdx.add(i);
            res.add(nums[i]);
        }

    }

    public int[] reset() {
        return nums;
    }

    public int[] shuffle() {
        if(resIdx.size() == 0){
            resIdx.clear();
            res.clear();
            for(int i=0; i<nums.length; i++){
               resIdx.add(i);
                res.add(nums[i]);
            }
        }

        for(int i=0; i<visit.length; i++)
            visit[i] = true;
        isSet = false;
        isEnd = false;
        dfs(0, nums.length);
        return prevRes.stream().mapToInt(i->i).toArray();
    }

    void dfs(int curDepth, int N){

        if(curDepth == N){
            if(!isSet){
                prevRes = new ArrayList<>();
                for(int num : res)
                    prevRes.add(num);
                isSet = true;
                return;
            }else{
                isEnd = true;
                return;
            }
        }

        int curIdx = 0;
        if(!isSet)
            curIdx = resIdx.get(curDepth);

        for(int i=curIdx; i<N; i++){
            if(!isSet){
                dfs(curDepth+1, N);
                if(isEnd)
                    return;
                visit[i] = false;
                res.remove(res.size()-1);
                resIdx.remove(resIdx.size()-1);   

            }
            else if(!visit[i]){
                visit[i] = true;
                res.add(nums[i]);
                resIdx.add(i);
                dfs(curDepth+1, N);
                return;                
            }
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

피드백

• 1시간 초과함
• permutation들이 각각 같은 확률로 나와야하는게 어려운 점이었다.
  • 모범답안은 random()을 쓰는데,,, 이 것을 정말 신뢰할 수 있을까? 난 못한다.
• dfs로 단순하게 permutation들을 뽑을 수는 있으나, 이걸 한 번에 다 뽑는 것은 최대 200!의 공간복잡도가 필요해서 말이 안됬다.
  • 따라서 한 개씩 뽑아야 한다.
  • 한 개씩 뽑기 위해서는 history를 유지해야 한다.
• dfs를 히스토리를 유지하면서 한 회기씩 뽑는 것이 구현 난이도가 높았다.
  • 기본 아이디어는 history에 쓰여진 대로 한 번 찌르고, 그 다음에 한 회기만 거치고 종료하는 것.
  • 원래 history 따라가는 부분, 한 회기의 history를 새로 쓰는 부분을 나누었다.
  • 근데 원래 history를 따라가는 부분에서 더 이상 진행되지 않고 끝나야하는 depth가 존재했다. 이때 isEnd로 예외처리 해줌
• random()을 안 쓰니 까탈스러운 예외들이 많은 문제였다. 하지만 해볼 가치가 있는 도전이었음.