본문 바로가기

알고리즘

[프로그래머스] 2021 Dev-matching : 웹 백엔드 개발자 풀이

데브매칭 문제가 공개되었길래 풀어보았다

이 날 라인 코테였나...? 날짜가 겹쳐서 하나만 나가느라 데브매칭은 신청 못했는데

문제가 공개되다니!!

 

1. 로또의 최고 순위와 최저 순위

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <string>
#include <vector>
 
using namespace std;
 
int get_rank(int i){
    if(i>=6return 1;
    else if(i==5return 2;
    else if(i==4return 3;
    else if(i==3return 4;
    else if(i==2return 5;
    else return 6;
}
 
vector<int> solution(vector<int> lottos, vector<int> win_nums) {
    vector<int> answer;
    int cnt = 0;
    int zeros = 0;
    for(int i = 0 ; i < 6 ; i++){
        if(lottos[i]==0){
            zeros++;
            continue;
        }
        for(int j = 0 ; j < 6 ; j++){
            if(lottos[i]==win_nums[j]) cnt++;
        }
    }
    int max = cnt + zeros;
    answer.push_back(get_rank(max));
    answer.push_back(get_rank(cnt));
   
    return answer;
}
cs

 

등수를 구할 때 0인 부분과 숫자가 있는 부분을 따로 세어주었다

그리고 max는 0인 부분이 모두 당첨숫자인 경우로 체크하여 더해주고 등수를 구했다

 

2. 행렬 테두리 회전하기

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <string>
#include <vector>
 
using namespace std;
int map[105][105];
 
void print_map(int rows, int columns){
    for(int i = 1 ; i <= rows ;i++){
        for(int j = 1 ; j <= columns ; j++printf("%d ",map[i][j]);
        printf("\n");
    }
    printf("\n");
}
int rotate(vector<int> query){
    int left_upper_r = query[0];
    int left_upper_c = query[1];
    int right_lower_r = query[2];
    int right_lower_c = query[3];
    
    int buffer = map[left_upper_r][left_upper_c];
    int min = 10000;
    for(int i = left_upper_r ; i  <right_lower_r;i++){
        map[i][left_upper_c] = map[i+1][left_upper_c];
        if(min>map[i][left_upper_c]) min = map[i][left_upper_c];
    }
    for(int i = left_upper_c ; i < right_lower_c ; i++){
        map[right_lower_r][i] = map[right_lower_r][i+1];
        if(min>map[right_lower_r][i]) min = map[right_lower_r][i];
    }
    for(int i = right_lower_r ; i > left_upper_r ; i--){
        map[i][right_lower_c] = map[i-1][right_lower_c];
        if(min>map[i][right_lower_c]) min = map[i][right_lower_c];
    }
    for(int i = right_lower_c ; i > left_upper_c ; i--){
        map[left_upper_r][i] = map[left_upper_r][i-1];
        if(min>map[left_upper_r][i]) min = map[left_upper_r][i];
    }
    map[left_upper_r][left_upper_c+1= buffer;
    if(min>buffer) min = buffer;
    return min;
}
 
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    int c = 1;
    for(int i = 1 ; i <= rows ;i++){
        for(int j = 1 ; j <= columns ; j++) map[i][j] = c++;
    }
    int len = queries.size();
    for(int i = 0 ; i < len ; i++){
        answer.push_back(rotate(queries[i]));
        //print_map(rows,columns);
    }
    return answer;
}
cs

 

삼성 코테 준비하면서 지긋지긋하게 풀었던 배열 회전!

한칸씩 땡기는 걸로 구현했다

 

3. 다단계 칫솔 판매

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <string>
#include <vector>
#include <map>
#include <iostream>
 
using namespace std;
 
// idx num is minho
int parent[10005];
 
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    int num = enroll.size();
    map<string,int> match_name;
    for(int i = 0 ; i < num ; i++){
        parent[i] = i;
        answer.push_back(0);
        match_name[enroll[i]] = i;
    }
    parent[num] = num;
    
    for(int i = 0 ; i < num ; i++){
        if(referral[i]=="-") parent[i] = num;
        else{
            int parent_idx = match_name[referral[i]];
            parent[i] = parent_idx;
        }
    }
    int len = seller.size();
    for(int i = 0 ; i < len ; i++){
        int seller_idx = match_name[seller[i]];
        int money = amount[i]*100;
        int parent_idx = parent[seller_idx];
        while(1){
            answer[seller_idx] += money-(int)(money*0.1);
            money = (int)(money*0.1);
            if(parent_idx==num) break;
            if(money==0break;
            seller_idx = parent_idx;
            parent_idx = parent[seller_idx];
        }
    }
    return answer;
}
cs

 

1,2번은 알고리즘이라기 보다는 그냥 구현 문제였는데

3번에서는 알고리즘 개념이 조금 필요했던 것 같다

나는 기존에 익숙하게 쓰던 Union find 코드를 아무생각 없이 써서 

이름을 숫자로 바꾸고 그 숫자의 부모를 다시 찾는 방식으로 구현했다

공식 사이트의 해설처럼 map 하나만 가지고 구현하는 것이 더 효율적일 듯 하다

 

4. 헤비 유저가 소유한 장소

 

1
2
3
4
5
6
7
SELECT *
FROM PLACES
WHERE HOST_ID in (
    SELECT HOST_ID
    FROM PLACES
    GROUP BY HOST_ID
    HAVING COUNT(*>= 2)
cs

 

sql 문제 오랜만에 풀어봐서 처음에 순간 헷갈렸다

먼저 heavy user인 Host id를 다 뽑고 그 host id를 이용하여 전체 Place에서 다시 골라줬다

 

전체적인 후기!

블라인드나 알고리즘 오픈채팅에서 올솔이 많길래 전부터 쉬웠나보다 싶었는데 난이도가 어렵게 나온 것 같진 않다

이래서 서류가 중요하구나ㅠㅠ

sql도 오랜만에 풀어봤는데 해커랭크나 리트코드에서 풀었던 문제들보다는 쉬운 것 같다

'알고리즘' 카테고리의 다른 글

[C++] 리모컨  (0) 2021.06.29
[C] Z  (0) 2021.06.29
[C++] 프로그래머스 순위  (0) 2021.04.22
[C++] 프로그래머스 전화번호 목록  (0) 2021.04.07
[C++] 연산자 끼워넣기  (0) 2021.03.31