'전체 글'에 해당되는 글 186건

프로그래머스 - 코딩테스트 고득점 키트

https://programmers.co.kr/learn/courses/30/lessons/42747

문제

풀이

해당 문제는 굉장히 복잡해보이지만 사실 간단한 규칙을 찾으면 풀 수 있다.

먼저 인용횟수를 내림차순으로 정렬한다.

그럼 예시로 주어진 벡터이 경우 6, 5, 3, 1, 0 순으로 정렬된다.

이 벡터를 탐색하면서 for loop를 돈다.

맨 앞에서부터 루프문을 돌며 

i = 0, citation 6 이상의 논문 1편 이상, 

i = 1, citation 5 이상의 논문 2편 이상,

i = 2, citation 3 이상의 논문 3편 이상,

i = 3, citation 1 이상의 논문 4편 이상, 

i = 4, citation 0 이상의 논문 5편 이상,

이 때 h의 최대값은 무엇일까, 바로 citations[i] 의 값이 i+1보다 작거나 같아지는 최초의 시점이다.

따라서 이를 코드로 구현하면 풀이가 가능하다.

코드

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

int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.begin(), citations.end(), greater<int>());
    for(int i = 0; i < citations.size(); i++)
    {
        if(citations[i] >= (i+1))
            answer++;
    }
    return answer;
}

평가

규칙을 찾아내는 것이 다소 혼란스러울 수 있는 문제지만, 규칙만 찾아낸다면 구현 자체의 난이도는 높지 않은 문제이다.

정렬을 활용한 트릭문제는 대부분 규칙성을 빠르게 찾아야하기 때문에, 입력 예시값을 이리 저리 정렬해보면서 여러가지 풀이 방법을 고민하는것이 좋다.

프로그래머스 - 코딩 테스트 고득점 키트

https://programmers.co.kr/learn/courses/30/lessons/42746

문제

풀이

이 문제를 풀이하는 방법은, 무조건 주어진 숫자의 첫번째 자리수가 가장 큰 것을 먼저 둬야한다는것이다.
그리고 자리수가 같을 경우에는 어떻게 합쳤을때가 더 큰지를 비교해야하는데, 이는 각 숫자를 문자열화 시키면 쉽게 풀이가 가능하다.

먼저 to_string 함수를 통해서 입력된 숫자값들을 문자열로 전환해준뒤, str_numbers라는 string 벡터에 push한다.

string에서 +연산은 문자열을 합치는 연산이므로 a+b와 b+a를 비교했을때 어떤 것이 더 큰지를 비교하는 compare함수를 만들어준뒤, sort함수를 사용한다. 

그 후 정렬된 순서대로 앞에서부터 쓰면 정답을 얻을 수 있다.

코드

#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

bool compare(string a, string b)
{
    return a+b > b+a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> str_numbers;
    for(auto number : numbers)
        str_numbers.push_back(to_string(number));     
    sort(str_numbers.begin(),str_numbers.end(),compare);
    if(str_numbers[0] == "0")
        return "0";
    for(auto number : str_numbers)
        answer += number;
    return answer;
}

평가

compare함수를 통해 문자열 a+b, b+a의 값을 내림차순으로 정렬하여 풀 수 있다는 것을 알아둬야하는 문제이다.

STL의 sort함수와 compare의 활용법을 알아두면 풀이가 가능하다.

해당 문제를 int형 숫자를 써서 풀려고하면 다소 복잡해지므로 to_string함수를 사용하는 방법에 대해서 잘 알아두고 넘어가자.

프로그래머스 - 코딩테스트 고득점 키트

https://programmers.co.kr/learn/courses/30/lessons/42748

문제

풀이

구간 for문을 사용하여 배열에 i번째 수부터 j번째 숫자까지 자른 후 tmp라는 벡터에 넣어준 뒤, STL의 sort함수를 사용하여 tmp 벡터 정렬을 진행한다.

