청정알고리즘

문제

https://codeforces.com/contest/1150/problem/D

풀이

3차원 dp를 이용하여 해결한다.

쿼리 형의 문제가 아니라 일반적인 DP라고 생각하고, 모든 문자가 미리 다 들어와있다고 가정하고 문제를 먼저 풀자.

$dp(i,j,k)$ = 1번, 2번 3번 religion description이 각각 i글자, j글자, k글자일 때, 필요한 Word of Universe의 최소길이

라고 정의하자. 

그러면 $dp(i,j,k)$는 $dp(i-1,j,k)$에서 한글자가 추가된 경우와, $dp(i,j-1,k)$에서 한글자가 추가된 경우, $dp(i,j,k-1)$에서 한글자가 추가된 경우. 이 세가지의 경우 중에서 가장 작은 경우의 답이 된다.

각 케이스는 서로 대칭이므로 첫 번째 케이스만 보자.

현재 $dp(i-1,j,k)$만큼의 Word of Universe를 사용하고 있다.

이 때 새로운 글자 c가 추가될 때 $dp(i,j,k)$는 Word of Universe 위에서 $dp(i-1,j,k)$ 이후에 나타나는 가장 가까운 c의 위치가 된다.

따라서 이를 빠르게 계산하기 위해서 $nx(i,j)$라는 배열을 만드는데 $nx(i,j)$는 Word of Universe 상에서 i+1~끝까지 배열에서 가장 가까운 알파벳 j의 위치이며, 이를 미리 만드는데에는 $O(n * |A|)$이면 충분하다. ($|A|$는 사용하는 알파벳의 개수) 

따라서, 이 nx를 이용해서 dp 관계식을 엄밀히 세워보면 다음과 같다.

$$dp(i,j,k)=\min(nx(dp(i-1,j,k), des_1(i-1)), nx(dp(i,j-1,k), des_2(j-1)), nx(dp(i,j,k-1), des_3(k-1)))$$

단, $des_i$는 i 종교의 description 목록이다.

이 점화식을 바탕으로 dp배열을 구현한다.

+ query가 들어올 경우 해당하는 글자를 하나 늘리고, 해당 글자가 늘어나서 값이 추가되는 부분만 새로 구해주면 된다. 이 부분의 개수는 쿼리 한 번에 $O(n^2)$이다.

- query가 들어올 경우 단순히 description 개수만 한개 빼주면 된다. 이미 채워져있는 테이블은 무시한다.

Time Complexity : $O(n|A|+qn^2)$

코드

#include <iostream>
#include <vector>
#include <string>

#define INF 1<<30
#define N 251
#define L 100010
#define A 26
using namespace std;

string wou;
int n,q;
int nx[L][A], p[A];
int dp[N][N][N], len[4], pre[4];
char des[4][L];

int main()
{
	cin>>n>>q>>wou;
	wou=" "+wou;
	for(int i=0;i<26;i++)
	{
		nx[n+1][i]=n+1;
		p[i]=n+1;
	}
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<26;j++) nx[i][j]=p[j];
		if(i) p[wou[i]-'a'] = i;
	}

	while(q--)
	{
		string type,c;
		int x;
		cin>>type>>x;

		for(int i=1;i<4;i++) pre[i]=0;
		if(type[0]=='-')
		{
			len[x]--;
			cout<< (dp[len[1]][len[2]][len[3]]<=n?"YES":"NO")<<"\n";
			continue;
		}
		cin>>c;
		pre[x] = len[x];
		des[x][len[x]++] = c[0];

		for(int i=pre[1];i<=len[1];i++) for(int j=pre[2];j<=len[2];j++) for(int k=pre[3];k<=len[3];k++)
		{
			if(i==0 && j==0 && k==0)continue;
			dp[i][j][k] = INF;
			if(i) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i-1][j][k] ][ des[1][i-1]-'a' ]);
			if(j) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i][j-1][k] ][ des[2][j-1]-'a' ]);
			if(k) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i][j][k-1] ][ des[3][k-1]-'a' ]);	
		}
		cout<< (dp[len[1]][len[2]][len[3]]<=n?"YES":"NO")<<"\n";
	}
}

문제

https://codeforces.com/contest/1150/problem/C

풀이

2를 제외한 모든 소수는 홀수이다.

따라서, 주어진 순열을 2 1 2 2 2 ... 2 2 1 ... 1 1 1의 형태로 놓는다면, $\sum a_i$이하의 모든 소수를 포함하게 된다.

이것이 불가능한 경우는, 모두 1이거나 모두 2인 경우뿐이므로, 이 경우만 따로 출력한다.

