99코딩

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

이후 종류별 옷의 수 + 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;
}

LRU(Least Recently Used) 알고리즘

가장 오랫동안 참조되지 않은 페이지를 교체하는 방식

기억 공간에 동일한 데이터가 존재하면 해당 데이터를 삭제한 뒤 top에 넣는다.

동일한 데이터가 존재하지 않을 때 기억 공간이 가득 찼다면 가장 오래된 데이터를 삭제한 뒤 새로운 데이터를 넣고

아니라면 바로 데이터를 넣는다. 

풀이 방법

데이터를 앞/뒤에서 삭제하기 용이한 덱(Deque)을 사용하였다.

1. cacheSize가 0이라면 캐시가 없기 때문에 항상 miss이므로 5*cities.size()를 리턴한다.

2. string형 덱 cache를 선언한다.

3. 대소문자 구분을 하지 않으므로 cities[i]를 소문자로 변환시켜준다.

4. miss를 판단할 bool형 cacheMiss를 true로 선언해주고 캐시 내부를 순회하며 cities[i]와 동일한 데이터가 있다면 캐시에서 해당 데이터를 지우고 answer++, cacheMiss = false를 한 다음 break한다.

5. cities[i]를 캐시에 넣는다.

6-1. cacheMiss가 true면 answer에 5를 더해준다.

6-2. cacheMiss가 true고 cache.size()가 cacheSize보다 크면 가장 오래된 데이터를 삭제하고 answer에 5를 더해준다.

7. 반복문이 끝난 후 answer 리턴 

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    if(cacheSize < 1) return 5 * cities.size();
    
    deque<string> cache;
    
    for(int i = 0; i < cities.size(); i++) {
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
        
        bool cacheMiss = true;
        
        for(int j = 0; j < cache.size(); j++) {
            if(cache[j] == cities[i]) {
                cache.erase(cache.begin() + j);
                answer++;
                cacheMiss = false;
                break;
            }
        }
            
        cache.push_back(cities[i]);
        
        if(cacheMiss) {
            if(cache.size() > cacheSize) 
                cache.pop_front();
            answer += 5;
        }
    }
    
    return answer;
}

[3, 0, 6, 1, 5]에서 3번이상 인용된 논문이 3편이고 이외의 논문은 3회 이하 인용되었기에 H-Index는 3이다.

다른 예시로 [5,4,3,6,2,1,5]가 있다고 할 때 우선 풀이하기 좋도록 내림차순으로 정렬하면 [6,5,5,4,3,2,1]이 된다.

arr = [6,5,5,4,3,2,1]

이것의 H-Index를 구하면 아래 표와 같다.

표를 보면 5에서부터는 숫자가 H-Index보다 작아지므로 H-Index는 4가 된다.

이를 보면 arr[i]가 i이하가 되기 전의 H-Index값이 최대임을 알 수 있다.

풀이 방법

1. citations의 요소들을 내림차순으로 정렬한다.

2. citations[i]가 i이하면 break, 아니면 HIndex++을 한다.

3. 반복문이 끝나면 HIndex를 리턴

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

using namespace std;

int solution(vector<int> citations) {
    int HIndex = 0;
    
    sort(citations.begin(), citations.end(), greater<int> ());

    
    for(int i = 0; i < citations.size(); i++) {
        if(citations[i] <= i) break;
        else HIndex++;
    }
    
    return HIndex;
}

멀리 뛰기 - 프로그래머스

칸이 1개일 때 (1)

칸이 2개일 때 (1,1), (2)

칸이 3개일 때 (1,2), (2,1), (1,1,1)

칸이 4개일 때 (1,1,2), (2,2), (1,2,1), (2,1,1), (1,1,1,1)

자세히 보면 칸이 n개일 때 뛸 수 있는 방법은 n-1의 방법에 1씩 추가한 방법 + n-2의 방법에 2씩 추가한 방법이란 걸 알 수 있다.

즉, 동적 계획법(Dynamic Programming)으로 풀면 되는 문제이다.

식으로 작성하면 DP[n] = DP[n-1] + DP[n-2]라는 피보나치 수열의 형태가 된다.

풀이 방법

1. int형 벡터인 con을 선언한다.

2. con[0]과 con[1]에 1을 담는다.

3. con[i -1] + con[i - 2] % 1234567를 i가 n이 될 때까지 con에 push_back()한다.

4. 반복문이 끝난 후 con.back()을 리턴

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;
    
    vector<int> con;
    
    con.push_back(1); con.push_back(1);
    
    for(int i = 2; i <= n; i++) {
        con.push_back((con[i - 1] + con[i - 2]) % 1234567);
    }
    
    answer = con.back();
    
    return answer;
}

점프와 순간 이동 - 프로그래머스

점프는 한 칸씩 이동하며 칸당 1만큼 건전지를 사용하고 순간 이동은 건전지를 사용하지 않고 현재까지 온 거리 x 2만큼 이동한다. n만큼 이동할 때 건전지 사용량이 최소가 되는 값 return이므로 n을 2로 나누며 나머지가 1이 될 때마다 answer++해주면 된다.

핵심은 순간이동의 x2이다.

예시를 들면 표와 같이 된다.(점프는 J, 순간이동은 T)

풀이 방법

1. n을 2로 나눈 나머지가 1이면 answer++

2. n /= 2를 한 뒤 반복

3. 반복이 끝나면 answer 리턴

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;
    
    while(n) {
        if(n % 2) ans++;
        n /= 2;
    }

    return ans;
}

예상 대진표 - C++

각 라운드가 진행될 때마다 참가자는 절반으로 줄어든다.

1 vs 2에서 2가 승리하면 다음 라운드에서는 1번, 5 vs 6에서 5가 승리한다면 다음 라운드에서는 3번.....

이런 형식이 아래 그림처럼 반복된다.

그림을 보면 현재 라운드의 승자는 다음 라운드에서 (현재 번호 + 1) / 2의 번호를 부여받는 다는 것을 알 수 있다.

이를 이용해 아래와 같은 방식으로 코드를 작성하였다.

풀이 방법

1. 반복문을 돌 때마다 answer++을 해주며 a == b면 answer를 리턴한다.

2. a != b면 다음 라운드로 넘어가므로 a와 b의 번호를 (현재 번호 + 1) / 2를 해준다.

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    
    for(int i = 1;;i++, answer++) {
        if(a == b) return answer;
        a = (a + 1) / 2;
        b = (b + 1) / 2;
    }
}

N개의 최소공배수

풀이 방법

최소공배수 = 두 수의 곱 / 최대공약수

1. 유클리드 호제법을 통해 최대공약수를 구하는 함수를 작성한다.

2. answer에 arr[0]을 대입한다.

3. 기존에 answer에 담겨있단 값과 arr[i]의 최소공배수를 구한다.

4. 이를 반복후 리턴한다.

#include <string>
#include <vector>

using namespace std;

int GCD(int x, int y) {
    if(!x) return y;
    return GCD(y % x, x);
}

int solution(vector<int> arr) {
    int answer = arr[0];
    
    for(int i = 1; i < arr.size(); i++)
        answer = (answer * arr[i]) / GCD(answer, arr[i]);
    
    return answer;
}