그 후, k번째의 수를 결과값을 저장하는 벡터인 answer에 push해준다. tmp벡터의 값을 clear()를 통해 삭제시킨 후, 다음 command에 대한 i,j,k연산을 진행한다.

모든 답을 구하면 answer 벡터를 반환한다.

코드

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

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> tmp;
    for(auto command : commands)
    {
        for(int i = command[0]-1; i < command[1]; i++ )
            tmp.push_back(array[i]);
        sort(tmp.begin(),tmp.end());
        answer.push_back(tmp[command[2]-1]);
        tmp.clear();
    }
    return answer;
}

평가

구간 for문에 대한 활용법과 vector를 다루는 방법을 알면 풀 수 있는 문제이다.

벡터에 대한 STL Sort활용법을 확실히 알고 넘어가도록 하자.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/42578

문제

풀이

먼저 각 부위에 해당하는 의상의 개수를 구하는 해시맵을 하나 선언한 후,

입력으로 받은 값의 형식이 [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]의 형식이므로 해시맵 myclothes를 선언한 후, myclothes[headgear], myclothes[eyewear]에 각각 몇개의 경우의 수가 있는지를 저장한다.

그 후, 조합할 수 있는 옷의 개수를 구하면 되는데 구하는 방식은 아주 간단하다.

반드시 의상을 1개를 입어야하며, 매번 다른 방식으로 입어야 한다는 조건이 있다.

따라서 headgear 2개, eyewear 1개가 있는 보기의 경우에 조합을 구하는 방법은 

yellow_hat을 쓰는 경우, green_turban을 쓰는 경우, 모자를 안쓰는 경우.

blue_sunglasses를 쓰는 경우, 안경을 안쓰는 경우.

이런식으로 고려해볼 수 있는데, 이 때 조합을 구하는 방법은 (2+1) * (1+1) = 6이다.

이 때 모자도 안쓰고 안경도 쓰지 않는것은 제약조건에 의해 불가능하므로 1을 빼준 값인 5가 리턴값이 된다.

이를 알고리즘으로 구현하면 아래와 같다.

코드

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<vector<string>> clothes) {
    unordered_map <string, int> myclothes;
    int answer = 1;
    for(auto item : clothes)
            myclothes[item[1]]++;
    for(auto tmp : myclothes)
        answer *= (tmp.second+1);
    return answer-1;
}

평가

옷에 대한 모든 조합을 어떻게 구할지 고민에 빠지면 시간을 많이 잡아먹는 문제이다.

경우의 수를 1번 모자를 쓰는경우, 2번모자를 쓰는경우, 그리고 안 쓰는 경우 이런식으로 나눠서 접근해야 단순곱으로 쉽게 문제를 해결할 수 있다.

아마 코드길이가 굉장히 길어지게 푸신분들은 모자를 안쓰는 경우, 안경을 안쓰는 경우를 고려하지 않고 그냥 Brute Force방식으로 모든 조합을 구하신 분들일 것 같다.

프로그래머스 - 코딩 테스트 고득점 키트

https://programmers.co.kr/learn/courses/30/lessons/42576

문제

풀이

unordered_map 자료형을 사용하여 해당 이름이 몇번 입력됬는지를 저장하는 해시맵을 구현하고,

completion에 들어온 사람들중에 participant에 없는 사람을 찾는 방식으로 풀이를 진행할 수 있다.

completion안에 있는 사람의 이름과 해당 이름의 출현회수를 저장하는 strkey 해시맵을 선언하고, 

participation 안에 있는 사람의 이름을 strkey안에서 검색한다.

만약 strkey안에 없는 이름이 나올 경우 그 사람은 참가자에는 있지만 완주자 리스트에는 없었다는 의미이므로 그 사람을 리턴한다. 

또한 만약 입력에 동명이인이 존재하고 한명만 완주에 성공했을경우를 방지하기 위해 특정 이름이 검색될때마다 strkey[name]-- 연산을 실행시켜준다.

만약 strkey[name]이 0보다 작아진다면 completion에 있던 특정 이름의 사람 수보다 participation에 있던 사람 수가 많다는 것이므로 해당 이름을 출력한다.

