홈 [LeetCode][c++, py] 944. Delete Columns to Make Sorted
포스트
취소

[LeetCode][c++, py] 944. Delete Columns to Make Sorted

게시 2023-01-03
By dapin1490
11 분읽는 시간

Table of Contents

문제

원문 보기 : [LeetCode] 944. Delete Columns to Make Sorted

모두 같은 길이인 n개의 문자열을 갖는 배열 strs가 주어진다.

한 줄에 문자열을 하나씩 놓아 배열을 만들 수 있다. 예를 들어 strs = ["abc", "bce", "cae"]라면 다음과 같다.

abc
bce
cae

사전순으로 정렬되지 않은 열을 지우고 싶다. 위의 예시에서(인덱스는 0부터 시작), 0번 열 ('a', 'b', 'c')와 2번 열 ('c', 'e', 'e')는 정렬되어 있지만 1번 열 ('b', 'c', 'a')는 그렇지 않다. 고로, 1번 열을 지워야 한다.

지워야 하는 열의 개수를 반환하라

조건(Constraints):

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 1000
  • strs[i]는 영어 소문자로 구성된다.

예제

Example 1:

1
2
3
4
5
6
7

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: The grid looks as follows:
  cba
  daf
  ghi
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Example 2:

1
2
3
4
5
6

Input: strs = ["a","b"]
Output: 0
Explanation: The grid looks as follows:
  a
  b
Column 0 is the only column and is sorted, so you will not delete any columns.

Example 3:

1
2
3
4
5
6
7

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: The grid looks as follows:
  zyx
  wvu
  tsr
All 3 columns are not sorted, so you will delete all 3.

계획

  1. 상황 파악
    주어지는 문자열들을 세로로 놓고, 세로 읽기를 해서 사전순이 아닌 열을 찾으면 된다.
  2. 어떻게 할 수 있을까
    1. 문제의 설정에 충실하게 모든 문자를 진짜 이차원 배열에 넣고 확인한다 : 굳이 안 해도 반복문으로 충분히 함
    2. 이중 반복문을 잘 써서 각 문자열을 세로로 읽게 하고, 아스키 코드 값이 증가하는지 확인한다.
  3. 더 자세한 계획
    1. 답으로 반환할 정수 변수를 준비한다. 개수를 세는 것이므로 0으로 초기화한다.
    2. 문자열은 어차피 배열로 주어지니 파싱할 필요가 없고, 배열의 총 크기와 개별 문자열의 길이를 찾아 반복문을 구성한다. 행 인덱스와 열 인덱스의 반복문 위치를 서로 바꾸어 세로로 읽게 하는 게 중요하다.
    3. 매 반복마다 이전 문자와의 비교를 해야 하므로 열 인덱스는 1부터 시작한다. 앞 문자와 아스키 코드 값을 비교해 지금 문자가 더 큰지 확인한다.
    4. 이전 문자보다 작은 경우가 발견되면 정답 변수를 1 증가시키고 다음 열로 넘어가게 한다(break). 이때 같은 열을 중복해서 세지 않아야 한다.
    5. 반복이 끝나면 정답 반환.
  4. 어떤 언어를 쓸까 : cpp나 파이썬이나 이번 문제에서는 비슷하게 쓸 수 있으니 못고르겠다. 둘 다 쓴다.
  5. 최소 런타임 샘플 답안 보기

풀이

1. 이중 반복문

리뷰

  1. 내가 가장 먼저 생각해내는 풀이가 항상 그렇듯 흔하고 쉽게 생각할 수 있는 풀이였던 것 같다. 정답은 당연히 나오겠지만 속도와 메모리는 다른 답안에 비해 낮은 편. 파이썬은 메모리는 적은 편으로 나오긴 했지만 전체적으로 범위가 좁아 큰 의미는 없을 것으로 보인다.
  2. 근데 그럼 이걸 어떻게 빠르게 할 수 있는지? 뭘 써야 하는데?
  3. 일단 C++ 최소 런타임 답안을 봤는데 내 답이랑 크게 다른 건 없고 int() 유무만 달라서 그걸 빼고 다시 제출해봤는데, 런타임이 대략 1/3 정도로 줄었다. int() 연산이 생각보다 시간을 많이 쓰는 것 같다.

C++ (1)

