C++ 재활용 문제 풀이

자릿수 더하기

숫자의 각 자리수를 더하여 반환하는 문제입니다.

#include <iostream>

using namespace std;
int solution(int n)
{
    int answer = 0;

    while(n > 0){
        answer += (n % 10);
        n /= 10;
    }
        
    cout << "Hello Cpp" << endl;

    return answer;
}

다른 사람 풀이로는 to_string 사용하여 각 위치의 값을 더하는 방식을 사용하였는데 이 과정에서s[i] - '0'으로 아스키 코드 값을 제거해서 숫자 계산하였습니다.

#include <iostream>
#include <string>

using namespace std;
int solution(int n)
{
    int answer = 0;

    string s = to_string(n);

    for(int i = 0; i < s.size(); i++) answer += (s[i] - '0');

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "Hello Cpp" << endl;

    return answer;
}

올바른 괄호

괄호의 특성을 확인하여 열린 괄호와 닫힌 괄호가 정상적으로 이루어졌는지 파악하는 코드입니다.

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    int left_open = 0;
    int right_close = 0;
    for(int i = 0; i < s.size(); i++){
        if(s.at(i) == '(') left_open++;
        else if(s.at(i) == ')') right_close++;
        if (right_close > left_open) {answer = false; break;}
    }
    if(right_close != left_open) answer = false;
    
    cout << "Hello Cpp" << endl;

    return answer;
}

각 괄호의 수에 대한 변수를 계산하여 True, False를 확인했지만 하나의 변수에 대한 증감식을 사용하여 계산하는것이 더욱 깔끔하다고 생각됩니다.(단 ')'가 먼저 들어오는 경우에 대한 예외조건이 필요합니다.)

짝 지어 제거하기

연속된 문자가 나오는 경우에 제거하여 문자열이 남아있는 경우 0 문자열이 모두 사라진 경우 1을 반환하는 코드입니다.

#include <iostream>
#include <string>
using namespace std;

int solution(string s)
{
    int answer = -1;
        
    for(int j = 0; j < s.size(); ){
        if(s.at(j) == s[j+1]) {
            s.erase(j, 2); 
            j = j-2;
            if(j = s.size()) j = 0;
        }
        else j++;
    }
    if(s.size() == 0) answer = 1;
    else answer = 0;
    
    cout << s << endl;

    return answer;
}

초기 풀이 코드로 string의 위치를 찾아가 현재 위치와 다음 위치가 같다면 삭제를 진행하는 방식을 사용하였습니다 j+1위치의 경우 string객체의 범위를 벗어나게 되어 at() 함수 대신 배열 접근 방법을 사용하였습니다.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int solution(string s)
{
    int answer = -1;

    stack<char> cw;
    char tmp;
    for(int j = 0; j < s.size(); j++){
        if(!cw.empty()) tmp = cw.top();
        cw.push(s.at(j));
        if(tmp == cw.top()){
            cw.pop();
            cw.pop();
            tmp = ' ';
        }
    }
    if (cw.empty()) answer = 1;
    else answer = 0;
    
    return answer;
}

다른 사람들의 풀이를 보고 stack을 사용한 방식입니다.
인덱스로 접근하는 방식이 아니라 인덱스 관련 문제가 존재하지 않습니다.

피보나치 수열

피보나치 수열 문제입니다.
마지막 값에 대해서 1234567로 나머지를 구한 값을 반환합니다.

#include <string>
#include <vector>

using namespace std;
int fibonacci(int n);

int fib[100002];

int solution(int n) {
    int answer = 0;
      
    answer = fibonacci(n);
    
    return answer;
}

int fibonacci(int n){
    if(n<=1) {
        fib[n] = n;
        return n;
    }
    else if(fib[n] != 0) return fib[n];
    else {
        fib[n] = (fibonacci(n-1) + fibonacci(n-2)) % 1234567;
        return fib[n];
    }
}

n은 2 이상 100,000 이하인 자연수로 해당 방식에서 마지막 answer에 값을 할당해주는 과정에서 1234567의 값에 대한 나머지를 구하게 되는 경우 int의 범위를 벗어나게 되어 피보나치 함수 내부에서 나눠줌으로서 해당 문제를 해결하였습니다.

숫자의 표현

연속된 자연수의 합으로 입력된 값이 나오는 경우의 수를 출력하는 문제입니다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    int start_num = 1;
    
    while(true){
        int sum = 0;
        int first_num = start_num;
        if(start_num == n || start_num > (n / 2 + 1)){
            answer++;
            break;
        }
        while(sum < n){
            sum += first_num++;
            if(sum == n) answer++;
        } start_num++;

    }
    return answer;
}

숫자가 시작되는 값에 대해 반복문을 수행하여 경우의 수를 반환하였습니다.

JadenCase 문자열 만들기

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
    string answer = "";
    
    for(int i = 0; i < s.length(); i++){
        if(s[i - 1] == ' ' && s.at(i) >= 'a' && s.at(i) <= 'z') {
            answer += s.at(i) - ('a'- 'A');
        }
        else if(s[i - 1] != ' ' && s.at(i) >= 'A' && s.at(i) <= 'Z') {
            answer += s.at(i) + ('a'- 'A');
        }
        else if(s.at(0) >= '0' || s.at(0) <= '9') {answer += s.at(i);}
    }
    if(answer.at(0) >= 'a' && answer.at(0) <= 'z') answer.at(0) -= ('a'- 'A');
        
    return answer;
}

조건문 사용하여 각 조건에 대한 문제 풀이를 진행하였습니다.
아스키 코드로 각 문자에 대한 변환 실행했습니다.
이후 유저들 풀이에서 toupper와 tolower함수 사용하여 풀이한 것을 확인하였습니다.

