[Leetcode] Weekly Contest 237 후기 및 풀이

Contest : Leetcode - Weekly Contest 237

Solution code : Github

Weekly Contest 237 후기

오랜만에 4문제 모두 PASS 했습니다. 개인적으로는 3번 문제가 신경쓸 부분이 좀 있어서 고민하는데 시간이 좀 걸렸고, 4번 문제가 오히려 난이도가 더 낮았던 것 같습니다. 1번은 단순 문자열 처리, 2번은 정렬, 3번은 힙 문제였으며 4번은 비트 연산에 대한 생각을 조금 해보면 풀 수 있었습니다.

문제 1. Check if the Sentence Is Pangram

문제

소문자로만 이루어진 문자열 sentence가 주어집니다. sentence 에서 소문자 알파벳 26개가 모두 최소 한번씩은 포함되어 있는 문자열인지 판단하는 문제입니다.

제약 조건:

1 <= sentence.length <= 1000

풀이

소문자 알파벳 26개가 모두 문자열에 포함되어 있는지 확인하면 됩니다.

Time : O(N) [N: sentence.length]
Space : O(1)
Tag : String

C++

class Solution {
public:
	bool checkIfPangram(string sentence) {
		int c[26] = { 0, };
		for (int i = 0; i < sentence.size(); i++)
			c[sentence[i] - 'a'] = 1;
		
		int sum = 0;
		for (int i = 0; i < 26; i++)
			sum += c[i];
		return sum == 26;
	}
};

Python

class Solution(object):
    def checkIfPangram(self, sentence):
        c = [0]*26
        for ch in list(sentence):
            c[ord(ch) - ord('a')] = 1
        
        return True if sum(c) == 26 else False

문제 2. Maximum Ice Cream Bars

문제

n개의 정수형 배열인 costs와 정수 값 coins가 주어집니다. costs는 n개의 아이스크림 가격을 의미하며 주어진 coins 으로 아이스크림을 구매할 수 있는 최대 개수를 구하는 문제입니다.

제약 조건:

costs.length == n
1 <= n <= 10^5
1 <= costs[i] <= 10^5
1 <= coins <= 10^8

풀이

아이스크림 가격을 오름차순으로 정렬한 후에 가장 저렴한 것부터 구매하면 됩니다.

Time : O(NlogN) [N : costs.length]
Space : O(1)
Tag : Greedy, Sort

C++

class Solution {
public:
	int maxIceCream(vector<int>& costs, int coins) {
		sort(costs.begin(), costs.end());
		int res = 0;
		for (int i = 0; i < costs.size(); i++)
		{
			if (coins < costs[i]) break;
			coins -= costs[i];
			res++;
		}
		return res;
	}
};

Python

class Solution(object):
    def maxIceCream(self, costs, coins):
        res = 0
        for x in sorted(costs):
            if(x > coins):
                break
            coins -= x
            res += 1
        return res

문제 3. Single-Threaded CPU

문제

N개의 작업이 주어집니다. 이 작업은 tasks[i] = [enqueueTime(i), processingTime(i)] 형태로 주어지며 모두 정수값입니다. enqueueTime은 이 시간부터 작업을 시작할 수 있고, processingTime은 작업을 마치기 위해 필요한 소요시간을 의미합니다.

이때 아래와 같은 single-threaded CPU 를 만들어야 합니다.

CPU가 Idle 상태에서 작업할 task가 없으면 아무런 처리를 하지 않습니다.
CPU가 Idle 상태에서 작업할 수 있는 tasks 중에서 가장 작은 processing Time를 가진 task 부터 처리합니다.
하나의 task를 시작하면 작업이 끝날때까지 그 작업만 처리합니다.
CPU가 task를 완료한 즉시 바로 다른 task를 시작할 수 있습니다.

제약 조건:

tasks.length == n
1 <= n <= 10^5
1 <= enqueueTime(i), processingTime(i) <= 10^9

풀이

CPU가 현재 시간 기준으로 작업가능한 task를 파악하기 위해 enqueueTime 순으로 정렬합니다. 단 작업번호를 출력해야하기 때문에 작업번호를 넣습니다.

