오산마 study day 5

DaewoongJeon·2021년 3월 6일
0

OSanMa Algorithm Study

목록 보기
5/10
  • 날짜 : 2021. 3. 5. (금)

1. 목표

A. 프로그래머스 코테 문제 1단계 6문제, 2단계 2문제 풀기

2. 프로그래머스 코테 문제 1단계 6문제, 2단계 2문제

  • 푼 문제 list
  1. 소수 만들기 https://programmers.co.kr/learn/courses/30/lessons/12977
  2. 직사각형 별찍기 https://programmers.co.kr/learn/courses/30/lessons/12969
  3. 예산 https://programmers.co.kr/learn/courses/30/lessons/12982
  4. [1차]비밀지도 https://programmers.co.kr/learn/courses/30/lessons/17681
  5. 실패율 https://programmers.co.kr/learn/courses/30/lessons/42889
  6. [1차]다트 게임 https://programmers.co.kr/learn/courses/30/lessons/17682
  7. 스킬트리 https://programmers.co.kr/learn/courses/30/lessons/49993
  8. 기능개발 https://programmers.co.kr/learn/courses/30/lessons/42586

A. 소수 만들기

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

int solution(vector<int> nums) {
    int answer = 0;
    vector<int> result;
    result.push_back(1);
    result.push_back(1);
    for (int i = 2; i <= 3000; i++)
        result.push_back(1);
    for (int i = 2; i * i <= 3000; i++)
    {
        if (result[i] == 1)
        {
            for (int j = i * i; j <= 3000; j += i)
            {
                result.erase(result.begin() + j);
                result.emplace(result.begin() + j, 0);
            }
        }
    }
    for (int i = 0; i < nums.size() - 2; i++)
    {
        for (int j = i + 1; j < nums.size() - 1; j++)
        {
            for (int z = j + 1; z < nums.size(); z++)
            {
                if (result[nums[i] + nums[j] + nums[z]] == 1)
                    answer++;
            }
        }
    }
    return answer;
}
  • 코드 설명
  1. 에라토스테네스의 체를 활용하여 nums를 모두 더한 값의 최댓값인 3000이하의 소수를 모두 찾는다.
  2. for loop 세개를 중첩시켜서 nums에 입력된 세 개의 인자를 차례대로 더해주었다.
  3. 더한 값이 소수인지 판별하여 소수일 경우 return할 answer를 1씩 증가시켰다.

B. 직사각형 별찍기

#include <iostream>
#include <stdio.h>

using namespace std;

int main(void) {
    int n;
    int m;
    cin >> n;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("*");
        }
        printf("\n");
    }
    return 0;
}
  • 코드 설명
  1. 표준입력으로 n과 m을 입력받는다.
  2. n과 m이 최대인 두 번의 for loop를 통해 *을 출력하고 줄 마지막 마다 개행문자('\n')를 출력한다.
  • 부가 설명
  1. cpp 에서 표준입력은 cin을 통해 수행한다.(c에서의 scanf라고 생각하면 됨)

C. 예산

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0;
    int result = 0;
    sort(d.begin(), d.end());
    for (int i = 0; i < d.size(); i++)
    {
        result += d[i];
        if (result > budget)
            break;
        answer++;
    }
    return answer;
}
  • 코드 설명
  1. sort 함수를 활용하여 입력받은 d vector를 오름차순 정렬한다.
  2. result int 변수에 오름차순으로 정렬된 d vector 값을 순서대로 더하고 예산인 budget을 초과하는 경우, for loop를 나와서 현재 answer 값을 return 한다.
  • 부가 설명
  1. sort(d.begin(), d.end()) : d vector의 begin()위치에서 end()위치까지 정렬을 수행한다는 의미이고, 세번째 매개변수로 아무것도 안들어갔을 경우, 자동으로 오름차순 정렬을 수행한다.

D. [1차]비밀지도

#include <string>
#include <vector>

using namespace std;

