M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 354 - Russian Doll Envelopes

최대 1 분 소요

문제

leetcode 354 - Russian Doll Envelopes 풀러가기

문제 분석

쉽게 생각하면, 러시아의 전통 인형인 마트료시카에 인형을 최대로 넣을 수 있는 수를 구하는 것이다.

한 인형에 대해, 그 인형 안에 들어가는 최대 수는 항상 같으므로 dynamic programming을 이용한다.

문제 풀이(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
    29
    30
    31
    32
    33
    34
    class Solution {
    public:
        int maxEnvelopes(vector<vector<int>>& envelopes) {
            
            if(envelopes.empty()){
                return 0;
            }
     
            sort(envelopes.begin(), envelopes.end(), [](vector<int> u, vector<int> v){
                if(u[0]==v[0]){
                    return u[1]<v[1];
                }else{
                    return u[0] < v[0];
                }
            });
            
            int ans = 0;
            
            vector<int> d(envelopes.size(), 1);
        
            for(int i=0;i<envelopes.size();i++){
                for(int j=0;j<i;j++){
                    if(envelopes[i][0] != envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){
                        d[i] = max(d[i], d[j]+1);
                    }
                }
                if(ans<d[i]){
                    ans = d[i];
                }
            }
            
            return ans;
        }
    };
    		cs
    • 9번째 줄 : 오름차순으로 인형들을 정렬한다. width가 같은 경우에 대해선 height를 오름차순으로 정렬한다.
    • 19번째 줄 : 현재 인형까지의 최대 값에 대한 정보를 가지고 있는 배열을 만든다.
    • 21~30번째 줄 : 현재 인형과, 현재 인형 이전의 인형들(인형들을 오름차순으로 정렬 했으므로 현재 인형 이전의 인형들은 현재 인형보다 width나 height가 작다.)을 비교하여
      • width가 다르면서, height는 현재 인형보다 작은 인형 j의 최대값 d[j]에 +1을 한 값과 현재 d[i]를 비교하여 더 큰 값을 d[i]에 넣어준다.(j가 반복되는 동안 d[i]는 계속 바뀌므로 d[i], d[j]+1을 비교해준다.)
      • 27번째 줄 : 현재 인형의 최대값이 전체 최대값 보다 크다면, 전체 최대값을 바꿔준다.

    Runtime: 1628 ms, faster than 9.21% of C++ online submissions for Russian Doll Envelopes.

    Memory Usage: 51.2 MB, less than 5.28% of C++ online submissions for Russian Doll Envelopes.

    사실 처음에는 재귀를 이용하는 방법으로 구현도 해봤는데, 85개의 test case 중 68번째에서 time limit exceed가 걸려서 위의 방법으로 바꿨다.






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

댓글남기기

참고