또한 작업 가능한 tasks에서 processingTime 이 가장 작은 작업부터 진행해야 되기 때문에 이를 Min-heap 으로 구성합니다.

이제 우선순위가 가장 높은 작업을 하나씩 처리하면서 현재시간을 업데이트하기만 하면 됩니다. 추가로 현재 시간에 하나도 작업할 수 없는 경우에는 바로 다음 enqueueTime으로 이동해야 하는 예외처리를 해주어야 합니다.

Time : O(NlogN), [N : tasks.length]
Space : O(N)
Tag : Heap

C++

class Solution {
	struct task
	{
		int i;
		int pTime;
		bool operator < (const task& rhs) const
		{
			if (pTime == rhs.pTime) return i > rhs.i;
			else return pTime > rhs.pTime;
		}
	};

public:
	vector<int> getOrder(vector<vector<int>>& tasks) {
		for (int i = 0; i < tasks.size(); i++) tasks[i].push_back(i);
		sort(tasks.begin(), tasks.end());

		priority_queue<task> available;
		vector<int> res;
		long long cT = 1, i = 0;
		while (available.size() != 0 || i < tasks.size())
		{
			while (i < tasks.size() && (long long)tasks[i][0] <= cT)
			{
				available.push({ tasks[i][2], tasks[i][1] });
				i++;
			}
            
            if (available.size() == 0)
            {
                cT = tasks[i][0];
                continue;
            }

			task top = available.top(); available.pop();
			res.push_back(top.i);
			cT += top.pTime;
		}
		return res;
	}
};

Python

class Solution(object):
    def getOrder(self, tasks):
        tasks = sorted([(v[0], v[1], i) for i, v in enumerate(tasks)])
        
        available = []
        res = []
        cT, i = 1, 0
        while len(available) != 0 or i < len(tasks):
            while i < len(tasks) and tasks[i][0] <= cT:
                heapq.heappush(available, (tasks[i][1], tasks[i][2]))
                i += 1
                
            if len(available) == 0:
                cT = tasks[i][0]
                continue
            
            pT, idx = heapq.heappop(available)
            res.append(idx)
            cT += pT
            
        return res

문제 4. Find XOR Sum of All Pairs Bitwise AND

문제

2개의 정수형 배열 arr1과 arr2가 주어집니다. 모든 가능한 (i, j) 쌍에 대하여 arr1[i] & arr2[j]인 값으로 구성된 배열을 만듭니다. 즉 arr1.length * arr2.length 크기의 배열이 만들어 집니다. 이때 이 생성된 배열의 XOR sum 값을 구하는 문제입니다.

여기서 XOR sum은 배열의 모든 element를 bitwise-XOR한 값입니다.

제약 조건:

1 <= arr1.length, arr2.length <= 10^5
0 <= arr1[i], arr2[j] <= 10^9

풀이

먼저 a1 & (b1^b2) = (a1&b1) ^ (a1&b2) 임을 알 수 있습니다. 조금 더 확장하면 (a1^a2) & (b1^b2) = (a1^b1) & (a1^b2) & (a2^b1) & (a2^b2) 입니다.

문제에서 구하고자 하는 것은 (xorsum of arr1) AND (xorsum of arr2)와 같은 값임을 알 수 있습니다.

Time : O(N + M) [N : arr1.length, M: arr2.length]
Space : O(1)
Tag : Bit Manipulation Greedy

C++

class Solution {
public:
	int getXORSum(vector<int>& arr1, vector<int>& arr2) {
		int xor1 = 0, xor2 = 0;
		for (int i = 0; i < arr1.size(); i++)
			xor1 ^= arr1[i];
		for (int i = 0; i < arr2.size(); i++)
			xor2 ^= arr2[i];
		return xor1 & xor2;
	}
};

Python

class Solution(object):
    def getXORSum(self, arr1, arr2):
        xor1 = xor2 = 0
        for x in arr1:
            xor1 ^= x;
        for y in arr2:
            xor2 ^= y
        return xor1 & xor2
        