99코딩

풀이방법

간선 방문 체크를 통해 방문한 적이 있다면 continue, 방문한 적이 없다면 answer++해준다.

단, 방문 체크 시 (A , B)와 (B, A)는 동일한 간선이므로 둘 다 체크해주어야한다.

#include <string>
#include <map>

using namespace std;

int solution(string dirs) {
    int answer = 0;
    map<pair<pair<int, int>, pair<int, int>>, bool> visited;
    
    int posX = 5;
    int posY = 5;
    
    for(int i = 0; i < dirs.length(); i++) {
        int startX = posX;
        int startY = posY;
        
        if(dirs[i] == 'U') {
            if(posY + 1 > 10) continue;
            posY++;
        }
        else if(dirs[i] == 'D') {
            if(posY - 1 < 0) continue;
            posY--;
        }
        else if(dirs[i] == 'R') {
            if(posX + 1 > 10) continue;
            posX++;
        }
        else {
            if(posX - 1< 0) continue;
            posX--;
        }
        
        if(visited[make_pair(make_pair(startX, startY), make_pair(posX, posY))] == true)
            continue;
        
        visited[make_pair(make_pair(startX, startY), make_pair(posX, posY))] = true;
        visited[make_pair(make_pair(posX, posY), make_pair(startX, startY))] = true;
        
        answer++;
    }
    
    return answer;
}

풀이방법

각 문자열을 잘른 뒤 오늘 날짜와 개인정보 수집 일자 + 약관 종류에 따른 유효기간을 비교해서 후자가 전자보다 작을 시 해당 개인정보는 파기해야하므로 해당 개인정보의 번호를 answer에 담는다.

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

using namespace std;

vector<int> solution(string today, vector<string> terms, vector<string> privacies) {
    vector<int> answer;
    vector<int> privDate;
    map<char, int> m;
    
    int todayY = stoi(today.substr(0, 4));
    int todayM = stoi(today.substr(5, 2));
    int todayD = stoi(today.substr(8, 2));
    
    int totalD = todayY * 12 * 28 + (todayM - 1) * 28 + todayD;
    
    for(int i = 0; i < terms.size(); i++)
        m[terms[i][0]] = stoi(terms[i].substr(terms[i].find(" "), terms[i].size() - 1));
    
    for(int i = 0; i < privacies.size(); i++) {
        int privY = stoi(privacies[i].substr(0, 4)); 
        int privM = stoi(privacies[i].substr(5, 2)); 
        int privD = stoi(privacies[i].substr(8, 2));
        char privT = privacies[i].back();
         
        int tmp = privY * 12 * 28 + (privM - 1) * 28 + privD + (m[privT] * 28 - 1);
        
        privDate.push_back(tmp);
    }
    
    for(int i = 0; i < privDate.size(); i++)
        if(privDate[i] < totalD) answer.push_back(i + 1);
    
    return answer;
}

풀이방법

순열을 이용하여 구할 수 있는 모든 조합을 구한 후 소수인지 판별하고 소수라면 중복을 제거하기 위해 set 자료구조에 담은 후 set의 크기를 반환하였다.

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

using namespace std;

bool isPrime(int n) {
    
    if(n == 0 || n == 1)
        return false;
    
    for(int i = 2; i*i <= n; i++) 
        if(n % i == 0) return false;
    return true;
}

int solution(string numbers) {
    int answer = 0;
    set<int> tmp;
    
    sort(numbers.begin(), numbers.end());
    
    do {
        for(int i = 1; i <= numbers.size(); i++) {
            int num = stoi(numbers.substr(0, i));
            if(isPrime(num)) tmp.insert(num); 
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return tmp.size();
}

풀이방법

문자열 형식의 숫자 number에서 k개 만큼 제거했을 때 만들어지는 수 중 가장 큰 숫자를 구해야하는 문제이다.

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int index = -1;
    
    for(int i = 0; i < number.length() - k; i++) {
        char maxnum = ' ';
        for(int j = index + 1; j <= k + i; j++) {
            if(maxnum < number[j]) {
                maxnum = number[j];
                index = j;
            }
        }
        answer += maxnum;
    }
    
    return answer;
}

풀이방법

제목 그대로 재귀 알고리즘 중 유명한 하노이의 탑을 구현하면 된다.

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> answer;

void Hanoi(int n, int from, int by, int to) {
    if (n == 1) answer.push_back({from, to});
    else {
        Hanoi(n - 1, from, to, by);
        answer.push_back({from, to});
        Hanoi(n - 1, by, from, to);
    }
}

vector<vector<int>> solution(int n) {
    Hanoi(n, 1, 2, 3);
    
    return answer;
}

풀이방법

변수 2개와 find 함수를 이용하여 각 스킬트리가 선행 스킬 순서를 만족하는지를 검사하였다.

1. 스킬트리가 조건을 만족했는지 검사하기 위한 변수들을 선언한다.

2. skill_trees[i][j]가 skill에 있는지 확인하고 없다면 계속 진행, 있다면 idx와 next를 이용해 순서가 맞는지까지 확인하고 만약 순서가 맞지 않는다면 잘못된 스킬트리이므로 flag = false로 하고 break한다.

3. flag가 true이면 가능한 스킬트리이므로 answer++한다.

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    for(int i = 0; i < skill_trees.size(); i++) {
        bool flag = true;
        int idx = 0, next = 0;
        
        for(int j = 0; j < skill_trees[i].size(); j++) {
            idx = skill.find(skill_trees[i][j]);
            if(idx == - 1) continue;
            else {
                if(idx != next++) {
                    flag = false;
                    break;
                }
            }
        }
        if(flag == true)
            answer++;
    }
    
    return answer;
}

