99코딩

프로그래머스 - 카펫

1. 모든 격자의 수의 합은 brown + red, 카펫의 가로, 세로 길이는 최소 3이상이다.

2. 반복문을 돌리며 width에 sum을 height로 나눈 몫을 대입한다.

3. sum이 height로 나누어 떨어지고 (width -2)*(height-2) 즉 테두리를 1줄을 제외한 부분의 값이 yellow와 같으면 answer에 width와 height를 담고 break한다.

4. answer 리턴

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int sum = brown + yellow;
    
    for(int height = 3;;height++){
        int width = sum / height;
        if(!(sum % height) && (width - 2)*(height - 2) == yellow) {
            answer.push_back(width);
            answer.push_back(height);
            break;
        }
    }
    
    return answer;
}

프로그래머스 - 짝지어 제거하기

풀이 방법

1.  스택처럼 사용할 문자열 str 선언

2-1.  str이 비어있거나 str의 마지막 문자, 즉 top이 s[i]와 다르면 str에 s[i] 삽입

2-2. top과 s[i]가 같다면 pop 해준다.

3 반복문을 마치고 str이 비어있으면 1을 리턴, 아니라면 0을 리턴한다.

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

int solution(string s)
{
    string str = "";
    if(s.length() % 2) return 0;
    
    for(int i = 0; i < s.length(); i++) {
        if (str.empty() || str.back() != s[i]) str += s[i];
        else if (str.back() == s[i]) str.pop_back();
    }
    
    if (str.empty()) return 1;
    else return 0;
}

프로그래머스 - 다음 큰 숫자

풀이방법

1. 들어오는 숫자를 이진변환한 후 1의 숫자를 세어 반환하는 함수를 선언한다.

2. n의 이진변환 시의 1의 갯수 num1과 num3의 이진변환 시의 1의 갯수 num2가 같으면 num3를 리턴한다.

#include <string>
#include <vector>

using namespace std;

int CountOne(int n) {
    int count = 0;
    string s = "";
    
    while(n > 0) {
        if(n % 2) {
            s = "1" + s;
            count++;
        }
        else s = "0" + s;
        n /= 2;
    }
    
    return count;
}

int solution(int n) {
    int answer = 0;
    
    int num1 = CountOne(n);
    int num2 = 0;
    int num3 = n;
    
    while(num1 != num2) {
        num3++;
        num2 = CountOne(num3);
    }
    
    return num3;
}

프로그래머스 - 최솟값 만들기

풀이 방법

큰 숫자와 작은 숫자끼리 곱해서 더해야 결과가 작게 나온다는 것을 이용

1. A를 오름차순으로 B를 내림차순으로 정렬한다.

2. 이후 같은 인덱스의 원소끼리 곱한 뒤 answer에 더한다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), greater<int>());
    
    for(int i = 0; i < A.size(); i++){
        answer += A[i] * B[i];
    }
    
    return answer;
}

프로그래머스 - 피보나치 수

아래처럼 재귀호출을 사용했더니 시간 초과가 떠서 배열로 풀었다.

#include <string>
#include <vector>

using namespace std;

int Fibonacci(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return Fibonacci(n - 1) + Fibonacci(n - 2) % 1234567;
}

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

풀이 방법

1. int형 벡터 컨테이너 Fibonacci를 선언한다.

2. n은 2 이상인 자연수이므로 0, 1 인덱스에 각각 F(0), F(1)에 해당하는 값을 넣어준다.

3. 이후 2부터 n까지 F(i - 1) + F(i - 2) % 1234567을 담는다. (오버플로우 방지)

4. n번째 피보니치 수를 1234567로 나눈 나머지를 리턴 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> Fibonacci;
    
    Fibonacci.push_back(0);
    Fibonacci.push_back(1);
    
    for(int i = 2; i <= n; i++){
        Fibonacci.push_back((Fibonacci[i - 1] + Fibonacci[i - 2]) % 1234567);
    }
    
    answer = Fibonacci[n];
    
    return answer;
}

프로그래머스 - 올바른 괄호

풀이 방법

1. 괄호가 짝지어진 것을 판단하기 위해 int형 countBracket을 선언

2. s[0]가 ')'면 괄호가 제대로 짝이 지어질 수 없으므로 false를 리턴하고 아니면 countBracket++을 해준다.

3. s[i]가 '('면 countBracket++을 해주고 ')'면 countBracket--를 해준다.

4. 이를 반복하며 도중에 countBracket이 음수가 되면 제대로 짝이 지어지지 않으므로 false를 리턴

5. 반복문이 끝난 뒤 countBracket이 0이면 괄호가 올바르게 짝지어졌으므로 true 리턴

6. 아니라면 false 리턴

#include <string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    int countBracket = 0;
    
    if(s[0] == ')') return false;
    else countBracket++;
    
    for(int i = 1; i < s.length(); i++){
        if(s[i] == '(') countBracket++;
        else if(s[i] == ')') countBracket--;
        
        if(countBracket < 0) return false;
    }
    
    if(countBracket == 0) return true;
    else return false;
}

프로그래머스 - 숫자의 표현

풀이 방법

1. sum이 n보다 커질 때까지 num부터 시작해서 num++한 값을 계속 sum에 더한다.

2. sum == num이면 answer++ 해준다.

3. 이를 i부터 n까지 반복

4. answer 리턴

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    for(int i = 1; i <= n; i++) {
        int num = i;
        int sum = 0;
        while(sum <= n){
            sum += num;
            
            if (sum == n) answer++;
            
            num++;
        }
    }
    
    return answer;
}

프로그래머스 - 이진 변환 반복하기

풀이 방법

1. int형 count, countZero와 문자열 temp를 선언합니다.

2. 문자열 s의 i번째 문자가 0이면 countZero++을 하고 1이면 temp += "1"을 해줍니다.

3. 추가로 선언한 num에 temp.length()를 대입하고 문자열 s를 비워줍니다.

4. num이 0이 아닐 때까지 이진 변환을 반복합니다.

5. count++을 해주고 이를 s가 "1"이 될때까지 반복합니다.

6. 반복문이 끝나면 count와 countZero를 answer에 담고 리턴

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    
    int count = 0;
    int countZero = 0;
    
    
    while(s != "1") {
        string temp = "";
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '0')
                countZero++;
            else 
                temp += '1';
        }
        
        int num = temp.length();
        
        s = "";
        while(num > 0){
            if(num % 2) s = "1" + s;
            else s = "0" + s;
            
            num /= 2;
        }
        
        count++;
    }
    
    answer.push_back(count);
    answer.push_back(countZero);
    
    return answer;
}