Time Complexity : $O(n)$

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n, onenum=0, twonum=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x==1) onenum++;
		else twonum++;
	}

	if(onenum==0)
	{
		for(int i=0;i<n;i++) cout<<"2 ";
	}
	else if(twonum==0)
	{
		for(int i=0;i<n;i++) cout<<"1 ";
	}
	else
	{
		cout<<"2 1 ";
		for(int i=0;i<twonum-1;i++) cout<<"2 ";
		for(int i=0;i<onenum-1;i++) cout<<"1 ";
	}
}

문제

https://codeforces.com/contest/1150/problem/B

풀이

왼쪽 위부터 순서대로 채운다. 이렇게 채워도 가능한 모든 경우를 다 볼수 있다는 것이 증명 가능하다.

저 첫 빈칸을 채우기 위해서는 저 첫 빈칸을 위쪽타일로 하는 십자타일을 놓는 경우 외에는 존재하지 않는다.

따라서, 이 타일을 전부 채울수 있는 경우가 있다면, 저 곳은 o로 포함된 타일 모양으로 채워야 하고, 이를 반복적으로 진행하여, 다 채울 수 있는지 확인한다.

Time Complexity : $O(n^2)$

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define N 52
using namespace std;

int n;
string mp[N];
bool f(int p,int q)
{
	if(p<0 || q<0 || p>=n || q>=n) return false;
	return mp[p][q]=='.';
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>mp[i];

	for(int i=0;i<n*n;i++)
	{
		if(mp[i/n][i%n]=='#')continue;
		int x=i/n, y=i%n;
		if( !f(x,y) || !f(x+1, y-1) || !f(x+1, y) || !f(x+1, y+1) || !f(x+2, y))
		{
			cout<<"NO";
			return 0;
		}
		mp[x][y]=mp[x+1][y-1]=mp[x+1][y]=mp[x+1][y+1]=mp[x+2][y]='#';
	}
	cout<<"YES";
}

문제

https://codeforces.com/contest/1150/problem/A

풀이

가장 저렴하게 구매해서, 가장 비싸게 파는 것이 유리하다.

$smin=\min(s_i)$와 $bmax=\max(b_i)$를 구하자.

가능한 만큼, $smin$원에 구매하고, $smax$원에 판매하면 된다.

Time Complexity : $O(n+m)$

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int main()
{
	int n,m,r,x;
	int smin=10000,bmax=0;

	cin>>n>>m>>r;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		if(smin>x)smin=x;
	}
	for(int i=0;i<m;i++)
	{
		cin>>x;
		if(bmax<x)bmax=x;
	}

	if(smin>=bmax) cout<<r;
	else cout<<(r/smin)*bmax+r%smin;
}

문제

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of kthen left-out nodes in the end should remain as it is.

풀이

list 문제의 연속이다.

전체 길이를 구한다음 k개씩 묶어서 각각을 뒤집는다. 뒤집는 과정은 다음과 같다.

Time Complexity : $O(n)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL || k==1)return head;
        ListNode* prev = new ListNode(0);
        prev->next = head;
        
        int l=0;
        for(ListNode* it = head; it!=NULL; it=it->next)l++;
        
        ListNode *p = prev;
        for(int i=0;i+k<=l;i+=k)
        {
            ListNode* now = p->next;
            ListNode* nxt = now->next;
            for(int j=1;j<k;j++)
            {
                now->next= nxt->next;
                nxt->next =p->next;
                p->next = nxt;
                nxt =now->next;
            }
            p=now;
        }
        return prev->next;
    }
};

문제

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

풀이

기본적인 list 구현문제이다.

적당한 list 연산을 이용해서, 위의 list를 아래와 같이 변형시켜주는 계산을 진행한다.

Time Complexity : $O(n)$

풀이

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* prev = new ListNode(0);
        prev->next=head;
        for(ListNode *it=prev; it!=NULL;)
        {
            if(it->next==NULL || it->next->next==NULL) break;
            ListNode *temp=it->next;
            it->next=it->next->next;
            temp->next = it->next->next;
            it->next->next=temp;
            it=temp;
        }
        return prev->next;
    }
};

문제

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

풀이

우리는 Merge Two Sorted Lists를 알고있다고 가정하자.

그렇다면 분할정복을 이용해서 문제를 해결할 수 있다.

list를 절반으로 나눠서 각각의 Merge k/2 Sorted Lists를 구한 다음, 이 두 list를 Merge Two Sorted Lists로 합치면 끝.

시간복잡도를 $T(list)$이라 한다면 $T(list)=T(l)+T(r)+O(|N|)$이므로 $T(list)=O(|N|logk)$이다.

(여기서 |N|은 총 노드의 수, k는 list의 원소의 수)

