99코딩

풀이 방법

이 문제는 동적 계산법으로 접근하였다.

예를 들어 위의 표처럼 3행 4열의 땅이 있다고 할 때 같은 열을 연속으로 밟지 않도록 하며 그 행의 가장 큰 수를 더한다 할 때 한 칸씩 내려올 때마다 결과는 아래 표처럼 된다.

n+1 행의 i번째 칸에서의 최댓값은 표에서의 n + 1 행의 i 번째 칸의 값에 n행의 i번째 칸을 제외한 다른 칸의 값 중 가장 큰 값을 더한 값과 같다는 것을 알 수 있다. 

이를 통해 점화식을 세워보면 arr[n+1][i] += max;가 될 것이고 이를 기반으로 코드를 작성하였다.

1. 한 행에서 최대값을 찾는 함수를 작성한다.

2. i = 0부터 land.size()까지 각 행에 이전 행의 같은 열을 제외한 최대값을 더해주는 것을 반복한다.

3. 반복문이 끝난 후 land[land.size()-1]에서 최댓값을 찾아 리턴한다.

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

using namespace std;

int search_max(vector<int>& v, int idx){
    int temp = 0;
    for(int i = 0; i < 4; i++) {
        if(i == idx) continue;
        temp = max(temp, v[i]);
    }
        
    return temp;
}

int solution(vector<vector<int>> land) {
    for(int i = 0; i < land.size() - 1; i++) {
        for(int j = 0; j < 4; j++) {
            land[i+1][j] += search_max(land[i], j);
        }
    }
    
    return search_max(land[land.size() - 1], 4);
}

풀이 방법

10진수인 n을 k진수 문자열로 변환하고 해당 문자열을 조건에 맞춰 파싱 후 소수의 개수를 리턴하면 된다.

1. n을 k진수 문자열로 변환하여 문자열 arithmetic에 담는다.

2. 문자열을 조건에 맞춰 파싱하여 tmp에 담고 숫자로 변환 후 소수인지 판별하고 소수면 answer++

3. 반복문이 끝난 후 tmp가 비어있지 않다면 한 번 더 소수인지 판별하고 소수면 answer++

4. answer 리턴

#include <string>
#include <vector>

using namespace std;

bool isPrime(long long n) {
    if(n < 2) return false;
    for(long long i=2; i*i<=n; i++)
        if(!(n % i)) return false;
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string arithmetic = "";
    string tmp = "";
    
    while(n) {
        arithmetic += to_string(n % k);
        n /= k;
    }
    
    arithmetic = string(arithmetic.rbegin(), arithmetic.rend());
    
    for(int i = 0; i < arithmetic.length(); i++) {
        if(arithmetic[i] == '0' && !tmp.empty()) {
            long long num = stoll(tmp);
            if(isPrime(num)) answer++;
            tmp = "";
        }
        else tmp += arithmetic[i];
    }
    
    if(!tmp.empty()) {
        long long  n = stoll(tmp);
        if(isPrime(n)) answer++;
    }
    
    return answer;
}

3진법과 같다고 생각하고 접근했다.

1. n이 0이 아닐때까지 num에 n % 3을 담고 n/= 해준다.

2-1. num == 0일 때 answer의 앞에 "4"를 더해주고 n--한다.

2-2. num == 1일 때 answer의 앞에 "1"을 더해준다.

2-3. num == 2일 때 answer의 앞에 "2"를 더해준다. 

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

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
    string answer = "";
    
    while (n!=0) {
        int num = n % 3;
        n /= 3;

        if (num == 0) {
            answer = "4" + answer;
            n--;
        }
        else if (num == 1) answer = "1" + answer;
        else if (num == 2) answer = "2" + answer;
    }

    return answer;
}

unordered_map의 == 연산자가 map에 저장된 요소의 순서와 상관없이 비교하므로 unordered_map 2개를 선언하여 두 개가 같으면 가능한 날이므로 answer++하여 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 구하였다.

1. string을 Key, int를 value로 가지는 unordered_map 2개를 선언한다.

2. wants라는 unordered_map에는 want[i], number[i]를 페어로 하여 삽입한다.

3. discounts에는 i부터 i + 10까지 discounts[discount[j]]++을 하고 wants == discounts가 true면 count++을 한다.

4. discounts를 비워주고 i++을 한 다음 위를 반복

5. 반복문이 끝나면 count를 리턴

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

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    int count = 0;
    
    unordered_map<string, int> wants;
    unordered_map<string, int> discounts;
    
    for(int i = 0; i < want.size(); i++)
        wants.insert({want[i], number[i]});
    
    for(int i = 0; i <= discount.size() - 10; i++) {
        
        for(int j = i; j < i + 10; j++)
            discounts[discount[j]]++;
        
        if(wants == discounts) count++;
        discounts.clear();
    }
    
    answer = count;
    
    return answer;
}

길이가 len인 연속 부분 수열의 합을 모두 구해서 set을 통해 중복을 제거 한 후 set의 크기를 리턴하면 된다.

먼저 연속 부분 수열의 합을 모두 구한다고 할 때, 예시로 [7,9,1,1,4]로 이루어진 원형 수열이 있으면 길이가 len인 연속 부분 수열의 합의 종류는 아래와 같다.

이를 자세히 보면 idx = i로 시작하는 연속 부분 수열들은 idx = 0의 값에 idx = len의 값을 순차적으로 더해준 값이다.

즉, 해당 표의 값들은 tmp에 elements[(index + len) % elements.size()]을 반복적으로 더해줌으로써 구할 수 있다.

1. set 자료구조 선언

2. 이중 for문을 통해 tmp = 0에 elements[(j + i) % elements.size()]의 값을 elements.size()번 더해주고, 더할 때마다 s에 삽입한다.

3. 반복문이 끝나면 s.size()를 리턴

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<int> elements) {
    set<int> s;

    for (int i = 0 ; i < elements.size() ; i++) {
        int tmp = 0;
        for (int j = 0 ; j < elements.size() ; j++) {
            tmp += elements[(j + i) % elements.size()];
            s.insert(tmp);
        }
    }

    return s.size();
}

풀이 방법

문제에 주어진 조건대로 2차원 배열을 만들면 아래 그림과 같은 구조가 된다

만약 n이 3이라 할 때 주어진 과정대로 1차원 배열을 만들면 아래와 같이 된다.

이것의 규칙을 자세히 보면 크기가 n인 idx = i에 있는 원소의 값은 (i / n) > (i % n) ? (i / n + 1) : (i % n + 1)임을 알 수 있다.

1. 각각 i / n과 i % n을 담을 int형 변수 tmp1와 tmp2를 선언한다.

2. i행 i열까지의 모든 빈 칸을 i로 채우는 1차원 배열 arr가 있다고 할 때 arr[left]부터 arr[right]를 구하기 위해 answer에 left부터 right까지 i / n이 i % n보다 크다면 i / n + 1, 아니면 i % 2 + 1을 담는다.

3. right까지 반복이 끝나면 answer 리턴

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    int tmp1 = 0, tmp2 = 0;
    
    for(long long i = left; i <= right; i++) {    
        int tmp1 = i / n;
        int tmp2 = i % n;
        
        answer.push_back(tmp1 > tmp2 ? tmp1 + 1 : tmp2 + 1);
    }
    
    return answer;
}

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;
}