JArchive 프로그래밍 일기

문제

실패율 프로그래머스 level1

2019 KAKAO BLIND RECRUITMENT

리뷰

answer에 담아야 하는 건 실패율 높은 순의 '인덱스'이다.

그래서 pair 에 인덱스와 실패율을 담았다. 자료형에 주의하자.

vector<pair<int, double>> per; // <인덱스, 실패율>

// 실패율  =  N스테이지에 위치한 사람 수  / N스테이지 이상에 위치한 사람 수 
double a = count(stages.begin(), stages.end(), i);  // N에 위치한 사람 
double b = count_if(stages.begin(), stages.end(), [i](int elem) { return elem >= i; });  // N 이상인 사람

제한 사항을 주의해야 한다.

• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• bool compare(pair<int, double> a, pair<int, double> b) { if (a.second == b.second) return (a.first < b.first); return (a.second > b.second) ; }

• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

if (b == 0) { // 스테이지에 도달한 사람이 없으면, 실패율 0 
    per.push_back({i , 0 });
    continue;
}

코드

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

// 만약 실패율이 같은 스테이지가 있다면,  작은 번호의 스테이지가 먼저 온다 

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

vector<int> solution(int N, vector<int> stages) {

    vector<int> answer;
    vector<pair<int, double>> per; // <인덱스, 실패율>

    for (int i = 1; i <= N; i++) { // 스테이지 : 1부터 N까지 

        double a = count(stages.begin(), stages.end(), i);  // i에 위치한 사람 
        double b = count_if(stages.begin(), stages.end(), [i](int elem) { return elem >= i; });  // i 이상인 사람

        if (b == 0) { // 스테이지에 도달한 사람이 없으면, 실패율 0 
            per.push_back({i , 0 });
            continue;
        }

        double fail = a / b; 
        per.push_back({i, fail});
    }

    sort(per.begin(), per.end(), compare); 

    for (int i = 0; i < N; i++) { // 인덱스를 answer에 옮긴다 
        answer.push_back(per[i].first);
    }

    return answer;
}

문제

체육복 프로그래머스 level1

리뷰

문제에서 주의할 점은 이 문장이다.

• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다.
• 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

이 점 때문에 헷갈릴 것 같아서. 여벌 가진 학생과 도난당한 학생을 따로 처리했다.

 //  answer 초기화.  모든 학생이 자신의 체육복을 가지고 있다고 가정한다.
int answer = n ;

// 1.  모든 학생이 1개의 체육복을 가지고 있다고 가정한다.
vector<int> student(n+1, 1); 

// 2.  여벌 있는 학생만  + 1 
for (auto i : reserve) { 
    student[i]++;
}

// 3.  도난 당했다면 -1
for (auto i : lost) { 
    student[i]--;
    if (student[i] == 0) answer--; // 0 이라면 정답에서 빼준다. 
}

자신의 앞이나 뒤의 학생에게만 체육복을 빌려줄 수 있다.

따라서 [ 2, 0 ] 인 경우, 내 뒤에 학생에게 빌려주면 [ 1 , 1] 이 된다.

[ 0, 2 ] 인 경우에도, 똑같이 [ 1, 1] 이 된다.

이 두 가지 경우에만 answer를 증가시킬 수 있다.

학생 두 명을 동시에 확인하니까 반복문 인덱스를 주의해야 한다.

    for (int i = 1; i < n; i++) { // 빌려줄 수 있는 경우는 (2, 0) 그리고 (0, 2) 인 경우 뿐이다. 

        if (student[i] == 2 && student[i+1] == 0) {
            student[i] = student[i + 1] = 1;
            answer++;

        }else if(student[i] == 0 && student[i + 1] == 2) {
            student[i] = student[i + 1] = 1;
            answer++;
        }
    }

코드

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

int solution(int n, vector<int> lost, vector<int> reserve) {

    int answer = n;

    vector<int> student(n+1, 1); // 1로 초기화 

    for (auto i : reserve) { // 여벌 있으면 + 1 
        student[i]++;
    }

    for (auto i : lost) { // 도난 당했다면 -1
        student[i]--;
        if (student[i] == 0) answer--;
    }

    for (int i = 1; i < n; i++) { // 빌려줄 수 있는 경우는 (2, 0) 그리고 (0, 2) 인 경우 뿐이다. 

        if (student[i] == 2 && student[i+1] == 0) {
            student[i] = student[i + 1] = 1;
            answer++;

        }else if(student[i] == 0 && student[i + 1] == 2) {
            student[i] = student[i + 1] = 1;
            answer++;
        }
    }

    return answer;
}

문제

최대공약수와 최소공배수 프로그래머스 level1

리뷰

최대공약수는 유클리드 호제법으로 구할 수 있다.

유클리드 호제법은 나머지를 구하는 MOD 연산을 이용한다.

MOD 연산

// MOD 연산 : 나머지를 구하는 연산 
5 % 3 = 2 
// 5를 3으로 나눈 몫은 1 이다. 나머지는 2. 

유클리드 호제법 (Euclidean algorithm)

2개의 자연수에 대해서. a 를 b로 나눈 나머지를 r 이라고 한다면. ( 단, a > b )

a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지를 구하는 과정을 반복하여.

나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대 공약수다.

예시를 읽으면 금방 이해된다. 위키백과 유클리드호제법

14와 24의 최대공약수(GCD, Greatest Common Divisor)

// 24와 14의 최대 공약수 구하기.  주의할 점은 a > b 

24 % 14 = 10 
14 % 10 = 4
10 % 4  = 2
4  % 2  = 0

// MOD 연산 결과가 0 이 되면 종료된다. -->  24와 14의 최대공약수는 2 

나머지가 0 일 때, 나누는 수 2가 최대공약수다.