string ft_bitset(int tmp, int n)
{
    string result = "";
    for (int i = 0; i < n; i++)
    {
        if (tmp != 0)
        {
            result = to_string(tmp % 2) + result;
            tmp /= 2;
        }
        else
            result = '0' + result;
    }
    return (result);
}

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    int tmp;
    string str_tmp;
    string str_tmp2;
    for (int i = 0; i < n; i++)
    {
        tmp = arr1[i] | arr2[i];
        str_tmp = ft_bitset(tmp, n);
        str_tmp2 = "";
        for (int j = 0; j < n; j++)
        {
            if (str_tmp[j] == '1')
                str_tmp2 += '#';
            else
                str_tmp2 += ' ';
        }
        answer.push_back(str_tmp2);
    }
    return answer;
}
  • 코드 설명
  1. 두 지도의 데이터가 담긴 arr1 vector와 arr2 vector, 정사각형 지도의 크기인 n을 입력으로 받는다.
  2. 같은 index에서 두 arr vector의 이진데이터 값이 하나라도 1일 경우, 원본 데이터는 1을 가리킨다.
  3. 위를 활용하여 for loop를 통해 각 index마다 arr1과 arr2간 비트 or연산을 수행한다.(or 연산은 두 비트가 하나라도 1일 시에 1을 출력하는 연산이다.)
  4. ft_bitset 함수를 활용하여 비트연산된 tmp 십진수 값을 이진수 값으로 변환하여 string 형태로 반환한다.
  5. 반환된 이진데이터 각 index의 값을 for loop를 통해 검사할 것이고, 이진 데이터가 1일 경우, '#' 0일 경우, ' '을 str_tmp2 string 변수에 더해준다.
  6. 모두 더해진 str_tmp2를 answer string vector에 차곡차곡 쌓는다.
  • 부가 설명
  1. bitset 클래스 내부의 bitset 함수를 활용하여 2진수로 변환할 수 있다. 하지만 오류가 발생하였고 오류 원인은 현재 파악이 안된상태이다.

E. 실패율

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

using namespace std;

bool compare(pair<int,double> a, pair<int,double> b)
{
    if (a.second != b.second)
        return (a.second > b.second);
    else
        return (a.first < b.first);
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<int,double>> answer_tmp;
    pair<int,double> pair_tmp;
    vector<int> vec_tmp(N + 2, 0);
    int tmp = stages.size();
    for (int i = 0; i < stages.size(); i++)
        vec_tmp[stages[i]]++;
    for (int i = 1; i <= N; i++)
    {
        if (vec_tmp[i] > 0)
        {
            pair_tmp.first = i;
            pair_tmp.second = (double)vec_tmp[i] / (double)tmp;
            answer_tmp.push_back(pair_tmp);
            tmp -= vec_tmp[i];
        }
    }
    sort(answer_tmp.begin(), answer_tmp.end(), compare);
    // pair<int, double> abcd;
    // for (int i=answer_tmp.size()-1; i>=1; i--)
    // {
    //     for (int j=i-1; j>=0; j--)
    //     {
    //         if (answer_tmp[i].second > answer_tmp[j].second)
    //         {
    //             abcd = answer_tmp[i];
    //             answer_tmp[i] = answer_tmp[j];
    //             answer_tmp[j] = abcd;
    //         }
    //     }
    // }
    for (int i = 0; i < answer_tmp.size(); i++)
        answer.push_back(answer_tmp[i].first);
    int i = 1;
    while (1)
    {
        if (answer.size() == N)
            break;
        if (vec_tmp[i] == 0)
            answer.push_back(i);
        i++;
    }
    return answer;
}

F. [1차]다트 게임

#include <string>
#include <vector>

using namespace std;

