99코딩

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다. 
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다. 

예를 들어, 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성해 주세요. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.

• 입력된 수, num은 1 이상 8,000,000 미만인 정수입니다.

풀이 방법

1. 입력된 수가 짝수라면 num /= 2, 홀수라면 num = num*3 + 1을 수행하고 결과로 나온 수에 같은 작업을 반복합니다.

2. 이를 반복할 때마다 answer++을 해줍니다.

3-1. num == 1이되면 break하고 answer를 리턴

3-2. answer == 500이 될 때까지 num == 1이 되지 않는다면 -1을 리턴합니다.

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    int answer = 0;
    
    while(true) {
        if(num == 1) break;
        if(answer == 500) {
            answer = -1;
            break;
        }
        
        if(num % 2 == 0) num /= 2;
        else if( num % 2 == 1) num = num * 3 + 1;
        
        answer++;
    }
    
    return answer;
}

행렬의 덧셈은 행과 열의 크기가 같은 두 행렬의 같은 행, 같은 열의 값을 서로 더한 결과가 됩니다. 2개의 행렬 arr1과 arr2를 입력받아, 행렬 덧셈의 결과를 반환하는 함수, solution을 완성해주세요.

• 행렬 arr1, arr2의 행과 열의 길이는 500을 넘지 않습니다.

풀이 방법

1. 내부를 순회하며 더한 값을 arr3에 저장한 뒤 arr3를 answer에 push_back()한다.

2. 이를 끝까지 반복하고 answer를 리턴

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer;
    
    for(int i = 0; i < arr1.size(); i++){
        vector<int> arr3;
        
        for(int j = 0; j < arr1[i].size(); j++){
            arr3.push_back(arr1[i][j] + arr2[i][j]);
        }
        
        answer.push_back(arr3);
        arr3.clear();
    }
    
    return answer;
}

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

• 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
• 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
• s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
• 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.

문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

• 1 ≤ s의 길이 ≤ 10,000
• s는 영어 소문자로만 이루어져 있습니다.

풀이 방법

1. 문자열의 첫 글자의 인덱스를 나타낼 idx와 x와 같은 글자가 나온 횟수 count1, 다른 글자가 나온 횟수 count2를 선언한다.

2. x와 s[i]를 비교해서 true면 count1++, false면 count2++해준다.

3. count1 == count2면 answer++해주고 idx에 count1 + count2를 더하고 count1과 count2를 0으로 초기화한다.

4. count1 != count2인 상태에서 더 이상 읽을 글자가 없다면 ++answer를 리턴한다.

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    int count1 = 0;
    int count2 = 0;
    int idx = 0;
    char x = s[idx];
    
    for(int i = 0; i < s.length(); i++){
        
        if(x == s[i]) count1++;
        else count2++;

        if(count1 == count2) {
            answer++;
            idx += count1 + count2;
            count1 = 0;
            count2 = 0;
            x = s[idx];
        }
        if ((count1 != count2) && i == s.length() - 1) return ++answer;
    }
}

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

풀이 방법

1. i = 0부터 commands.size()까지 commands[i][0] - 1부터 commands[i][1]까지 배열에 담고 배열을 정렬한 후 commands[i][2] - 1 번째에 있는 원소를 answer에 담는다.

2. 배열을 초기화하고 이를 반복한다.

3. answer 리턴

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

• n은 1 이상 100,000,000 이하인 자연수입니다.

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

• n은 2이상 1000000이하의 자연수입니다.

풀이 방법

1. 제곱근 범위 나누기법을 이용하여 isPrime()에 들어오는 숫자에 따라 소수인지 아닌지 판별한다.

2. isPrime() == true면 숫자가 소수이므로 answer++한다.

3. 1은 소수가 될 수 없으므로 이를 i=2부터 n까지 반복하는 반복문을 작성한다.

4. answer 리턴