99코딩

numbers에 들어있는 문자열을 이어 붙여 만들 수 있는 가장 큰 수를 구해야한다.

문자열 a와 b가 있다고 할 때 a + b > b + a를 리턴하는 cmp() 함수를 만들어 sort()의 세 번째 인자 값으로 넣어 정렬한 문자열 배열을 index = 0부터 이어 붙이면 가장 큰 수가 된다.

예시)

1. numbers의 원소들을 문자열로 변환하여 문자열 벡터 nums에 담는다.

2. 문자열 a와 b를 받아 a + b > b + a를 리턴하는 함수 cmp()를 작성한다.

3. 위 함수를 가지고 nums를 정렬한다.

4-1. nums[0]이 "0"이면 벡터에서 가장 큰 문자열이 0인 것이므로 "0"을 리턴

4-2. answer에 nums의 원소들을 더한 후 answer 리턴

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

using namespace std;

bool cmp(string a, string b) {
    return a + b > b + a;
}
    

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> nums;
    
    for(int i = 0; i < numbers.size(); i++)
        nums.push_back(to_string(numbers[i]));
    
    sort(nums.begin(), nums.end(), cmp);
    
    if(nums[0] == "0") return "0";
    for(int i = 0; i < nums.size(); i++)
        answer += nums[i];
    
    return answer;
}

스택에 주식 가격의 인덱스를 담고 해당 인덱스의 prices값과 prices[i]를 비교해서 prices[s.top()]이 더 크다면 answer에 i에서 s.top()을 뺀 값을 담는다. 비교가 끝난 후 스택이 비어있지 않다면 스택에 남아있는 값을 인덱스로 가지는 price는 가격이 떨어지지 않았으므로 prices.size() - s.top() - 1를 answer에 담는다.

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    
    s.push(0);
    for(int i = 1; i < prices.size(); i++) {
        while(!s.empty() && prices[s.top()] > prices[i]) {
            answer[s.top()] = i - s.top();
            
            s.pop();
        }
        s.push(i);
    }
    
    while(!s.empty()) {
        answer[s.top()] = prices.size() - s.top() - 1;
        s.pop();
    }
    
    return answer;
}

가로의 길이가 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;
}