[Leetcode] Biweekly Contest 48 후기 및 풀이

in Problem Solving on Leetcode


Contest : Leetcode - Biweekly Contest 48

Solution code : Github

Biweekly Contest 48 후기

3번째 콘테스트입니다. 이번에는 4문제 중 3문제를 PASS 하였습니다. 그런데 난이도가 높은 4번째 문제는 풀었는데 오히려 3번째 문제를 못 풀었습니다. 3번 문제는 계속 복잡도가 큰 방법밖에 안떠올라서 결국 Discuss 봤는데 아이디어에 감탄했습니다. 또 고수분의 도움으로 다행히 모든 풀이가 가능했습니다.

이제 솔루션을 적어봅니다.

문제 1. Second Largest Digit in a String

문제

문자와 숫자가 섞인 문자열 s가 주어집니다. s에서 숫자 중 2번째로 큰 숫자가 무엇인지 찾아내는 문제입니다. 만약 2번째로 큰 숫자가 없으면 -1을 출력하면 됩니다.

풀이

문자열에서 숫자만 필터링하여 숫자가 1개 이하면 -1이고 그 외에는 2번째 큰 숫자를 출력하면 됩니다.

  • Time : O(N)
  • Space : O(1)
  • Tag : Greedy

C++

class Solution {
public:
	int secondHighest(string s) {
		int cnt[10] = { 0, };
		for (int i = 0; i < s.size(); i++)
		{
			if ('0' <= s[i] && s[i] <= '9')
				cnt[s[i] - '0']++;
		}

		int exist = 1;
		for (int i = 9; i >= 0; i--)
		{
			if (cnt[i] != 0)
			{
				if (exist > 0) exist--;
				else return i;
			}
		}
		return -1;
	}
};

문제 2. Design Authentication Manager

문제

인증시스템을 만든다고 가정하고 여러 가지 기능을 구현하는 문제입니다. 인증 토큰을 만들면 currentTime 부터 timeToLive 후에 만료됩니다. 이 토큰들을 관리하기 위한 아래 기능을 구현하면 됩니다.

  • AuthenticationManager(int timeToLive) : timeToLive 값 설정
  • generate(string tokenId, int currentTime) : currentTime에 tokenId가 토큰 생성
  • renew(string tokenId, int currentTime) : currentTime에 tokenID의 토큰 세션 갱신 (현재 기준 재생성)
  • countUnexpiredTokens(int currentTime) : currentTime 기준 전체 토큰의 개수 반환

풀이

tokenId의 개수와 countUnexpiredTokens() 기능을 고려할 때 Key는 tokenId, Value는 만료시간을 Dictionary로 구성하면 됩니다.

전체 Function call 수가 최대 2000개로 아주 적기 때문에 단순 구현해도 됩니다.

  • Time : O(1)
  • Space : O(N) (N은 토큰 개수)
  • Tag : HashTable Greedy

C++

class AuthenticationManager {
public:
	map<string, int> tokens;
	int X;

	AuthenticationManager(int timeToLive) {
		X = timeToLive;
	}

	void generate(string tokenId, int currentTime) {
		tokens[tokenId] = currentTime + X;
	}

	void renew(string tokenId, int currentTime) {
		map<string, int>::iterator pos = tokens.find(tokenId);
		if (pos != tokens.end())
		{
			if (pos->second <= currentTime) tokens.erase(tokenId);
			else pos->second = currentTime + X;
		}
	}

	int countUnexpiredTokens(int currentTime) {
		vector<map<string, int>::iterator> eraseList;
		for (map<string, int>::iterator it = tokens.begin(); it != tokens.end(); it++)
			if (it->second <= currentTime) eraseList.push_back(it);

		for (int i = 0; i < eraseList.size(); i++) tokens.erase(eraseList[i]);

		return tokens.size();
	}
};

문제 3. Maximum Number of Consecutive Values You Can Make

문제

정수형 배열인 N개의 coins 가 주어집니다. 이 N개의 coins를 자유롭게 사용하여 합을 X를 만들 수 있습니다. 합을 0부터 시작하여 연속적인 값을 최대 몇개까지 만들 수 있는지 찾는 문제입니다.