int solution(string dartResult) {
    int answer = 0;
    string str_tmp;
    int int_tmp = 1;
    int index = -1;
    vector<int> score;
    vector<int> option(3, 0);
    vector<int> bonus;
    for (int i = 0; i < dartResult.size(); i++)
    {
        if (dartResult[i] >= '0' && dartResult[i] <= '9')
        {
            if (dartResult[i] == '1' && dartResult[i + 1] == '0')
            {
                score.push_back(10);
                i++;
            }
            else
            {
                str_tmp = dartResult.at(i);
                score.push_back(stoi(str_tmp));
            }
            index++;
        }
        if (isalpha(dartResult[i]))
        {
            if (dartResult[i] == 'S')
                int_tmp = 1;
            else if (dartResult[i] == 'D')
                int_tmp = 2;
            else if (dartResult[i] == 'T')
                int_tmp = 3;
            bonus.push_back(int_tmp);
        }
        if (dartResult[i] == '#')
            option.emplace(option.begin() + index, -1);
        else if (dartResult[i] == '*')
            option.emplace(option.begin() + index, 2);
    }
    for (int i = 0; i < score.size(); i++)
    {
        int_tmp = 1;
        if (option[i] == -1)
            int_tmp *= -1;
        for (int j = i; j < option.size() && j < i + 2; j++)
        {
            if (option[j] == 2)
                int_tmp *= 2;
        }
        for (int j = 0; j < bonus[i]; j++)
            int_tmp *= score[i];
        answer += int_tmp;
    }
    return answer;
}
  • 코드 설명
  1. 첫 for loop를 통해 입력으로 받은 dartResult를 score, bonus, option vector에 알맞게 파싱하여 넣는다.
  2. 두번째 for loop에서 알맞게 파싱한 score, bonus, option 데이터를 활용하여 최종 점수를 도출한다.

G. 스킬트리

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int tmp;
    int flag;
    for (int i = 0; i < skill_trees.size(); i++)
    {
        tmp = -1;
        flag = 1;
        for (int j = 0; j < skill_trees[i].size() && flag == 1; j++)
        {
            for (int z = 0; z < skill.size() && flag == 1; z++)
            {
                if (skill[z] == skill_trees[i][j])
                {
                    if (tmp == z - 1)
                        tmp = z;
                    else
                    {
                        flag = 0;
                        break;
                    }
                }
            }
        }
        if (flag == 1)
            answer++;
    }
    return answer;
}
  • 코드 설명
  1. flag int 변수를 활용하여 입력으로 받은 스킬트리가 유효한 스킬트리인지 판별할 것이다.
  2. tmp int 변수를 활용하여 스킬트리가 skill string에 맞게 순서대로 짜여있는지 확인할 것이다.
  3. 스킬트리 변수 내에 있는 값이 skill 변수 안에 있는 값과 일치할 경우, 해당 index 값을 tmp와 비교하여 해당 스킬차례가 맞는지 확인할 것이고, 맞다면 tmp를 해당 index로 갱신시켜준다.

H. 기능개발

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int index = 0;
    int int_tmp;
    int j;
    for (int i = 0; index < progresses.size(); i++)
    {
        int_tmp = progresses[index] + (speeds[index] * i);
        if (int_tmp >= 100)
        {
            for (j = index; j < progresses.size(); j++)
            {
                int_tmp = progresses[j] + (speeds[j] * i);
                if (int_tmp < 100)
                {
                    int_tmp = j - index;
                    index = j;
                    break;
                }
            }
            if (j == progresses.size())
            {
                int_tmp = j - index;
                index = j;
            }
            answer.push_back(int_tmp);
        }
    }
    return answer;
}
  • 코드 설명
  1. index는 다음 바로 배포될 서비스를 가리킨다. 0으로 초기화 되어 있다.
  2. 첫번째 for loop에서 index에 해당하는 서비스가 100이 되었는지 speed에 곱해지는 i를 1씩 증가시키면서 확인한다.
  3. index에 해당하는 서비스가 100을 넘으면 그 뒤의 서비스들도 연속적으로 100을 넘는지 확인한다.
  4. 100을 안넘는 서비스를 만나면 index를 해당 서비스의 index로 갱신시키고 100을 넘는 서비스의 갯수를 int_tmp에 입력하여 두번째 for loop를 종료한다.
  5. int_tmp에 입력된 수는 answer vector에 차곡차곡 입력된다.
profile
DaewoongJeon
이전 포스트

오산마 study day 4

다음 포스트

오산마 study day 6

0개의 댓글