연속 부분 수열 합의 개수

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

using namespace std;

void get_sum(set<int> &sum, const vector<int>& vec, int len);

int solution(vector<int> elements) {
    int answer = 0;
    set<int> sum;

    for(int len = 1; len <= elements.size(); len++){
        get_sum(sum, elements, len);
    }
    
    answer = sum.size();
    return answer;
}

void get_sum(set<int> &sum, const vector<int>& vec, int len){
    int size = vec.size();
    
     for(int i = 0; i < size; i++){
        int tmp = 0;
        
         for(int j = 0; j < len; j++){
            int idx = (i + j) % size;
            tmp += vec[idx];
        }
        sum.insert(tmp);
    }
}

set : sum을 외부 함수로 넘겨 이중 for 문으로 각 벡터에 대해 연산하고 set에 추가하는 방식을 사용하였습니다.
하지만 for 내부에서 이중 for문인 get_sum을 불러와 시간에 대한 복잡도가 높습니다.

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

using namespace std;

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

    int n = elements.size();

    for (int i = 0 ; i < n ; ++i) {
        int sum = 0;
        for (int j = i ; j < i + n ; ++j) {
            sum += elements[j % n];
            S.insert(sum);
        }
    }

    return S.size();
}

다른 풀이로는 이중 for문으로 계산한 방식으로 이중 for문을 하나의 for문으로 작성하여 시간 복잡도를 줄였습니다.

점프와 순간이동

K칸 이동은 에너지 1 사용, 현재 이동한 위치 x 2의 경우에는 에너지를 소비하지 않을 경우 최소한의 에너지를 사용하여 목적지 n까지 이동하는 문제입니다.

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;
    
    while(n != 1){
        if(n % 2 == 1) {n -= 1; ans++;}
        else n /=2;
    } ans++;
    
    cout << "Hello Cpp" << endl;

    return ans;
}

시작에서 K칸 이동과 이동하는 위치를 계산하는 방법도 있지만 뒤에서 시작하면 더 간편히 써지지 않을까 하여 뒤에서부터 시작하였습니다.

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 1;
    int len = 1;
    while(len != n){
        if(len * 2 <= n) len *= 2;
        else {len++; ans++;}
    } 
    
    cout << "Hello Cpp" << endl;

    return ans;
}

다음은 시작 부분에서 진행한 코드입니다. 다음 코드에서의 문제점은 ans 증가 이후 2배를 하는 것이 더 효율적인지 2배를 한 이후 ans를 증가시키는 것이 더 효율적인지에 대한 보장이 없다는 것입니다. 따라서 해당 코드의 경우에는 BFS 알고리즘을 사용해야 합니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int solution(int n)
{
    // 현재 위치, 현재까지 쓴 배터리
    queue<pair<int, int>> q;
    
    q.push({0, 0});

    vector<int> visited(n + 1, 2100000000);
    visited[0] = 0;

    while(!q.empty()){
        int curr = q.front().first;
        int cost = q.front().second;
        q.pop();

        // 적은 배터리로 이곳에 온 적이 있다면, 지금 경로는 폐기
        if(visited[curr] < cost) continue;

        // 순간이동 (*2)
        if(curr * 2 <= n && visited[curr * 2] > cost) {
            visited[curr * 2] = cost;
            q.push({curr * 2, cost});
        }

        // 점프 (+1)
        if(curr + 1 <= n && visited[curr + 1] > cost + 1) {
            visited[curr + 1] = cost + 1;
            q.push({curr + 1, cost + 1});
        }
    }

    return visited[n];
}

DP도 생각해보았으나 DP는 이전 진행된 값이 고정되어야 하기에 쓰지 못하였습니다.

N개의 최소공배수

하나의 벡터에 있는 모든 원소들에 대한 최소 공배수 값을 구하는 문제입니다.

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

using namespace std;

int gcd(int a, int b);
int lcm(int a, int b);

int solution(vector<int> arr) {
    int answer = 0;
      
    for (int i = 0; i < arr.size() - 1; i++){
        arr.at(i + 1) = lcm(arr.at(i), arr.at(i + 1));
    } answer = arr.at(arr.size() -1);
    
    return answer;
}

int gcd(int a, int b)
{
	int c;
	while (b != 0)
	{
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}
int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

최대공배수를 구하기 위한 최소공배수 함수 gcd를 생성하였습니다.
이전의 값의 최대 공배수를 새로운 비교값 원소로 설정하였습니다.
최소공배수를 구하는 과정에서 원소들간 작은 수가 높은 수의 약수인 경우를 제거하고 최대공배수를 구하면 효율성이 올라갈 수 있을까 생각해보았지만 제거하는 과정에서의 for문에 들어가는 비용이 더 높아 도중 제외했습니다.

영어 끝말잇기

주어진 vector객체를 기반으로 나열이 되었을 끝말잊기를 틀린 사람이 있는지 파악하고 몇번째 어느 사람이 틀렸는지 이야기하는 문제입니다.

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

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;

    for(int i = 1; i < words.size(); i++) {
        if(words[i-1].back() != words[i].front() || 
           find(words.begin(), words.begin() + i, words[i]) != words.begin() + i) {
            answer.push_back((i % n) + 1);
            answer.push_back((i / n) + 1);
            return answer;
        }
    }

    answer.push_back(0);
    answer.push_back(0);
    
    return answer;
}

if문은 마지막 글자와 첫번째 글자의 맞고 틀림을 검사하는것과 동시에 find 함수로 찾은 이터레이터값이 마지막 위치와 같은지를 확인하여 틀리다면 이전 앞에서 먼저 사용한 것으로 판단하여 해당 위치에서의 반복 횟수와 사람의 인덱스를 answer에 추가하는 방식입니다.