99코딩

풀이방법

0부터 t x m까지의 숫자를 n진법으로 변환해서 temp에 더한다. 이후 temp에서 튜브가 말해야 하는 숫자들만 구해서 answer에 담아 리턴한다.

#include <string>
#include <vector>

using namespace std;

string convert(int n, int num) {
    char list[] = {'0', '1', '2', '3', '4', '5', '6', '7',
                   '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    
    string temp = "";
    
    while(num / n != 0) {
        temp = list[num % n] + temp;
        num /= n;
    }
    temp = list[num % n] + temp;
    
    return temp;
}

string solution(int n, int t, int m, int p) {
    string answer = "";
    string temp = "";
    int count = 0;
    
    for(int i = 0; i < t * m; i++) temp += convert(n, i);
    for(int i = p - 1; i < temp.length(), count < t; i += m, count++;)
        answer += temp[i];
    
    return answer;
}

문제 이해

• 문제에서 블록 번호에 따른 숫자 블록은 블록 번호의 가장 큰 약수이다.
• 10000000의 구간마다 0, 1, 1, 2, 1...의 규칙이 반복된다.

풀이방법

1-1. begin이 1이라면 answer에 0을 담고 continue

1-2. 약수를 체크해서 나머지가 0이고 몫이 10000000이하라면 i / j를 answer에 담고 flag = true를 해준 뒤 break

1-3. flag가 false라면 해당 번호는 소수이므로 1을 answer에 담는다

2. 위를 begin부터 end까지 반복 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    
    for(int i = begin; i <= end; i++) {
        bool flag = false;
        if(i == 1) {
            answer.push_back(0);
            continue;
        }
        
        for(int j = 2; j*j <= i; j++) {
            if(!(i % j) && (i / j <= 10000000)) {
                answer.push_back(i / j);
                flag = true;
                break;
            }
        }
        
        if(!flag) answer.push_back(1);
    }
    
    return answer;
}

풀이방법

좌표평면에서 원의 1사분면에 점을 찍는 방법을 이용하였다.

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

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    long long y = 0;
    
    for(long long x = 0; x <= d; x += k) {
        y = sqrt((long long)d*d - x*x) / k;
        answer += y + 1;
    }    
    
    return answer;
}

풀이방법

record를 공백을 기준으로 3 단어로 잘라 string형 벡터 tmp에 담고 tmp[0]가 Enter, Leave, Change인지 판별한다.

맵 자료구조를 통해 유저 아이디를 Key, 닉네임을 Value로 하여 저장함으로써 Enter나 Change를 통해 유저 아이디에 따른 닉네임이 저장 및 수정될 수 있도록 하였다.

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

using namespace std;

vector<string> solution(vector<string> record) {
    vector<string> answer, userId;
    map<string, string> m;
    
    for(int i = 0; i < record.size(); i++) {
        vector<string> tmp;
        
        string stmp = "";
        for(int j = 0; j < record[i].length(); j++) {
            if(record[i][j] == ' ') {
                tmp.push_back(stmp);
                stmp = "";
            }
            else stmp += record[i][j];
        }
        tmp.push_back(stmp);
        
        if(tmp[0] == "Enter") {
            answer.push_back("님이 들어왔습니다.");
            userId.push_back(tmp[1]);
            m[tmp[1]] = tmp[2];
        }
        else if(tmp[0] == "Leave") {
            answer.push_back("님이 나갔습니다.");
            userId.push_back(tmp[1]);
        }   
        else m[tmp[1]] = tmp[2];
    }
    
    for(int i = 0; i < answer.size(); i++) {
        answer[i] = m[userId[i]] + answer[i];
    }
    
    return answer;
}

풀이방법

간선 방문 체크를 통해 방문한 적이 있다면 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;
}

풀이방법

순열을 이용하여 구할 수 있는 모든 조합을 구한 후 소수인지 판별하고 소수라면 중복을 제거하기 위해 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;
}