재귀 코드

// 나머지가 0이 나올 때 종료.
int GCD(int a, int b)   // 단, a > b
{
    if (b == 0) return a;
    else return GCD(b, a%b);
}

반복문 코드

int GCD(int a, int b){  // 단, a > b
    int temp = 0;

    while(b){
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

최소공배수 (LCM, Least Common Multiple)

a 와 b의 최소공배수는 최대공약수를 구하면 계산할 수 있다.

LCM =  a * b * GCD(a, b);

코드

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

int gcd(int a, int b) 
{
    if (b == 0) return a;
    else return gcd(b, a%b);

}

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

    // 큰 값을 앞에, 작은 값을 뒤에.
    int gcd_num = gcd(max(n, m), min(n, m));

    answer.push_back(gcd_num);
    answer.push_back((n*m)/gcd_num);

    return answer;
}

Angry Professor

HackerRank Algorithm

교수님은 최소 k명의 학생이 수업 시작 시간에 도착해야 화가나지 않는다.

음수 는 일찍온 학생. 0은 제시간에 온 학생. 양수는 지각한 학생이다.

음수와 0 의 개수가 k명보다 작거나 같은지 판단하는 문제다.

내 코드

string angryProfessor(int k, vector<int> a) {

    sort(a.begin(), a.end());

    int cnt = 0;
    string answer = "NO";

    for (int i = 0; i < a.size() && cnt < k; i++) {
        if (a[i] <= 0) {
            cnt++;
        }
    }

    if (cnt < k) answer = "YES"; // 화남 

    return answer;
}

Operators

HackerRank Coding Chanllenge Day2

double, int 자료형을 계산하여 실수형이 나오는데.

가장 가까운 int로 답을 출력하는 문제다.

중요한 건 반올림 함수 round() . 가장 가까운 int 로 출력해야 하기 때문이다.

#include <cmath>

//  round(12.62)  -> 12 가 반환된다 
double round(double num);
long double round(long double num);

참고] 버림 함수 trunc()

소수점 아래 수는 정수로 바꾼다.

#include <cmath>

float trunc(float num);
double trunc(double num);
long double trunc(long double num);

// trunc(3.97)  -> 3

truncate 단어를 줄여서 만들었나보다.

내 코드

void solve(double meal_cost, int tip_percent, int tax_percent) {

    double total = meal_cost;
    double tip = (double)tip_percent * meal_cost / 100;
    double tax = (double)tax_percent * meal_cost / 100;

    cout << round(total + tip + tax);

    return;
}

문제

멀쩡한 사각형 프로그래머스 level2

리뷰

가로 W, 세로 H가 1억 이하의 자연수로 들어오기 때문에, 변수들을 long long 형으로 처리해줘야 한다.

넓이를 구할 때 얘네를 곱셈을 하니까 int 표현 범위를 넘어설 수 있기 때문이다.

가로, 세로 비율에 따라서 사용불가한 종이의 개수가 일정하다.

최대공약수가 필요하겠다 싶어서 gcd 함수를 만들었다.

// 재귀 형태 GCD
long long gcd(long long a, long long b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

// 반복문 형태 GCD 
int GCD(int a, int b){

    int i = 1;
    for(i = (a<b)? a:b; i > 0; i--){ // 작은 수를 i로 두고 시작 
        if( (a%i == 0 ) && (b%i == 0) ){ // 둘 다 나누어 떨어지는 숫자를 구하면 탈출 ! 
            break;
        }
    }
    return i;
}

너비 W를 gcd 로 나눈 길이와 높이 H를 gcd로 나눈 길이로 된 사각형에서 규칙성이 발견된다.

예를 들어, 가로 8, 세로 12 라면, 최대공약수 gcd가 4이다.

가로 2, 세로 3 사각형 단위로 종이가 총 6칸이다. 여기서 사용불가 종이가 4개씩 발생한다.

사용불가 종이가 가로2 + 세로3 - 1개 씩 발생한다. ( 4 == 2+3-1)

직사각형 종이의 가로 8, 세로12 에서도 최대공약수 만큼 사용불가 종이가 발생한다.

사용불가 16개 == 8 + 12 - 4

총 넓이 (W * H) 에서 16개를 빼면 답이 나온다.

이 때 W, H를 곱한 수가 int 표현범위를 초과할 수 있으니까 전부 long long 으로 처리한다.

코드

using namespace std;

long long gcd(long long a, long long b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

long long solution(int w,int h) {
    long long answer = 1;
    long long total =(long long)w * h; // 직사각형의 총 넓이  
    long long gcd_num = gcd((long long)w, (long long)h); // W, H의 GCD 

    answer = total - (w + h - gcd_num);

    return answer;
}

처음 짰던 코드

using namespace std;

long long gcd(long long a, long long b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

long long solution(int w,int h) {
    long long answer = 1;
    long long total = (long long)w*h;

    long long gcd_num = gcd((long long)w, (long long)h); // GCD

    long long temp_w = (long long)w / gcd_num; // w를 GCD로 나눈 길이
    long long temp_h = (long long)h / gcd_num; // h를 GCD로 나눈 길이 

    // 사용 불가 종이의 개수  == (temp_w + temp_h -1)
    long long block_cnt = w / temp_w; 
    answer = total - (block_cnt * (temp_w + temp_h -1) );

    return answer;
}

Birthday Cake Candles

HackerRank Algorithm Warmup

벡터에서 최대값 원소를 찾는다.

최대값 원소가 총 몇개인지 리턴하는 문제다.

내 코드

int birthdayCakeCandles(vector<int> a) {
    // 최대 원소 값 
    int max_one = *max_element(a.begin(), a.end());
    // 개수 
    int cnt = count(a.begin(), a.end(), max_one);

    return cnt;
}