99코딩

가로의 길이가 n일 때 타일을 배치할 수 있는 방법의 수는 아래와 같이 변화한다.

n = 1		1가지
n = 2		2가지
n = 3		3가지
n = 4	문제 설명 참조	5가지
n = i		DP[i-1] + DP[i-2]

즉 이 문제도 동적 계획법을 이용해 풀 수 있다.

식을 세워보면 DP[i] = DP[i-1] + DP[i-2]가 되므로 이를 가지고 길이가 n인 직사각형에 타일을 배치하는 방법의 수를 구하면 된다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int DP[60001];
    
    DP[1] = 1;
    DP[2] = 2;
    
    for(int i = 3; i <= n; i++) 
        DP[i] = (DP[i-1] + DP[i-2]) % 1000000007; 
    
    return DP[n];
}

박스에 담아 판매할 때 귤의 크기의 종류가 최소가 되어야 하므로 개수가 많은 크기의 귤을 차례대로 담아주면 된다.

이를 위해 map을 사용해 귤의 크기를 key값 개수를 value로 하여 저장하고 이를 value 값에 따라 오름차순으로 정렬한 다음 크기가 많은 순서대로 담아 합이 k이상이 됐을 때의 종류의 수를 리턴하였다.

풀이 방법

1. int형을 각각 key,value로 가지는 m을 선언한다.

2. tangerine을 m에 담는다.

3. 벡터에 담고 value 값에 따라 오른차순으로 정렬한다.

4. value값을 더하며 합이 k이상이 되면 더한 횟수 count를 리턴한다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    if(a.second == b.second) return a.first > b.first;
    else return a.second > b.second;
}

int solution(int k, vector<int> tangerine) {
    int count = 0;
    int tmp = 0;
    
    map<int, int> m;
    
    for(int i = 0; i < tangerine.size(); i++)
            m[tangerine[i]]++;
    
    vector<pair<int, int>> v(m.begin(), m.end());
    
    sort(v.begin(), v.end(), cmp);
    
    for(int i = 0; i < v.size(); i++) {
        tmp += v[i].second;
        count++;
        
        if (tmp >= k) return count;
    }
}

처음에는 아래와 같이 코드를 작성했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    sort(scoville.begin(), scoville.end());
    
    while(scoville.front() <= K) {
        scoville[1] = scoville[0] + (scoville[1] * 2);
        answer++;
        
        scoville.erase(scoville.begin());
        sort(scoville.begin(), scoville.end());
        
        if(scoville.size() == 1 && scoville.front() < K)
            return -1;
    }
    
    return answer;
}

당연히 다 틀렸다.

풀이방법

문제 분류에도 힙(Heap)이 있는만큼 우선순위 큐를 이용해서 문제를 해결하였다.

1. 원소가 오름차순으로 정렬되는 우선순위 큐를 선언한다.

2. scoville 컨테이너에 들어있는 원소들을 전부 우선순위 큐에 담는다.

3. 우선순위 큐의 top이 K보다 작을 때 우선순위 큐의 첫 번째 원소를 tmp1, 두 번째 원소를 tmp2에 담고 tmp1 + tmp2 * 2를 한 값을 다시 우선순위 큐에 담고 answer++한다.

4-1. 만약 반복문을 도는 중 우선순위 큐의 사이즈가 1이고 top의 값이 K보다 작다면 스코빌 지수를 K 이상으로 만들 수 없으므로 -1을 리턴한다.

4-2. 반복문이 종료되면 answer를 리턴한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> prio_que;
    
    for(int i = 0; i < scoville.size(); i++)
        prio_que.push(scoville[i]);
    
    while(prio_que.top() < K) {
        int tmp1 = prio_que.top(); prio_que.pop();
        int tmp2 = prio_que.top(); prio_que.pop();
        int tmp3 = tmp1 + tmp2 * 2;
        
        prio_que.push(tmp3);
        answer++;
        
        if(prio_que.size() == 1 && prio_que.top() < K)
            return -1;
    }
    
    return answer;
}

풀이방법

두 문자열을 문제에 나와있는 조건에 맞춰 각각 두 글자씩 잘라서 벡터에 담고 서로 비교하며 교집합의 수를 구한 뒤 합집합의 수를 구하고 두 수를 통해 자카드 유사도를 구했다.

1. 대문자와 소문자의 차이는 무시한다 되어있으므로 두 문자열을 소문자로 변환해준다.

