383. Ransom Note

 

https://leetcode.com/problems/ransom-note/

Ransom Note - LeetCode

문제 이해

ransomNote의 있는 문자열이 개별 요소가 magazine 문자열에 모두 포함되는지 확인하는 문제

 

Bruth-force 풀이

ransomeNote, magazine 문자열의 방문 여부를 판단하는 array를 하나 만들고 전체 탐색을 하여 모두 다 방문했는지 못했는지 판단하는 방법으로 1차 풀이는 아래 코드와 같다.

bool canConstruct(string ransomNote, string magazine) {
	
	int size = magazine.size();
	vector<bool> vis_ransom(ransomNote.size());
	vector<bool> vis_magazine(magazine.size());
	for (int i = 0; i < ransomNote.size(); i++) {
		char ch = ransomNote[i];
		for (int j = 0; j < size; j++) {
			if (vis_ransom[i] || vis_magazine[j]) {
				continue;
			}

			if (ch == magazine[j]) {
				vis_ransom[i] = true;
				vis_magazine[j] = true;
			}

		}
	}

	bool ok = true;
	for (int i = 0; i< vis_ransom.size(); i++) {
		if (false == vis_ransom[i]) {
			ok = false;
			break;
		}
	}

	return ok;
}

 

위 코드의 수행 속도는 1200 ms 나온다. 2 중 반복문 + 1 반복문 On^2 + On의 수행 결과가 나온다.

문제에서 주어진 조건은 a~z 알파벳 범위 내에서 문자열이 들어서 오는 것을 힌트 삼아 재 풀이하도록 한다.

 

배열 인덱싱을 활용한 풀이

 알파벳 범위 만큼 배열 선언한다.

magazine의 문자열을 순회하면서 각 알파벳의 개수를 기록하고, ransomenote의 문자열을 순회하면서 각 알파벳의 개수를 감소한다. 순회하면서 arr 배열의 값이 0 이면 모두 포함하지 못한다고 판정한다.

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {

        int arr[27] = { 0 };
        const int aindex = static_cast<int>('a');
        for (char c : magazine)
        {
            ++arr[static_cast<int>(c) - aindex];
        }
        for (char c : ransomNote)
        {
            if (arr[static_cast<int>(c) - aindex] == 0)
                return false;
            --arr[static_cast<int>(c) - aindex];
        }
        return true;
    }
};

 

Runtime: 28 ms, faster than 55.89% of C++ online submissions for Ransom Note.

Memory Usage: 10.9 MB, less than 100.00% of C++ online submissions for Ransom Note.