보다 빠른 이해를 위해서는 아래 소스코드를 참고하자.

코드

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map <string, int> strkey;
    for(auto str : completion)
    {
        if(strkey.end() == strkey.find(str))
            strkey[str] = 1;
        else
            strkey[str]++;
    }
    
    for(auto str : participant)
    {
        if(strkey.end() == strkey.find(str))
            return str;
        else
        {
            strkey[str]--;
            if(strkey[str] < 0)
                return str;
        }
    }
}

평가

해시맵에 대해서 이해하고 이를 통해 문제를 풀이하는 방법을 익힐 수 있는 문제이다.

unordered_map이 기존 hash_map과 같은 역할을 수행한다는 것을 알아두자.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59040

문제

풀이

GROUP BY 문을 통해서 ANIMAL_TYPE으로 Tuple을 묶고, 이를 COUNT(*)을 통해서 세어주면 되는 문제이다.

이 때, 어차피 ANIMAL_TYPE에서 Cat이 Dog보다 사전순 오름차순에서 먼저 나오므로, 먼저 조회에 대해서는 신경쓸 필요가 없다.

코드

SELECT ANIMAL_TYPE, COUNT(*) FROM ANIMAL_INS GROUP BY ANIMAL_TYPE

평가

GROUP BY 문을 통해서 종류별로 개수를 세는 문제이다.

실제 DB 처리를 할 때 많이 사용되는 GROUP BY 이니 만큼 블로그 검색 등을 통해 확실히 이해하고 넘어가자.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59408

문제

풀이

본 문제에서는 NULL을 제외한 동물의 이름의 개수를 조회해야 한다.

이 때 중복을 제거하기 위해서 DISTINCT 구문을 사용하여 중복을 1개로 세게끔 할 수 있으며, NAME이 NULL이면 집계하지 않아야하므로 WHERE NAME IS NOT NULL; 조건을 넣어 풀이하여야 한다.

코드

SELECT COUNT(DISTINCT(NAME)) FROM ANIMAL_INS WHERE NAME IS NOT NULL;

평가

DISTINCT를 사용해 중복을 제거해주어야하고, WHERE에서 IS NOT NULL 조건을 통해 COUNT를 진행하는 문제이다.

DISTINCT와 IS NOT NULL에 대해 이해하고 넘어가면 좋을 것 같다.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59406

문제

풀이

COUNT 함수를 활용하면 Attribute에 대해서 그 숫자를 세어준다.

따라서 위 문제에서는 프라이머리 키값인 ANIMAL_ID에 대한 COUNT를 출력해주면 풀이가 가능하다.

코드

SELECT COUNT(ANIMAL_ID) as count FROM ANIMAL_INS

평가

COUNT를 통해 개수를 셀 수 있다는 것을 이해하고 넘어가자.

COUNT 구문은 문제에 자주 출제되니 반드시 외우는 것이 좋다.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59038

문제

풀이

MIN을 통해서는 최솟값을 구할 수 있다.

동물 보호소에 가장 먼저 들어온 동물은 DATATIME값이 가장 적은 동물이므로 MIN을 통해 풀이가 가능하다.

코드

SELECT MIN(DATETIME) FROM ANIMAL_INS;

평가

MAX와 반대되는 기능을 가진 MIN함수의 기능을 이해하고 넘어가도록 하자.

프로그래머스 - SQL 키트

https://programmers.co.kr/learn/courses/30/lessons/59415

문제

풀이

MAX(Attribute_NAME) 형식의 구문을 사용하면 최대값을 얻어올 수 있다.

가장 최근의 들어온 동물은 DATETIME값이 가장 큰 동물일 것이므로, MAX구문을 통해 풀이가 가능하다.

코드

SELECT MAX(DATETIME) as 시간 FROM ANIMAL_INS;

평가

MAX함수를 통해 최대값을 출력하는 방식을 짚고 넘어가면 되는 문제이다.