2. 두 글자가 전부 영문자인지 확인하고 맞다면 문자열에서 두 글자를 잘라 벡터에 담는다.

3. 이후 다중집합을 의미하는 벡터 2개가 다 비어있다면 65536을 리턴한다.

4. 아니라면 두 벡터의 원소를 비교하며 값이 같으면 교집합의 수를 하나 더하고 해당 원소의 값을 빈 문자열로 바꿔 교집합이 중복으로 검출되지 않도록한다.

5. 위를 통해 구한 교집합의 수로 합집합의 수도 구하고 합집합의 수가 0이면 나눌 수 없으므로 65536 리턴, 아니라면 자카드 유사도를 구한 뒤 65536을 곱한 값을 리턴한다.

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

using namespace std;

int solution(string str1, string str2) {
    vector<string> multiset1;
    vector<string> multiset2;
    int intersectionCount = 0;
    int unionCount = 0;
    
    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
    
    for(int i = 0; i < str1.length() - 1; i++) {
        if(isalpha(str1[i]) && isalpha(str1[i+1]))
            multiset1.push_back(str1.substr(i,2));
    }
    
    for(int i = 0; i < str2.length() - 1; i++) {
        if(isalpha(str2[i]) && isalpha(str2[i+1]))
            multiset2.push_back(str2.substr(i,2));
    }
    
    if(multiset1.empty() && multiset2.empty())
        return 65536;
    
    for(int i = 0; i < multiset1.size(); i++) {
        for(int j = 0; j < multiset2.size(); j++) {
            if(multiset1[i] == multiset2[j]) {
                intersectionCount++;
                
                multiset2[j] = "";
                
                break;
            }
        }
    }
    
    unionCount = multiset1.size() + multiset2.size() - intersectionCount;
    
    if(unionCount == 0) return 65536;
    
    double jaccard = (double)intersectionCount / (double)unionCount;
    
    return jaccard*65536;
}

코드블럭에 언어를 지정할 수 있단 걸 이제야 알았다

해시 분류에 속해있는 문제인만큼 해시를 사용해서 문자를 하나씩 받아 비교하는 방식으로 풀이하였다.

처음 코드 실행 시 테스트 케이스 2번이 오답이 나와서 확인해보니 문자를 비교하는 부분에서 현재 문자열과 같을 때는 제외하는 코드를 작성하지 않아 생긴 문제였다.

풀이방법

1. string형을 key로 int형을 value로 가지는 unordered_map 변수를 선언한다.

2. 각 전화번호들을 key로 하고 value는 1을 값으로 가지도록 한다.

3. string형 tmp에 phone_book[i]의 문자를 하나씩 더해주며 tmp가 phone_book[i]와 같지 않고, unordered_m[tmp]의 value가 1이면 다른 번호가 현재 번호의 접두어로 쓰인것이므로 false를 리턴한다.

4. 반복문이 완전히 끝났다면 한 번호가 다른 번호의 접두어로 쓰인 경우가 없으므로 true를 리턴한다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> unordered_m;
    
    for(int i = 0; i < phone_book.size(); i++) {
        unordered_m[phone_book[i]] = 1;
    }
    
    for(int i = 0; i < phone_book.size(); i++) {
        string tmp = "";
        for(int j = 0; j < phone_book[i].length(); j++) {
            tmp += phone_book[i][j];
            if(unordered_m[tmp] && (tmp != phone_book[i]))
                return false;
        }
    }
    
    return true;
}

풀이 방법

작업 진도가 자연수이므로 99에 작업 진도를 뺀 값을 작업 속도로 나누어서 남은 날짜를 구해서 큐에 넣는다.

이후 큐의 front이 저장된 변수와 비교해서 작으면 완료한 작업의 개수를 1씩 증가시켜주고 pop을 한다.

만약 front보다 크다면 front값이 저장된 변수에 front값을 새로 대입하고 저장된 완료한 작업의 개수를 answer에 push_back한 다음 완료한 작업의 개수를 0으로 초기화한다.

이를 큐가 빌때까지 반복한 다음 마지막으로 완료한 작업의 개수를 push_back하고 answer를 리턴한다.

1. int형 큐 q를 선언한다.

2. (99 - progresses[i]) / speeds[i]를 q에 담는다.

3. 이후 q의 front를 저장할 tmp1과 완료한 작업의 개수를 저장할 tmp2를 선언한다.

4-1. q가 비어있지 않은 동안 q의 front가 tmp1이하면 tmp2++, q.pop()을 한다.

