아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.
- 모두 해결
1. 스킬트리
문제 설명
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
제한 조건
- 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 스킬 순서와 스킬트리는 문자열로 표기합니다.
- 예를 들어, C → B → D 라면 "CBD"로 표기합니다
- 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
- skill_trees는 길이 1 이상 20 이하인 배열입니다.
- skill_trees의 원소는 스킬을 나타내는 문자열입니다.
- skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
입출력 예
풀이
#include <string>
#include <vector>
using namespace std;
int solution(string skill, vector<string> skill_trees) {
int answer = 0;
int skill_pos = 0;
int flag = 0;
for (int i = 0; i < skill_trees.size(); i++)
{
skill_pos = 0;
flag = 0;
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(z == skill_pos)
{
skill_pos += 1;
}
else
flag = -1;
}
}
}
if (flag == 0)
answer += 1;
}
return answer;
}설명
- skill의 값은 순서대로 skill_trees에 적힐수 있는데, 만약 순서대로 나와 있지 않으면 카운터를 하지 않도록 로직을 설계하였다.
2. 기능개발
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 /* 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
풀이
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
vector<int> answer;
vector<int> tmp = speeds;
int sp_i = 0;
int save;
while (sp_i < speeds.size())
{
save = 0;
for (int i = sp_i; i < speeds.size(); i++)
{
if (progresses[i] == 0)
{
sp_i += 1;
save += 1;
}
else
break;
}
if (save != 0)
answer.push_back(save);
for (int j = sp_i; j < speeds.size(); j++)
{
if (progresses[j] < 100)
progresses[j] += tmp[j];
else
{
tmp[j] = 0;
progresses[j] = 0;
}
}
}
return answer;
}설명
- 현재 인덱스를 따로 만들어 주고, 해당인덱스의 작업이 100프로 완료가 되면, for 구문을 통해, 해당 인덱스와 뒤에오는 인덱스들이 작업이 끝나는지 확인하도록 for 구문을 따로 주어 로직을 완성하였다.
3. 멀쩡한 사각형
문제 설명
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
코드를 입력하세요제한사항
- W, H : 1억 이하의 자연수
입출력 예
풀이
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
long long solution(int w, int h) {
long long answer = 1;
long long max = (long long)(w * h);
double ww = (double)w;
double hh = (double)h;
double aw = ww/hh;
double ah = hh/ww;
int sum = 0;
double sum_w = ww/hh;
double sum_h = hh/ww;
double tmp;
while(sum_w <= ww && sum_h <= hh)
{
if(sum_w < sum_h)
{
sum_w += aw; // 8/12
}
else if(sum_h < sum_w)
{
sum_h += ah; // 12/8
}
else
{
sum_h += ah;
sum_w += aw;
}
sum++;
}
max = max -(long long)sum;
return max;
}설명
- 대각선과 겹치지 않는 부분만 세어주면 된다.
- 기울기에 내림이나 올림을 이용해, 색칠된 네모들만 카운트 해 주엇다.
