M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 75 - Sort Colors

1 분 소요

문제

75 - Sort Colors 풀러가기

문제 분석

이 문제는 c++의 algorithm 내의 sort를 이용하면 간단하게 해결 가능하다.

하지만, sort를 사용하지 않고 풀어보겠다.

문제 풀이(C++)

  1. 전체 코드(deque 이용)

    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
    #include <deque>
     
    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            deque<int> d1;
            deque<int> d2;
            
            for(int i=0;i<nums.size();i++){
                switch(nums[i]){
                    case 0:
                        d1.push_front(0);
                        break;
                    case 1:
                        d1.push_back(1);
                        d2.push_back(1);
                        break;
                    case 2:
                        d2.push_front(2);
                        break;
                }
            }
            for(int i = 0;i<d1.size();i++){
                nums[i] = d1[i];
            }
            for(int i = 0;i<d2.size();i++){
                if(d2[i] == 1){
                    break;
                }
                nums[i+d1.size()] = d2[i];
            }
        }
    }
    		cs

    • 이 방법은 deque를 이용했다. deque 두개를 이용해서

      • d1은 0이면 앞, 1이면 뒤
      • d2는 1이면 뒤, 2면 앞

      으로 넣도록 했다.

    • 23번째 줄 ~ : d1과 d2의 값을 결과 set인 nums에 넣어준다. 이때, d2를 이용해서 값을 넣어주는 경우에는 1이 들어오는 경우 반복문을 중단한다.

    Runtime: 4 ms, faster than 54.01% of C++ online submissions for Sort Colors.

    Memory Usage: 8.8 MB, less than 69.32% of C++ online submissions for Sort Colors.

  2. 전체 코드(map 이용)

    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
    #include <map>
     
    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            
            // 여기에 
     
            for(int i=0;i<nums.size();i++){
                m[nums[i]]++;
            }
            
            for(int i=0;i<nums.size();i++){
               while(i<m[0]){
                   nums[i] = 0;
                   i++;
               }
                while(i<m[0]+m[1]){
                    nums[i] = 1;
                    i++;
                }
                while(i<m[0]+m[1]+m[2]){
                    nums[i] = 2;
                    i++;
                }
            }
            
        }
    };
    		cs
    • 이 방법은 map을 이용하였다. 0,1,2라는 것을 index로 사용하는 것에 집중하다 보니 map을 사용했는데 int 값이니까 그냥 배열을 이용해도 된다….ㅎ * 7번째 줄에 map<int, int> m = 0,{1,0},2; 을 추가해야 된다. 이걸 추가 한 채로 코드를 업로드하니 블로그 생성에서 오류가 나서 뺌….
      • 근데 이것도 0가 되야 된다고 오류 나서 저렇게 했는데, {0,0},{1,0},{2,0} 을 중괄호 사이에 넣어야 한다.

Runtime: 4 ms, faster than 54.01% of C++ online submissions for Sort Colors.

Memory Usage: 8.8 MB, less than 69.32% of C++ online submissions for Sort Colors.

결과는 앞과 동일하다.






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

댓글남기기

참고