[programmers] 258712번 - 가장 많이 받은 선물(DP, 2024 KAKAO WINTER INTERNSHIP)

1. 문제 및 예제

 

DP 열심히 풀던 와중에 이런 문제가 나오다니.. 행복했다. 회사에서는 JS를 쓰기 때문에 다시 C++을 사용해보니 메소드도 기억 안나서 그냥 내가 몇개 만들었다. 그래도 첫 제출에 맞춰서 나름 뿌듯했다. 1분 뒤에 레벨1 원트에 맞았다고 뿌듯해하는 내 자신을 보면서 자괴감도 조금 들었다...

---

https://school.programmers.co.kr/learn/courses/30/lessons/258712

프로그래머스

---

2. 본론

 

선물을 주고받은 기록을 따로 배열에 저장하면 해결되는 간단한 DP문제이다. 선물을 주고 받는 부분만 계산하면 답은 쉽게 구해지기 때문에 시간복잡도는 O(N)이 된다.

 

브루트포스로도 풀 수 있을까? 싶었다. 사실 입력 최대값이 크지는 않았기 때문에 가능할 수 있겠지만 많이 복잡할 것 같았다. 결국에는 결과를 저장해야했기 때문에 DP를 선택하였다.

 

문제를 나누는 과정은 다음과 같다.

---

1. 선물을 주고받은 횟수를 저장한다.

2. 전 단계를 바탕으로 답을 구한다.

---

배열은 이차원 배열로 다음과 같이 활용하였다.

---

준 사람: i

받은 사람: j

 

gift_board[i][j]++

---

위의 방식대로 처리하면 i가 j에게 선물을 몇번 줬는지 알 수 있다. 다음은 전체 코드이다.

 

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

using namespace std;

int get_index(vector<string> arr, string name){
    for(int i = 0; i < arr.size(); i++){
        if(arr[i] == name)
            return i;
    }
}

pair<string, string> get_from_to(string str){
    string to = "";
    string from = "";
    bool flag = false;
    
    for(auto it : str){
        if(it == ' '){
            flag = true;
        }else {
            if(flag){
                to += it;
            }else{
                from += it;
            }
        }
    }
    return make_pair(from, to);
}

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    
    //선물 지수
    int gift_rate[55] = {0};
    int gift_board[55][55] = {0};
    
    for(auto it : gifts){
        pair<string, string> tmp = get_from_to(it);
        int from_index = get_index(friends, tmp.first);
        int to_index = get_index(friends, tmp.second);
        
        gift_board[from_index][to_index]++;
        
        gift_rate[from_index]++;
        gift_rate[to_index]--;
    }
    
    for(int i = 0; i < friends.size(); i++){
        int tmp = 0;
        for(int j = 0; j < friends.size(); j++){
        
            if(i == j)
                continue;
            
            if(gift_board[i][j] > gift_board[j][i]){
                tmp++;
            }else if(gift_board[i][j] == gift_board[j][i]){
                if(gift_rate[i] > gift_rate[j]){
                    tmp++;
                }
            }   
        }
        answer = max(answer, tmp);
    }
    
    return answer;
}

 

3. 결어

 

다음에는 레벨3 문제도 풀어 올려볼 계획이다.