Runtime : 127 ms, Beats 33.33%
Memory : 12.3 MB, Beats 30.23%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int answer = 0;
        int row = strs.size();
        int col = strs[0].length();

        for (int i = 0; i < col; i++) {
            for (int j = 1; j < row; j++) {
                if (int(strs[j - 1][i]) > int(strs[j][i])) { // 이 부분에서 int()를 빼고 쓰면 런타임이 49 ms로 줄어든다
                    ++answer;
                    break;
                }
            }
        }

        return answer;
    }
};

python (1)

Runtime : 596 ms, Beats 14.6%
Memory : 14.5 MB, Beats 90.63%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def minDeletionSize(self, strs):
        """
        :type strs: List[str]
        :rtype: int
        """
        answer = 0
        row = len(strs)
        col = len(strs[0])

        for i in range(0, col):
            for j in range(1, row):
                if strs[j - 1][i] > strs[j][i]:
                    answer += 1
                    break

        return answer

2. 최소 런타임 샘플 답안

C++ (2)

Runtime : 32 ms

리뷰

  1. 내 답안과 크게 다르지 않다(풀이 생략). int()를 사용하지 않은 것과 앞에서 뒤로 비교한 것이 차이이다.
  2. 내가 int()를 사용하지 않고 낸 답안과 런타임이 17 ms 차이난다. 이 정도 차이는 그냥 때에 따라 달라지는 오차 정도인가?(몰라서 하는 말임)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int count = 0;
        int n = strs.size(), m = strs[0].size();
        for(int i=0; i<m; i++){
            for(int j=0; j<n-1; j++){
                if(strs[j][i]>strs[j+1][i]){
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};

python (2)

몇 가지 배울 점이 있어서 풀이를 2개 가져왔다. 논리는 동일하니 한번에 풀이하겠다.

풀이

  1. 문자열을 열 단위로 가져온다.
  2. 열 단위 문자열 그대로인 것과, 이를 정렬한 것을 비교해 서로 다르면 정답을 증가시킨다.

첫 번째 예시
Runtime : 71 ms

리뷰

  1. 이 답안에서 볼 부분은 zip(*strs)이다. 참고 자료 [1]을 참고하여 무슨 코드인지 배워왔다. *이 붙은 strs가 iterable하다는 전제 하에, *을 붙여서 zip() 함수에 입력하면 *args로 전달되어 자동으로 열끼리 엮을 수 있다고 한다.
  2. *args는 가변 매개변수이다. 입력받을 값의 개수가 정해지지 않은 경우에 사용한다. 참고 자료 [1]에 의하면 튜플 형태로 전달된다고 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def minDeletionSize(self, strs):
        """
        :type strs: List[str]
        :rtype: int
        """

        ret = 0

        for c in zip(*strs):
            if list(c) != sorted(c):
                ret += 1

        return ret

두 번째 예시
Runtime : 108 ms

리뷰

  1. 이 답안은 첫 번째 답안보다 풀이를 이해하기가 쉬울 것 같아 가져왔다.
  2. 문자열을 열 단위로 가져오는 부분에서 리스트 컴프리헨션을 사용했고, 한 글자씩 비교하지 않고 정렬한 다음 한번에 비교했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def minDeletionSize(self, A):
        """
        :type strs: List[str]
        :rtype: int
        """
        res = 0
        for i in range(len(A[0])):
            tmp = [ele[i] for ele in A]
            tmp_sort = sorted(tmp)
            if tmp !=tmp_sort:
                res+=1

        return res

C++과 python의 차이?

cpp 풀이에서는 글자를 정렬하지 않고 하나씩 비교했지만, 파이썬 풀이에서는 글자를 정렬한 다음 통째로 비교했다. 왜 이렇게 다른 논리를 사용했을까? 분명 파이썬과 cpp의 실행 방식(컴파일러/인터프리터)이나 메모리 이용 방식의 차이에 따른 것으로 보이는데, 이걸 뭐라고 해야 할지는 모르겠다. chatGPT에게 물어봤지만 내가 원하는 대답은 듣지 못했다.

내가 생각할 수 있는 건 cpp는 정렬하는 것보다 글자를 하나씩 읽는 게 더 빠르고, 파이썬은 하나씩 읽느니 다 가져와서 정렬하는 게 더 빠르다는 것뿐이다. 이건 표면적인 차이이고 내가 알고 싶은 건 왜 저런 차이가 생기는지이다.. 쉽지 않네.

참고 자료

IT, 문제풀이
지식 IT LeetCode 릿코드 문제풀이
이 기사는 저작권자의 CC BY-NC-ND 4.0 라이센스를 따릅니다.
최근 업데이트
바로가기