1. 예상 대진표
1) 문제
문제 설명
△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.
제한 사항
- N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
- A, B : N 이하인 자연수 (단, A ≠ B 입니다.)
입출력 예
N A B answer
8 4 7 3
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
using namespace std; int solution(int n, int a, int b) { int answer = 0; while(a != b) { a = (a+1) / 2; b = (b+1) / 2; answer++; } return answer; }
1. 다단계 칫솔 판매
1) 문제
문제 설명
제한 사항
- enroll의 길이는 1 이상 10,000 이하입니다.
- enroll에 민호의 이름은 없습니다. 따라서 enroll의 길이는 민호를 제외한 조직 구성원의 총 수입니다.
- referral의 길이는 enroll의 길이와 같습니다.
- referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
- 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
- enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.- seller의 길이는 1 이상 100,000 이하입니다.
- seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
- seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
- amount의 길이는 seller의 길이와 같습니다.
- amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
- 판매량의 범위, 즉 amount 의 원소들의 범위는 1 이상 100 이하인 자연수입니다.
칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
모든 조직 구성원들의 이름은 10 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.입출력 예
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <iostream> #include <vector> #include <unordered_map> using namespace std; unordered_map<string, string> refMap; unordered_map<string, int> profitMap; void setProfit(string member, int amount) { int total = amount * 100; int distribution; do { if (total <= 9) { profitMap[member]+=total; break; } else { distribution = total / 10; profitMap[member]+= total - distribution; member = refMap[member]; total = distribution; } }while(member != "Center"); } vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) { vector<int> ans; // refMap 채우기 for (int i=0; i<enroll.size(); ++i) { string ref; if (referral[i] == "-") ref="Center"; else ref = referral[i]; refMap[enroll[i]]= ref; } // 판매금액을 통한 이익금 처리 for (int i = 0; i < amount.size(); i++) { setProfit(seller[i], amount[i]); } for (auto& e : enroll) { ans.push_back(profitMap[e]); } return ans; }
1. 길 찾기 게임
1) 문제
문제 설명
라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
모든 노드는 서로 다른 x값을 가진다.
같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
자식 노드의 y 값은 항상 부모 노드보다 작다.
임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,
노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.제한 사항
- nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
- nodeinfo의 길이는 1 이상 10,000 이하이다.
- nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
- 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
- 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
- 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.
입출력 예
nodeinfo
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]
result
[[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <algorithm> #include <iostream> #include <unordered_map> using namespace std; struct Node { Node(int x, int num) : _x(x), _num(num) , _left(nullptr), _right(nullptr){} int _x; int _num; Node* _left; Node* _right; }; class BST { public: BST() : _root(nullptr) {}; void insert(int x, int num); void PreOrder(vector<int>& vec); void PostOrder(vector<int>& vec); private: Node* insertPrivate(Node* node, int x, int num); void PreOrder(Node* node, vector<int>& vec); void PostOrder(Node* node, vector<int>& vec); Node* _root; }; void BST::insert(int x, int num) { if (_root == nullptr) _root = new Node(x,num); else { _root = insertPrivate(_root, x, num); } } Node* BST::insertPrivate(Node* node, int x, int num) { if (node == nullptr) { Node* newNode = new Node(x,num); return newNode; } if (node->_x < x) { node->_right = insertPrivate(node->_right, x, num); } else if (node->_x > x) { node->_left = insertPrivate(node->_left, x, num); } return node; } void BST::PreOrder(vector<int>& vec) { PreOrder(_root, vec); } void BST::PostOrder(vector<int>& vec) { PostOrder(_root, vec); } void BST::PreOrder(Node* node, vector<int>& vec) { if (node == nullptr) return; vec.push_back(node->_num); PreOrder(node->_left, vec); PreOrder(node->_right, vec); } void BST::PostOrder(Node* node, vector<int>& vec) { if (node == nullptr) return; PostOrder(node->_left, vec); PostOrder(node->_right, vec); vec.push_back(node->_num); } bool cmp (vector<int> vec1, vector<int> vec2) { return vec1[1] > vec2[1]; } vector<vector<int>> solution(vector<vector<int>> nodeinfo) { vector<vector<int>> answer(2,vector<int>()); unordered_map<int, int> xtonum; for (int i=0; i<nodeinfo.size(); i++) { xtonum[nodeinfo[i][0]] = i+1; } // y가 큰 장소가 먼저 삽입되어야 // x만 가지고 BST만들 수 있음. sort(nodeinfo.begin(), nodeinfo.end(), cmp); BST bst; for (int i=0; i<nodeinfo.size(); i++) { bst.insert(nodeinfo[i][0], xtonum[nodeinfo[i][0]]); } bst.PreOrder(answer[0]); bst.PostOrder(answer[1]); return answer; }
