M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 957 - Prison Cells After N Days

최대 1 분 소요

문제

leetcode 957 - Prison Cells After N Days 풀러가기

문제 분석

이 문제는 감옥 i의 양쪽이 1,1이거나 0,0일 때 i가 1로 채워지는 문제다.

문제 해결 방식만 보면 단순하다고 생각할 수 있으나, N(날짜의 수)이 커지면 복잡도가 증가한다는 문제가 있다.

그래서 이 문제의 핵심은 이 복잡도를 해결하는 것에 있다.

이 문제의 경우에는 복잡도를 해결하기 위해 cycle을 이용하면 된다.

즉, 방이 차 있는 상태가 특정 주기로 반복된다는 것이다.

문제 풀이(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    public:
        vector<int> prisonAfterNDays(vector<int>& cells, int N) {
            
            vector<vector<int>> record; 
            int cycle;
            
            while(N--){
                    vector<int> temp(8,0);
                    for(int j=1;j<7;j++){
                        if(cells[j-1] == cells[j+1]){
                            temp[j] = 1;
                        }
                    }
                    
                    if(record.size() && record.front() == temp){
                        cycle = record.size();
                        cells = record[N%cycle];
                        break;
                    }else{
                        record.push_back(temp);
                    }
                    cells = temp;
                
            }
            return cells;
        }
    };
    		cs
    • 8번째 줄 : 날이 반복되는 만큼 반복문을 진행한다. N<cycle이면 cycle을 찾기 전에 답을 찾게 되고, N>cycle이면 cycle을 이용하여 답을 찾게 된다.
    • 9 ~ 10 번째 줄 : 0번째 날이 지나면, 양 끝 감옥은 0이 된다. 왜냐하면 양쪽이 1이거나 양쪽이 0인 경우에 1이 되는데, 양 끝 감옥은 양쪽 값을 가질 수 없기 때문이다. 그래서 1번 감옥과 6번 감옥까지의 값을 구한다.
    • 21번째 줄 : cycle을 찾을 때 까지, 감옥의 상태를 계속해서 저장한다.
    • 16번째 줄 : 현재 감옥의 상태와 저장된 감옥의 상태 중 첫번째 요소와 같다면, cycle을 찾은 것이다. 따라서, cells에 알맞은 값을 넣고 반복문을 중단한다.

    참고 블로그






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고