Time Complexity : $O(|N|logk)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * ans=new ListNode(0);
        ListNode * it =ans;
        for(ListNode* i1=l1, *i2=l2; i1 || i2;it=it->next)
        {
            if(i1==NULL)
            {
                it->next=i2;
                i2=i2->next;
            }
            else if(i2==NULL)
            {
                it->next=i1;
                i1=i1->next;
            }
            else if(i1->val>i2->val)
            {
                it->next=i2;
                i2=i2->next;
            }
            else
            {
                it->next=i1;
                i1=i1->next;
            }
        }
        return ans->next;
    }
    ListNode* merge(int l, int r, vector<ListNode*>& lists)
    {
        if(l==r) return NULL;
        if(l+1==r) return lists[l];
        int mid=(l+r)/2;
        return mergeTwoLists(merge(l,mid,lists), merge(mid,r,lists));
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(0,lists.size(),lists);
    }
};

문제

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

풀이

분할정복법으로 풀이가 가능하다.

임의의 괄호열은 "( 괄호열1 ) 괄호열2" 꼴로 나타낼 수 있다.

또한 괄호열1과 괄호열2를 만드는 것은 전체문제의 subproblem이기 때문에 분할정복법이 가능한 것이다.

괄호열1이 $i$쌍의 괄호열이라면 총 $n$쌍이기 때문에, 괄호열2는 $n-1-i$쌍이 된다.

또한, 임의의 괄호열에 대해서 i값은 유일하게 정해진다.

따라서, 0부터 n-1까지의 i에 대해서, generateParenthsis(i)와 generateParenthesis(n-1-i)를 구한다.

각각 구한 쌍에 대해서, 모든 "( 괄호열1 ) 괄호열2"의 조합을 만들면 된다.

정답을 모두 구해야하기 때문에 시간복잡도는 정답 개수에 binding 된다.

괄호열의 개수는 n번째 카탈란 수라는 것이 알려져 있다.

Time Complexity : $O( |ans| )$

코드

class Solution {
private:
    string lp = "(";
    string rp = ")";
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        if(n==0) ans.push_back("");
        else for(int i=0;i<n;i++)
            for(string l: generateParenthesis(i))
                for(string r:generateParenthesis(n-1-i))
                    ans.push_back(lp+l+rp+r);
        return ans;
    }
};

문제

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

풀이

list에 대한 기본 구현을 묻는 문제이다. Merge Sort에 대한 기본적인 지식이 있다면 어렵지 않게 풀수 있다.

각각의 list가 정렬되어 있으므로, 가장 작은 숫자는 l1[0](그냥 array notation으로 쓰겠다.)과 l2[0]중에 작은 것이 된다.

그 후 그 작은걸 list에서 제거하면, 다시 처음과 같은 상황이 되고 l1[0]과 l2[0]중에 작은 숫자를 찾으면 된다.

이를 계속해서 반복하여, 제거되는 숫자들을 모으면 정렬된 리스트를 만들 수 있다.

Time Complexity : $O(|l1|+|l2|)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * ans=new ListNode(0);
        ListNode * it =ans;
        for(ListNode* i1=l1, *i2=l2; i1 || i2;it=it->next)
        {
            if(i1==NULL)
            {
                it->next=i2;
                i2=i2->next;
            }
            else if(i2==NULL)
            {
                it->next=i1;
                i1=i1->next;
            }
            else if(i1->val>i2->val)
            {
                it->next=i2;
                i2=i2->next;
            }
            else
            {
                it->next=i1;
                i1=i1->next;
            }
        }
        return ans->next;
    }
};

문제

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

풀이

Valid Parenthese를 판별하는 문제는 스택(Stack) 자료구조를 사용하는 문제로 유명하다.

문자열을 순서대로 돌면서 여는 괄호가 나오면 죄다 스택에 넣는다.

닫는 괄호가 나오면 스택에서 가장 위의 원소와 현재 닫는 괄호가 매칭이 되는 지를 체크한다.

만약 이때, 스택이 비어있거나 매칭이 되지 않으면 Invalid하므로 바로 false를 return한다.

마지막으로 문자열을 다 계산한 후에, 스택이 비어있으면 올바른 괄호열이 된다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    bool isValid(string s) {
        stack<char> S;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='('||s[i]=='{'||s[i]=='[')
            {
                S.push(s[i]);
                continue;
            }
            if(S.empty())return false;
            if(s[i]==')' && S.top()!='(') return false;
            if(s[i]==']' && S.top()!='[') return false;
            if(s[i]=='}' && S.top()!='{') return false;
            S.pop();
        }
        return S.empty();
    }
};