풀이방법

문자열 s의 각 알파벳에 index만큼 뒤에 있는 알파벳을 구하되 문자열 skip에 있는 알파벳은 카운트하지 않아야한다.

이를 구현하기 위해 문자열 s의 각 알파벳에 index번 만큼 1을 더하였을 때 해당 알파벳이 skip에 들어있는 알파벳일 경우 반복 횟수를 한 번씩 늘려주도록 했다. 또한 s와 skip은 알파벳 소문자로만 이루어져 있으므로 s[i]에 1을 더하였을 시 아스키 코드 값이 122를 초과한다면 a가 되도록 하였다.

1. 알파벳의 검사를 위해 int형 변수 cur을 선언

2. s[i]에 ++해준다.

3. s[i]가 z보다 커지면 a로 변환하고 find함수로 s[i]가 skip안에 있는지 찾고 있다면 반복 횟수를 늘려주고 없다면 계속해서 수행한다.

4. 이를 index번만큼 반복 후 변환된 문자열 s를 리턴

#include <string>
#include <vector>

using namespace std;

string solution(string s, string skip, int index) {
    int cur = 0;
    
    for(int i = 0; i < s.size(); i++) {
        for(int j = 0; j < index; j++) {
            s[i]++;
            if(s[i] > 'z') s[i] = 'a';
            
            cur = skip.find(s[i]);
            if(cur == -1)
                continue;
            else j--;
        }
    }
    
    return s;
}

풀이 방법

문자열을 시간 / 차량 번호 / 내역으로 잘라서 차량번호를 Key 해당 차량 번호의 시간들을 Value로 해서 map 컨테이너에 저장한다.   만약 value의 개수가 홀수라면 그 차량이 나간 기록이 records에 담겨 있지 않으므로 23:59에 출차한 것이니 value에 "23:59"를 추가한다.  이후 차량이 하루동안 몇 분 주차되어 있는지를 계산해서 기본 시간보다 짧으면 기본 요금을 아니라면 기본 요금에 단위 시간마다 단위 요금을 추가해서 answer에 담는다.

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

using namespace std;

int convert_min(string s) {
    int total_min = 0;
    
    int hour = stoi(s.substr(0, 2));
    int min = stoi(s.substr(3, 2));
    
    total_min = hour * 60 + min;
    
    return total_min;
}

vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    map<string, vector<string>> m;
    
    for(int i = 0; i < records.size(); i++) {
        vector<string> v;
        
        string tmp = "";
        for(int j = 0; j < records[i].length(); j++) {
            if(records[i][j] == ' ') {
                v.push_back(tmp);
                tmp = "";
            }
            else tmp += records[i][j];
        }
        v.push_back(tmp);
        
        m[v[1]].push_back(v[0]);
        v.clear();
    }
    
    for(auto it : m) {
        vector<string> times = it.second; 
                
        if(times.size() % 2) times.push_back("23:59");
        
        int time = 0;
        for(int i = 0; i < times.size() - 1; i += 2) {
            int num1 = convert_min(times[i]);
            int num2 = convert_min(times[i+1]);
            time += num2 - num1;
        }
        
        if(time > fees[0])
            answer.push_back(fees[1] +  ceil((time - fees[0]) / (double)fees[2]) * fees[3]);
        else answer.push_back(fees[1]);
    }

    
    return answer;
}