단, coins에서 같은 값을 가진 코인이 있을 수도 있습니다.

풀이

먼저 X = 0 은 모든 경우에 만들 수 있습니다. 우리는 coins를 이용하여 X가 몇까지 가능한지 판단해야 합니다. 숫자를 연속적으로 만들 수 있는지 확인하기 위해서 가장 작은 coin부터 사용하기 위해 N개의 coins를 정렬합니다.

현재까지 X를 만들 수 있다고 가정할 때, coins[i]를 사용하여 X+1를 만들 수 있으려면 (X + 1 - coins[i]) >=0 이어야 합니다. X + 1 < coins[i] 이면 X+1을 만들 수 없고, 그 외 경우에는 X + coins[i] 만큼은 반드시 만들 수 있습니다. 이것을 인덱스 i를 0부터 n-1까지 반복하면 됩니다.

  • Time : O(N)
  • Space : O(1)
  • Tag : Greedy

C++

class Solution {
public:
	int getMaximumConsecutive(vector<int>& coins) {
		int ans = 0;
		sort(coins.begin(), coins.end());

		for (int i = 0; i < coins.size(); i++)
		{
			if (ans + 1 < coins[i])
				return ans + 1;
			else
				ans += coins[i];
		}
		return ans + 1;
	}
};

문제 4. Maximize Score After N Operations

문제

정수형 배열 nums 가 주어집니다. nums 의 크기는 2*n 이고 n번의 아래와 같은 동작을 해야 합니다.

i 번째 동작(1부터 시작):

  1. nums에서 임의의 값 x와 y을 선택
  2. i * GCD(x, y)의 점수를 얻음
  3. nums에서 x 와 y의 값을 삭제

n번의 동작을 수행한후 얻을 수 있는 전체 점수의 최대값을 계산하는 문제입니다.

여기서 GCD(x, y) 는 x와 y 의 최대공약수 입니다.

풀이

먼저 최대공약수를 구하는 것은 유클리드 호제법을 보시고 여기서는 생략합니다.

가장 쉬운 방법인 DFS를 사용하여 전체 경우를 탐색하면 쉽게 최대값을 계산가능 합니다. 다만 n의 값이 최대 7이므로, 경우의 수가 (14C2 * 12C2 * 10C2 ...)로 TLE가 발생합니다.

중복되는 부분문제가 많으므로 다음과 같은 Bitmask DP를 이용하면 됩니다.

dp[state][i] : i번째까지 동작을 수행했고, nums의 인덱스 사용여부 state일 때 점수의 최대값
dp[state][i] = max(dp[state & ~(1<<x) & ~(1<<y)] + i*GCD(x,y)) where (x, y) not in prestate
  • Time : O(2^(2N)*N)
  • Space : O(2^(2N)*N)
  • Tag : Bitmask DP

C++

class Solution {
public:
	int size;
	int d[100000];
	int gcd[14][14];
	int visit[14];
	int ans = 0;

	int GCD(int a, int b)
	{
		if (b == 0) return a;
		else return GCD(b, a%b);
	}

	int F(int state)
	{
		if (state == (1 << size) - 1)
			return 0;

		int& ref = d[state];
		if (ref != -1) return ref;

		int cnt = 0;
		for (int i = 0; i < size; i++) if (state & (1 << i)) cnt++;
		cnt /= 2;

		ref = 0;
		for (int i = 0; i < size; i++)
		{
			if (state & (1 << i)) continue;
			for (int j = i + 1; j < size; j++)
			{
				if (state & (1 << j)) continue;

				state |= (1 << i);
				state |= (1 << j);
				ref = max(ref, F(state) + (cnt + 1)*gcd[i][j]);
				state &= ~(1 << i);
				state &= ~(1 << j);
			}
		}
		return ref;
	}

	int maxScore(vector<int>& nums) {
		for (int i = 0; i < 100000; i++) d[i] = -1;

		size = nums.size();
		for (int i = 0; i < size; i++)
			for (int j = i + 1; j < size; j++)
				gcd[i][j] = GCD(nums[i], nums[j]);

		return F(0);
	}
};