[프로그래머스] Level 1에서 볼 만한 문제

이 글에서는 프로그래머스의 Level 1 문제 중 꼭 한 번은 다루고 넘어갔으면 좋겠는 문제들에 대해 살펴보도록 하겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

일단 시작하기 전, 프로그래머스 Level 1 문제에는 [2019 카카오 개발자 겨울 인턴십 : 크레인 인형뽑기 게임] [2018 카카오 블라인드 채용 1차 : 비밀지도, 다트게임] [2019 카카오 블라인드 채용 1차 : 실패율] [2018 summer/winter coding : 예산]이 포함되어 있습니다. 이 문제들은 선택적으로 풀어보는 것이 아닌 반드시 풀어보아야 할 문제일테니 따로 다루지 않고 넘어가도록 하겠습니다. (다루고 싶어도 문제 및 풀이를 밖으로 꺼내어 쓸 수가 없어서 사실 쓰고 싶어도 못써요ㅠ)

완주하지 못한 선수

이 문제의 경우 제가 프로그래머스에서 제일 처음 풀어보았던 문제입니다. 그래서 이미 풀이도 전 포스팅에서 작성해 놓았습니다. 해시로 분류를 해 놓은 문제이니 제가 1) 직관적으로 sorting해서 풀기 2) map, unordered_map써서 풀기 3)  hash table과 collision handling 방식을 separate chaining으로 풀기 해놓았으니 확인해보세요~! (완주하지 못한 선수 풀이)

소수찾기

제가 기억하기로는 프로그래머스에는 소수 찾기가 2문제가 있습니다. 하나는 제가 이전에 풀었던 이 문제이고, .다른 하나는 지금 소개 해드리는 문제인데 이 문제가 찐입니다. 효율성을 따지니까요. 그래서 c++로 코드를 짜시는 분들은 반드시 에라토스테네스의 체를 사용하셔서 문제를 푸셔야 합니다.

에라토스테네스의 체를 이용하여 문제를 풀 때 2가지를 명심하시면 됩니다.

1. 소수가 아닌 것을 먼저 찾고 걸러 내는 원리를 활용하는 것

2. num 이하의 숫자들 중 소수를 찾는다고 하면 sqrt(num)까지만 검사를 하면 됨

 

코드 자체는 어렵지 않습니다. 아래 더보기를 펼치시면 복사해서 보실 수 있습니다.

#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    
    int answer = 0;
    
    // arr : 'true' if prime num, 'false' if not
    bool *arr = new bool[n+1];
    for(int i = 2; i < n+1; i++){
        arr[i] = true;
    }

    // 에라토스테네스의 체
    for(int i = 2; i * i <= n; i++){
        if(arr[i]){
            for(int j = i * i; j <= n; j += i)
                arr[j] = false;
        }
    }
    
    // find numbers that are true and add
    for(int i = 2; i < n+1; i++)
        if(arr[i])
            answer++;
    
    return answer;
}

시저 암호

따로 찾아보지 않아 잘은 모르겠지만 분명 다양한 풀이가 있을 것 같습니다. 제가 '시저 암호' 문제를 한 번쯤 살펴봤으면 좋겠다고 한 이유는 아스키코드 때문입니다. 아스키 코드에서 알아두면 분명 편리한 범위가 있습니다. 한국에서는 이걸 알고 있는게 당연했는데 NTU에서 공부할 당시 수업시간에 대답하니까 교수님께서 이걸 왜 외우고 있냐고 여쭤보시더라구요.... 그냥...알고 있는건데 밍

1. 소문자 a~z = 97 ~ 122

2. 대문자 A~Z = 65 ~ 90

3. 숫자 0 = 48

 

사실 이 문제 하나로는 아스키코드로 문자, 숫자 가지고 놀기에는 충분하지 않습니다. 시저 암호는 비교적 간단히 풀이 되는데 아래와 같이 풀 수 있으니 코드를 보고 싶으신 분들은 더보기를 눌러주세요. 

#include <string>
#include <vector>

using namespace std;

string solution(string s, int n) {
    string answer = "";
    
    for(int i = 0; i < s.length(); i++){
        if(isalpha(s[i])){
            if(97 <= s[i] && s[i] <= 122){
                // lower letter
                if(s[i] + n > 122){
                    answer += s[i] + n - 26;
                } else{
                    answer += s[i] + n;
                }
            } else {
                // upper letter
                if(s[i] + n > 90){
                    answer += s[i] + n - 26;
                } else{
                    answer += s[i] + n;
                }
            }
        } else{
            answer += " ";
        }
    }  
  
    return answer;
}

 

한 단계 더 나아가서 놀고 싶으신 분들은 하샤드의 수라는 문제를 풀어보시면 좋을 것 같습니다. 하샤드의 수에서는 숫자와 문자를 왔다갔다 하며 문제를 풀기 때문이죠. 하샤드의 수 풀이도 아래 더보기에 놓도록 하겠습니다.

#include <string>
#include <vector>

using namespace std;

bool solution(int x) {
    bool answer = true;
    string tostring = to_string(x);
    
    int sum = 0;;
    for(int i = 0; i < tostring.size(); i++){
        sum += (tostring[i] - '0');
    }
    
    if (x % sum != 0)
        answer = false;
    return answer;
}

 

문자열 내 마음대로 정렬하기

정렬을 내가 설정한 기준에 맞춰 할 수 있는 방법을 터득할 수 있으므로 이 문제는 한 번쯤 꼭 풀어보고 가셨으면 좋겠습니다. c++을 쓰는 가장 큰 이유 중 하나는 STL 때문일 것입니다. 그래서 정렬을 해야하는 상황이 오시면 당연히 #include <algorithm> 추가하고 sort(v.begin(), v.end());를 쓰셨겠죠? 그러나 만약 문자의 2번째 글자를 기준으로 정렬을 하라고 한다면?!ㅎㅎ

 

일단 sort 함수의 형태를 보고 가시는게 좋을 것 같습니다. 

default로는 void sort (RandomAccessIterator first, RandomAccessIterator last); 이렇게 생겼습니다. 시작지점과 끝지점을 지정하고 정렬을 하게 되어있죠. 그런데 custom으로 지정을 할 수 있는데

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); 이렇게 생겼습니다. 바로 이 Compare comp 부분에 우리가 쓰고 싶은 조건이 달립니다.

comp는 2개의 매개변수를 받아들이는 함수로써 bool로 치환이 되는 값을 반환합니다. 반환되는 값은 첫 번째 매개변수가 두번째 매개변수보다 앞에 오는지를 알려주는 것입니다. 그래서 문자열의 2번째 문자로 정렬을 하고 싶은 경우 아래와 같이 comp를 만들 수 있습니다.

bool strangeOrder(string a, string b){ 
    if(a[index] != b[index]){
        return a[index] < b[index];
    } else{
        return a < b;
    }
}

전체 코드를 보고 싶으신 분들은 아래 더보기를 눌러주시기 바랍니다.

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

using namespace std;

int index;

bool strangeOrder(string a, string b){ 
    if(a[index] != b[index]){
        return a[index] < b[index];
    } else{
        return a < b;
    }
}

vector<string> solution(vector<string> strings, int n) {
    vector<string> answer;
    index = n;
    
    sort(strings.begin(), strings.end(), strangeOrder);
    
    return strings;
}

 

뭐 level 1 다 풀고 다른 레벨에 있는 몇 문제 푸니 지금 6062등이네요? 더 땡기러 가겠습니다 쓩ㅋㅋ