[LeetCode][C++] 2255. Count Prefixes of a Given String

Table of Contents

• 문제
• 예제
• 할 일
• 상황 파악
• 계획
• 풀이
  • 1. 제출 답안
    • 리뷰
    • 코드
  • 2. 최소 런타임 샘플 답안
    • 리뷰
    • 코드
  • 3. 약간 수정해 제출한 답안
    • 리뷰
    • 코드

문제

원문 보기: [LeetCode] 2255. Count Prefixes of a Given String

words라는 문자열 배열과 s라는 문자열이 주어진다. words[i]와 s는 영어 소문자로만 이루어져 있다.

words에 있는 문자열 중 s의 접두사인 것의 개수를 반환하라.

접두사란 문자열의 앞에 나타나는 부분 문자열이다. 부분 문자열은 문자열에 포함된 연속한 문자들의 집합이다.

조건(Constraints):

• 1 <= words.length <= 1000
• 1 <= words[i].length, s.length <= 10
• words[i]와 s는 영어 소문자만을 포함한다.

예제

Example 1:

Input: words = ["a","b","c","ab","bc","abc"], s = "abc"
Output: 3
Explanation:
The strings in words which are a prefix of s = "abc" are:
"a", "ab", and "abc".
Thus the number of strings in words which are a prefix of s is 3.

Example 2:

Input: words = ["a","a"], s = "aa"
Output: 2
Explanation:
Both of the strings are a prefix of s. 
Note that the same string can occur multiple times in words, and it should be counted each time.

할 일

• 데이터를 그대로 옮겨적지 않고 필요한 방식에 맞게 활용하는 방법 고민
• 문제 파악 및 계획 시간과 코드 작성 시간 따로 재고 확인

* # 상황 파악 문단과 # 계획 문단은 문제를 풀 때 적은 그대로 썼음

상황 파악

1. 문자열 다루는 문제. 배열에 존재하는 문자열과 주어진 문자열의 앞에서부터 일부분이 일치하는지 확인하고 개수 세기.
2. 설마하니 모든 문자열을 직접 한글자씩 비교하게 만들지는 않았을 것이다. 어떻게 효율적으로 정보를 이용할 생각? 예시를 보건대 접두사라고 꼭 주어진 문자열보다 짧을 필요는 없고, 동일해도 된다. 비교해야 할 접두사의 개수는 최대 1000개.
3. 맵을 쓸까? 주어진 문자열을 앞에서부터 1글자, 2글자, 3글자… 씩 자른 문자열들을 글자 수에 따라 맵으로 만들어두고 배열에서 나오는 문자열마다 글자 수에 따른 값과 동일한지 비교한다. 당연히 주어진 문자열보다 긴 게 나오면 제외한다. 각 단어의 길이는 최대 10이니까 가능한 계획. 그리고 맵은 서치 속도가 빠르니까 메모리를 좀 손해보더라도 단어 길이가 길어져도 적용 가능할 것 같음.
4. 단어 배열을 정렬할 필요는 없을 것 같다. 그거 정렬하는 것보다 해시로 구현된 맵 쓰는 게 훨씬 낫겠다. 배열을 정렬하든 맵을 쓰든 주어진 문자열을 글자수만큼 잘라내는 연산은 똑같이 해야 하니까 고른다면 정렬이라도 안 하는 쪽이지.
5. 언어는? 파이썬은 문자열 다루기가 편하고 맵도 편하긴 한데 일단은 c++로 써보겠다. 내맘임.

계획

1. unordered_map과 정수 변수 준비. 맵은 부분 단어를 저장할 거고 정수 변수는 정답 개수 셀 용도.
2. s를 1글자부터 끝까지 앞에서부터 잘라서 맵에 저장, 키는 글자 수이고 값은 부분 문자열.
3. 배열을 순회하며 맵을 이용해 문자열이 일치하는지 비교, s보다 길면 바로 패스

풀이

문제 파악 및 계획 12분 25초
코드 작성 및 최초 정답 통과 6분 38초

1. 제출 답안

Runtime 30 ms, Beats 5.87%
Memory 12.1 MB, Beats 8.45%

리뷰

• 문제를 이해하고 풀이하는 데 걸린 시간은 그럭저럭 볼만하게 나왔지만 쉬운 문제라 그닥 짧은 시간도 아닌 것 같다.
• 나는 나름 생각한다고 한 건데 내 런타임이 5%밖에 안 된다는 점에서 별로 즐겁지는 않았다.
• 데이터 활용에 집중하느라 기본 함수 활용을 까먹다니

코드

#include <unordered_map> // map으로 잘못 알고 있었음
using namespace std;

class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        unordered_map<int, string> dict;
        int cnt = 0; // 정답 개수
        int len = s.length();

        for (int i = 1; i <= len; i++)
            dict[i] = s.substr(0, i);

        for (auto& word : words) {
            int word_len = word.length();

            if (word_len > len)
                continue;
            else if (word == dict[word_len])
                ++cnt;
        }

        return cnt;
    }
};

2. 최소 런타임 샘플 답안

Runtime 0 ms

리뷰

• 배열을 순회하면서 매번 s에서 find로 부분 문자열을 찾는 방식으로 풀이했다.
• 아니 부분 문자열을 미리 잘라놓고 비교하는 것보다 배열 길이만큼 매번 find하는 게 더 빠르다고?
• 다른 상위 런타임 답안도 대체로 매번 문자열을 자르는 풀이로 썼다. 아니 미리 잘라서 저장해두는 게 더 오래 걸린다고? 그래봐야 30ms 이하로 차이나는 것 뿐이지만.

코드

* 임의로 불필요한 주석과 공백을 지웠음

class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        int counter = 0;
        for (auto word : words) {
            if (s.find(word) == 0) {
                counter++;
            }
        }
        return counter;
    }
};

3. 약간 수정해 제출한 답안

Runtime 8 ms, Beats 82.74%
Memory 12 MB, Beats 68.79%

리뷰

• 생각보다 변수 정의는 런타임을 많이 잡아먹는다는 것을 알았다. 사람이 보기 좋으라고 만들었던 변수 몇 개를 지우고 똑같이 제출해봤는데 꽤 차이났다.
• 다음 문제 풀이부터 잘 고려해보겠음.
• 사실 먼저 제출했던 답안의 결과에 미련이 남아서 혹시 이거라도, 하고 제출했던 답안인데 의외의 결과가 나와서 배우긴 배웠지만 별로 즐겁지는 않음.

코드

#include <unordered_map>
using namespace std;

class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        unordered_map<int, string> dict;
        int cnt = 0; // 정답 개수

        for (int i = 1; i <= s.length(); i++)
            dict[i] = s.substr(0, i);

        for (auto& word : words) {
            if (word.length() > s.length())
                continue;
            else if (word == dict[word.length()])
                ++cnt;
        }

        return cnt;
    }
};