본 포스팅에서 언급하는 문제는 모두 프로그래머스에서 확인하실 수 있습니다.
이하의 코드는 모두 C++로 작성되어 있음을 미리 알려드립니다.
제가 생각한 방법 외에 다른 방법으로 푸신 분들이 계시다면 덧글로 공유해 주시면 감사하겠습니다 👋🏻
문제 1: 가장 많이 받은 선물
1번 문제는 단순 구현 문제였던 것 같아요.
문제에서 입력 값을 모두 문자열로 주기 때문에, split 함수를 사용하거나 기타 여러 방법으로 문자열 전처리 과정이 필요합니다.
어? 근데 C++에는 split 함수가 없는데요??
그래서 저는 split 함수를 따로 구현해서 사용하고 있어요 !
#include <string>
#include <vector>
#include <sstream>
using namespace std;
vector<string> split(string input, char delimiter)
{
vector<string> answer;
stringstream ss(input);
string temp;
while (getline(ss, temp, delimiter))
{
answer.push_back(temp);
}
return answer;
}아무튼 이런 방법으로 문자열을 자르면, 결국 친구들 사이에는 선물을 주고 받은 횟수에 대하여 방향 그래프 관계가 생기게 됩니다.
예를 들어 문제의 첫 번째 입출력 예의 경우
firends: ["muzi", "ryan", "frodo", "neo"]
gifts: ["muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"]
위와 같은 방향 그래프를 얻을 수 있습니다.
여기서 간선의 방향은 선물을 준 방향과 동일하고, 간선의 가중치는 선물을 준 횟수입니다.
따라서 이 그래프를 보고 frodo가 muzi에게 선물을 한 번 줌을 알 수 있습니다.
이렇게 방향 그래프를 만든 후에는 선물을 주고 받은 적 있는 친구들끼리는 선물을 더 많이 준 친구가 선물을 받도록 하고,
선물을 주고 받은 적 없는 친구나 선물을 똑같이 주고 받은 친구들끼리는 선물 지수가 더 높은 친구가 선물을 받도록 하면 됩니다.
문제 2: 도넛과 막대 그래프
2번 문제는 입력으로 주어진 그래프에서 도넛 모양 그래프, 막대 모양 그래프 그리고 8자 모양 그래프의 개수를 알아내는 문제이기 때문에, 먼저 각 그래프의 특징을 찾아야 합니다.
도넛 모양 그래프 특징
- 노드의 개수가 N개인 경우, 간선의 개수도 N개이다.
막대 모양 그래프 특징
- indegree가 0인 노드는 단 1개만 존재한다.
- 노드의 개수가 N개인 경우, 간선의 개수는 항상 N-1개이다.
8자 모양 그래프 특징
- 노드의 개수가 N개인 경우, 간선의 개수는 항상 N+1개이다.
위의 그래프들과 무관한 정점부터 찾자
위와 같은 특징들을 알아낸 후에는 먼저 위의 그래프들과 무관한 정점부터 찾아야 합니다.
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다.
이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.
문제에 따르면, 그래프들과 무관한 정점은 indegree가 0이고 outdegree는 1 이상인 정점임을 알 수 있으므로, 간단하게 찾을 수 있습니다.
무관한 정점을 찾은 후에는 무관한 정점과 연결되어 있는 간선을 모두 제거해줘야 하는데, 이는 막대 모양 그래프의 첫 번째 특징을 이용하기 위함입니다.
문제의 두 번째 입출력 예시를 예로 들면,
위와 같은 그래프에서 무관한 노드는 indegree가 0인 4번 노드가 되고, 여기서 4번 노드를 제거하면
이렇게 모든 그래프들이 독립적으로 존재하게 됩니다.
여기서 막대 모양 그래프의 첫 번째 특징 indegree가 0인 노드는 단 1개만 존재한다를 활용해서 2번 노드가 막대 모양 그래프의 시작 노드임을 알 수 있죠.
만약에 막대 그래프가 2개 이상 존재한다면, indegree가 0인 노드를 모두 찾아서 막대 그래프의 개수를 카운트해 주시면 됩니다.
이렇게 막대 그래프를 모두 찾은 후에는 아직 방문하지 않은 노드들에 대하여, 그래프 탐색을 수행하면 됩니다.
그래프 탐색을 수행할 때, 현재 탐색중인 그래프에 포함된 노드의 개수와 간선의 개수만 카운트해 주시면 도넛 모양 그래프와 8자 모양 그래프를 구분하실 수 있습니다.
문제 3: 주사위 고르기
3번 문제는 완전 탐색 문제입니다.
주사위를 절반씩 나누어 가진 후, 나누어 가진 주사위에서 나올 수 있는 숫자의 합을 모두 구해야 합니다.
그렇기 때문에 문제를 1. 주사위를 절반씩 나누어 가지는 문제와 2. 나누어 가진 주사위로 나올 수 있는 숫자의 합을 구하는 문제로 나눌 수 있습니다.
1. 주사위를 절반씩 나누어 가지는 문제
주사위를 절반씩 나누어 가지는 문제는 combination이나 완전 탐색으로 직접 구현하면 간단하게 해결할 수 있습니다.
2. 나누어 가진 주사위로 나올 수 있는 숫자의 합을 구하는 문제
이 문제는 A와 B 각각 나누어 가진 주사위로 나올 수 있는 숫자의 합을 모두 저장해 놓으면 해결할 수 있습니다.
물론 주사위로 나올 수 있는 숫자의 합을 구할 때에는 조합을 사용합니다.
A와 B가 가진 주사위로 나올 수 있는 숫자의 합을 저장한 배열을 각각 dice_a dice_b라고 하면,
dice_a와 dice_b에 저장되어 있는 값들로 A가 승리한 횟수를 셀 수 있고,
이를 바탕으로 A가 승리한 횟수가 가장 많은 경우가 정답이 됨을 알 수 있습니다.
문제 4: n + 1 카드게임
4번 문제는 1부터 n까지의 카드가 한 장씩 있다는 사실을 잘 이용해야 합니다.
예를 들어 n이 6인 경우, 1과 6 2와 5 3과 4를 더하면 모두 7이 됨을 알 수 있습니다.
또한 앞선 라운드에서 카드 1을 먹고 나중에 카드 6을 먹는 것은
나중에 카드 1과 6을 동시에 먹는 것과 동일한 결과를 만든다는 것을 활용하면 문제는 바로 해결됩니다.
문제의 첫 번째 입출력 예를 예시로 들어서 설명하겠습니다.
coin: 4
cards: [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]처음에 카드 뭉치에서 카드를 4장 가져가므로, 아래와 같이 됨을 알 수 있습니다.
내 카드: [3, 6, 7, 2]
남은 코인: 4개
cards: [1, 10, 5, 9, 8, 12, 11, 4]여기서 각 라운드 별로 뽑게 될 카드는 모두 아래처럼 되는데
1라운드: [1, 10]
2라운드: [5, 9]
3라운드: [8, 12]
4라운드: [11, 4]앞선 라운드에 위치한 숫자를 더했을 때, 13(n+1)이 되도록 뒷 라운드로 보내면 아래처럼 됩니다.
1라운드: [-, 10]
2라운드: [-, -]
3라운드: [8+5, 12+1]
4라운드: [11, 4+9]여기서 손에 들고 있는 카드들 중, 두 카드의 합이 13이 되는 카드를 많이 가지고 있을 수록 더 많은 라운드를 진행할 수 있음을 알 수 있습니다.
따라서 각 라운드에 위치한 카드를 구매할 수 있는 경우에는 무조건 구매하고, 라운드 별로 두 카드의 합이 13이 되는 카드 2장을 제거하면 최대 라운드까지 진행할 수 있게 됩니다.
따라서 각 라운드는 아래와 같이 진행됩니다.
1라운드: 코인 1개를 사용해서 카드 10을 가져옴.
내 카드: [3, 6, 7, 2, 10]
남은 코인: 3개
카드 6과 7을 사용해서 다음 라운드 진행.2라운드: 아무런 카드도 가져오지 않음
내 카드: [3, 2, 10]
남은 코인: 3개
카드 3과 10을 사용해서 다음 라운드 진행.3라운드: 코인 2개를 사용해서 카드 8과 5를 가져옴.
내 카드: [2, 5, 8]
남은 코인: 1개
카드 5와 8을 사용해서 다음 라운드 진행.4라운드: 코인 1개를 사용해서 카드 11을 가져옴.
내 카드: [2, 11]
남은 코인: 0개
카드 2와 11을 사용해서 다음 라운드 진행.5라운드: 코인이 없기 때문에 카드를 가져올 수 없음
내 카드: []
남은 코인: 0개
더 이상 낼 수 있는 카드가 없기 때문에 게임 종료.따라서 정답은 5가 됩니다 !
문제 5: 산 모양 타일링
5번 문제는 제가 아직 못풀었기 때문에.. 카카오 공식 풀이로 대체하겠습니다 🫣
