[C++/PGS] [PCCP 모의고사 #1] 3번 - 유전법칙 🤯

 

https://school.programmers.co.kr/learn/courses/15008/lessons/121685

프로그래머스

---

프로그래머스 PCCP 모의고사 1회 - 3번

소요시간 1시간 이상 (힌트 참고함)

stack 활용한 수학 연산, dfs/bfs로도 가능한 듯, 추정 난이도는 level 2-3

 

4로 나눈 나머지를 스택에 넣어주고,

가장 상위 부모부터 꺼내어 그 자식을 찾는다. (top -> down)

그리고, "RR"이나 "rr"일 경우에는 자식이 항상 부모와 동일하므로 break해준다

 

나머지를 연산해야 하고, 반복적으로 나오는 패턴을 고민해야 하는 부분에서 꽤 어려웠다 ㅠㅠ

 

 

나의 풀이

#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

vector<string> solution(vector<vector<int>> queries) {
    vector<string> answer;
    
    for (auto q : queries) {
        string parent = "Rr";
        int n = q[0];
        int m = q[1] - 1; // 0부터 연산

        stack<int> s; // 나머지 저장
        for (int i = 0; i < n - 1; ++i) {
            s.push(m%4);
            m /= 4;
        }

        while (!s.empty()) {
            int now = s.top(); // parent를 갱신하며(가장 상위 부모부터) 반복문 진행
            s.pop();

            if (parent == "Rr") {
                if (now == 0) parent = "RR";
                else if (now == 1 || now == 2) parent = "Rr";
                else if (now == 3) parent = "rr";
            } else { // "rr"이나 "RR"이면 더 이상 바뀌지 않음
                break;
            }
        }

        answer.push_back(parent);
    }
    return answer;
}

 

2회차 모의고사에 이어서 1회차도 완료!