[99클럽 코테 스터디 42일차 TIL] First Day Where You Have Been in All the Rooms - Java [자바][LeetCode]

 

📜 문제 내용

 

🤔 과정

• 0번 방부터 i 번 방까지 모든 방을 방문하는 데 걸리는 최소 날짜를 저장한 dp 배열을 생성.
• 이때, 최소 날짜가 굉장히 커질 수 있으므로 overflow 문제를 방지하기 위해서 문제에서 주어진 10의 9승 + 7 을 MOD 변수에 넣고 계산 수행. 
• int 형의 범위를 초과할 수 있으므로 long 자료형을 이용한다. 

< 이동 로직 >

• i 번 방을 방문하는 데 걸리는 날을 계산하기 위해서는 이전 방인 i - 1 번 방까지의 방문 최소 날짜인 dp[i - 1] 값과, nextVisit[i - 1] 번 방으로 돌아가야 하는 날이 필요하다. 
• dp[i - 1] 값은 이미 알고 있는 값으로 0 번 방부터 i - 1 번 방까지 모든 방을 방문하는 데 걸리는 최소 날짜이다. 
• 초기 상태 : 우리는 i - 1 번 방에 도착한 상태고, dp[i - 1] 일이 걸렸다. ( dp[i - 1] )
• 첫 번째 방문 : 초기 상태에 의해 1번 방문한 상태고, 홀수 번째 방문이므로 nextVisit[i - 1] 번 방으로 이동하면서 1일 추가 ( + 1 )
• nextVisit[i - 1] 번 방에서 다시 i - 1 번 방으로 돌아오기 : 0 번 방에서 i - 1 번 방까지의 걸린 날짜(dp[i - 1]) 와 0 번 방에서 nextVisit[i - 1] 번 방까지의 걸린 날짜(dp[nextVisit[i - 1]]) 의 차이가 곧 nextVisit[i - 1] 번 방에서 dp[i - 1] 번 방까지 가는데 걸린 날짜이다. ( dp[i - 1] - dp[nextVisit[i - 1] )
• 두 번째 방문 : i - 1 번 방을 두 번째 방문했으므로 1일 추가. ( + 1 )
• 정리하면, dp[i] = dp[i -1] + 1 + (dp[i - 1] - dp[nextVisit[i - 1]) + 1 = 2 * dp[i - 1] - dp[nextVisit[i - 1] + 2 이다.  

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

class Solution {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int n = nextVisit.length;
        int MOD = 1_000_000_007;

        // dp[i]는 방 0부터 i까지 모두 방문한 최소 날짜
        long[] dp = new long[n];
        dp[0] = 0;
        
        // dp[i] = dp[i - 1] + (dp[i - 1] - dp[nextVisit[i - 1]] + 1) + 1
        for (int i = 1; i < n; i++) {
            dp[i] = (2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2 + MOD) % MOD;
        }

        return (int) dp[n - 1];
    }
}

 

🔗 문제 링크

• LeetCode - First Day Where You Have Been in All the Rooms (링크)