4-2. front가 tmp1보다 크다면 tmp1에 q.front를 새로 대입하고 answer.push_back(tmp2)를 해준 뒤 tmp2를 0으로 초기화한다.

5. 반복문이 끝나면 tmp2를 answer에 push_back하고 answer 리턴 

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    
    int size = progresses.size();
    
    for(int i = 0; i < size; i++)
        q.push((99 - progresses[i]) / speeds[i] );
    
    int tmp1 = q.front();
    int tmp2 = 0;
    
    while(!q.empty()) {
        if(q.front() <= tmp1) {
            tmp2++;
            q.pop();
        }
        else {
            tmp1 = q.front();
            answer.push_back(tmp2);
            tmp2 = 0;
        }
    }
    answer.push_back(tmp2);
    
    return answer;
}

각 옷의 종류마다 몇 개씩 있는지만 구하면 되는 문제이다.

이후 종류별 옷의 수 + 1을 곱하면 해당 옷들로 할 수 있는 조합의 수가 나온다.

그리고 하루에 최소 한 개의 의상은 입는다는 조건이 있으므로 어떤 옷도 입지 않는다는 경우를 제외하면 조건에 맞는 답이 나온다.

예를 들어 아래의 표처럼 옷을 가지고 있을 때 문제의 조건을 만족하는 서로 다른 옷의 조합의 수는 (5 x 3 x 2) - 1이다.

풀이방법

1. string형을 Key로 int형을 value로 가지는 m을 선언한다.

2. clothes 벡터를 순회하며 의상의 이름은 필요하지 않으므로 같은 종류의 의상이 나올때마다 m[clothes[i][1]]++ 해준다.

3. answer에 m의 value에 +1한 값을 곱한다.

4. 반복문이 끝나면 answer--를 하고 answer를 리턴

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    map<string, int> m;
    
    for(int i = 0; i < clothes.size(); i++) {
        m[clothes[i][1]]++;
    }
    
    for(auto cloth = m.begin(); cloth != m.end(); cloth++) {
        answer *= (cloth->second + 1);
    }
    answer--;
    
    return answer;
}

올바른 괄호 문자열이 되기 위해서는

1. 문자열이 닫는 부호로 시작해서는 안된다.

2. 여는 부호 다음에는 여는 부호 또는 해당 부호를 닫는 부호가 나와야한다.

3. 위 조건에 맞춰 짝이 맞춰진 후 남는 부호가 없어야한다.

풀이 방법

이번에는 괄호끼리 매칭시켜 짝이 맞는 괄호는 삭제하기위해 스택을 사용하였다.

1. char형 스택 bracket을 선언

2. 올바른 괄호인지 판별하기 위한 bool형 flag를 선언

3. bracket이 비어있을 때 s[j]가 닫는 부호라면 올바른 괄호 문자열이 아니므로 flag에 false를 대입 하고 break한다.

4-1. bracket이 비어있지 않을 때 s[j]가 여는 부호라면 bracket에 넣는다.

4-2. bracket.top()이 각각 '(', '{', '['일 때 s[j]가 ')', '}', ']', 즉 괄호가 올바르게 짝지어지면 bracket.pop()을 한다.

4-3. 위 두 조건에 부합하지 않는다면 flag에 false를 대입하고 break한다.

5. 위 조건문들이 끝난 후 bracket이 비어 있고 flag가 true라면 answer++

6. 문자열을 한 칸씩 회전시켜준다.

7. 반복문이 끝나면 answer 리턴

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    for(int i = 0; i < s.length(); i++) {
        stack<char> bracket;
        bool flag = true;
        for(int j = 0; j < s.length(); j++) {
            if(bracket.empty()){
                if(s[j] == ')' || s[j] == '}' || s[j] == ']') {
                    flag = false;
                    break;
                }
                else bracket.push(s[j]);
            } else {
                if(s[j] == '(' || s[j] == '{' || s[j] == '[')
                    bracket.push(s[j]);
                else if(bracket.top() == '(' && s[j] == ')' || 
                        bracket.top() == '{' && s[j] == '}' || 
                        bracket.top() == '[' && s[j] == ']') bracket.pop();
                else {
                    flag = false;
                    break;
                }
            }
        } 
        if(bracket.empty() && flag) answer++;

        char tmp = s[0];
        s.erase(s.begin());
        s += tmp;
    }
    
    return answer;
}