JArchive 프로그래밍 일기

문제

멀쩡한 사각형 프로그래머스 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;
}

문제

정수 제곱근 판별 프로그래머스 level1

리뷰

양의 정수 x의 제곱이 아니라면, sqrt() 결과가 실수가 된다.

따라서 정수로 나오는지 실수로 나오는지 구분해야 한다.

// 제곱근을 long long 으로 형변환 한 것과 비교  
sqrt(n) - (long long)sqrt(n)

제곱할 때는 pow() , 제곱근 구하는 sqrt() 가 있다.

pow 도 자료형에 따라 몇 개 더 있으니 정리했다.

#include <cmath>

// x의 y승을 계산하는 pow() 

double pow(double x, double y); // 밑수x, 멱수y 순으로 매개변수 넣기 
float powf(float x, float y);
long double powl(long double x, long double y);

/*
float 4bytes, double 8bytes, long double 8bytes 
*/

내 코드

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

long long solution(long long n) {
    long long answer = -1;  // 양의 정수 x의 제곱이 아니라면 -1 

    if ( (sqrt(n) - (long long)sqrt(n)) == 0) {
        answer = pow(sqrt(n) + 1, 2);
    }

    return answer;
}

다른 사람의 코드

#include <string>
#include <vector>
#include <math.h>
using namespace std;

long long solution(long long n) {
    long long answer = sqrt(n);

    return powl(answer, 2) == n ? powl(answer + 1, 2) : -1;
}

문제

정수 내림차순으로 배치하기 프로그래머스 level1

리뷰

단순하게 숫자 한 자리씩 잘라서 처리해야지 하고 짰다.

1. 정수를 한 자리씩 잘라서 벡터에 넣는다.
2. 정렬한다.
3. 10의 n승으로 바꿔서 더한다.

다른 분의 풀이를 보니 형변환을 하셔서 간단히 푼 코드였다.

정수를 string 으로 형변환

string str = to_string(1234567);

string을 long long 으로 형변환

long long answerll = stoll("1234");

형변환은 PS에서 반드시 알아야 하고 자주 나오는 요소니까 자주 쓰면서 숙지하자!

내 코드

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

long long solution(long long n) {
    long long answer = 0;
    vector<int> v; 

    while (n) {
        v.push_back(n % 10);
        n /= 10;
    }

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

    for (int i = 0; i < v.size(); i++) {
        answer += ( pow(10, i) * v[i] );
    }

    return answer;
}

다른 사람의 코드

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

long long solution(long long n) {
    long long answer = 0;

    string str = to_string(n);
    sort(str.begin(), str.end(), greater<char>());
    answer = stoll(str);

    return answer;
}

문제

베스트앨범 프로그래머스 level3

리뷰

해시 카테고리의 문제다.

map을 잘 다루면 풀 수 있는 문제였다.

장르 별로 가장 많이 재생된 노래 2개 씩 모아 앨범을 출시한다.

1. 속한 노래가 많이 재생된 장르를 내림차순으로 정렬한다.

// 장르명, 재생횟수 
map<string, int> genre_cnt;

2. 장르 내에서 많이 재생된 노래를 내림차순으로 정렬한다.

// 장르명 string,   <재생횟수, 고유번호> pair로 vector를 저장한다. 
map<string, vector<pair<int,int>>> genre_playlist;  

3. 장르 내에서, 재생횟수가 같은 노래 중에는 고유번호가 낮은 노래를 수록한다.

// 장르명, 재생횟수를 저장한다. 
vector<pair<string, int>> genre_v;

코드

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

bool compare(pair<int,int> a, pair<int,int> b){
    return a.first > b.first; // 재생횟수 내림차순  
}

bool compare_song_cnt(pair<string,int> a, pair<string,int> b){
    return a.second > b.second; // 노래 개수 내림차순  
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;

    map<string, int> genre_cnt; // 장르별 재생횟수 
    map<string, vector<pair<int,int>> > genre_playlist; // 장르별 노래의 재생횟수 및 고유번호
    vector<pair<string, int>> genre_v;  // 장르별 노래 개수 

    for(int i = 0; i < genres.size(); i++){
        genre_cnt[genres[i]] += plays[i]; // 장르별 재생횟수 누적
        genre_playlist[genres[i]].push_back({plays[i], i}); // 장르별 노래의 재생횟수 및 고유번호 
    } 

     // 재생횟수를 이용하여 내림차순 정렬 
    for( auto &song : genre_playlist){
        sort(song.second.begin(), song.second.end(), compare);    
    }    

     genre_v.assign(genre_cnt.begin(), genre_cnt.end()); // 장르별 노래 개수
    sort(genre_v.begin(), genre_v.end(), compare_song_cnt); // 내림차순  

    for(int i = 0; i <genre_v.size(); i++){ // 장르 종류만큼 반복

        string genre_name = genre_v[i].first; // 장르 이름  

        // genre_playlist 에서 최대 2곡까지 선택 가능 (j < 2)
        for(int j = 0; ( j <genre_playlist[genre_name].size() && j < 2 ); j++){ 
            answer.push_back(genre_playlist[genre_name][j].second);
        } 
    }

    return answer;
}

문제

x만큼 간격이 있는 n개의 숫자 문제링크

프로그래머스 level 1

문제 설명

함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요.

제한 조건

• x는 -10000000 이상, 10000000 이하인 정수입니다.
• n은 1000 이하인 자연수입니다.

입출력 예

리뷰

자료형을 주의하면 되는 문제였다.

int

4byte 크기 (대강 -2,147,000,000 ~ 2,147,000,000 )

printf 서식문자 %d

long long

8byte 크기

-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

printf 서식문자 %lld

자료형 출력시 서식문자는 자꾸 헷갈리지만.. 자꾸 보면 익숙해지겠지.

코드

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(int x, int n) {
    vector<long long> answer;
    long long init_num = x;

    for(; n>0; n--){ 
        answer.push_back(init_num);
        init_num += x;
    }

    return answer;
}

문제

모의고사

프로그래머스 level 1

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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하는 값을 오름차순 정렬해주세요.

입출력 예

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

리뷰

가장 높은 점수를 받은 사람이 여럿인 경우에 오름차순 정렬 출력을 어떻게 할지가 고민이었다.

일단 max() 함수로 최고점 받은 사람을 알아내고 나니깐 풀렸다.

코드

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

int first[] = {1, 2, 3, 4, 5};
int second[] = {2, 1, 2, 3, 2, 4, 2, 5};
int third[] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

vector<int> solution(vector<int> answers) {

    vector<int> answer;
    vector<int> score = {0, 0, 0}; // 수포자 1, 2, 3번이 맞춘 문제 개수 

    int len_answer = answers.size();
    int i = 0, max_score = 0;

    for(i=0; i<len_answer; i++){

        if(answers[i] == first[i%5]) score[0]++;
        if(answers[i] == second[i%8]) score[1]++;        
        if(answers[i] == third[i%10]) score[2]++;
    }
    // 셋 중에 최대값  
    max_score = max(score[0], max(score[1], score[2]) );

    for(i=0; i<3; i++){
        if(max_score == score[i]) {
            answer.push_back(i+1);
        }
    }

    return answer;
}

문제

같은 숫자는 싫어

프로그래머스 level 1

문제 설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

리뷰

수열의 순서는 유지하되, 중복숫자만 걷어내면 된다.

iterator를 사용해서 erase 하려다가 잘 안되서 새 벡터에 옮겨담아서 풀었다.

다른 풀이를 보니 unique() 함수로 erase() 한 코드가 있었다.

unique()함수는 헤더를 추가해서 사용하면 된다.

범위 내에 중복된 원소를 제거한다.

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

int main(){
    vector<int> arr v{1, 1, 3, 0, 0};
    v.unique(arr.begin(), arr.end());  // unique(시작점, 끝점)

    return 0;
}

unique와 erase로 중복제거 참고 포스팅

c++ 레퍼런스

다른 분들 코드

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

vector<int> solution(vector<int> arr) 
{

    arr.erase(unique(arr.begin(), arr.end()),arr.end());

    vector<int> answer = arr;
    return answer;
}

코드

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

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    int i = 0;
    int temp = arr[0];

    answer.push_back(temp);

    for(i=1; i<arr.size(); i++){

        if(temp != arr[i]){ // 직전 숫자와 다르면 push_back()
            answer.push_back(arr[i]);
        }
        temp = arr[i];
    }

    return answer;
}

도움이 되셨다면 '공감'을 눌러주세요 :)