[프로그래머스/C++] 홀짝트리

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 크게 어렵지 않지만, 구현이 생각보다 빡센 문제였다.

 

주어진 수식들 중에 수식의 결과를 알고 있다면, 그 수식을 이용해 N진법이 가능한지 판단하고, 만약 결과를 모른다면 후보군에 두면 된다.

 

N진법이 가능한지 판단하는 방법은 간단하다.

 

먼저 2~9진법의 수로만 수식이 이루어지므로, A + B = C라는 수식에서 A, B, C를 각각 N진법의 수가 가능한지 판단한다.

만약 A, B, C 수가 전부 N진법이 가능하다면, A + B라는 값이 C라는 식과 일치하는지 판단한다.

 

이렇게 비교해서 만약 A+B=C라면 이 수식에서 N진법이 가능하다는 뜻이다.

만약 A+B값이 C와 다르다면 N진법은 현재 수식은 N진법이 아니라는 뜻이다.

 

이렇게 조건을 비교해 수식들로부터 2~9진법중 가능한 N진법 목록을 뽑는다.

 

이후 이 N진법 목록을 이용해 수식의 값을 모르는 식의 값을 구해보면된다.

 

예를 들어 가능한 N진법 List가 [3, 4, 5]라면, A+B 를 3진법으로 계산한 결과를 4진법으로 계산한결과, 5진법으로 계산한 결과와 비교한다.

 

이렇게 모든 진법으로 계산한 결과를 비교한 뒤, 모든 진법으로 계산했을 때, 같은 값 X가 나오면 X를 그 수로 표현하고 만약 하나라도 다른 값이 나오면 ?를 출력하면 된다.

 

이때 진법을 변환할 때, 헷갈리지 않게 주의해야 한다.

 

나는 계산을 편하게 하기 위해 A + B = C라는 수식이 있으면,  A, B, C를 2~9진법 수라고 가정하고 10진법의 값으로 변경했다.

 

이후 N진법 수 A, B, C를 10진법으로 변환한 뒤에 계산해 결과 값 A+B = C라면 N진법 이 가능하다고 판단했다.

 

반대로 X값을 구하는 과정은 좀 더 복잡하다.

 

A + B = X에서 A, B를 10진법으로 바꾼 뒤 A+B를 계산한다. 이후 A+B를 다시 N_0진법으로 변환한 수를 저장한다.

 

이후 가능한 N진법 List { N_0, N_1, N_2 ... } 에서  A+B를 다시 10진법으로 바꾼 뒤 A+B를 계산하고 A+B를 N_1진법으로 변환해 이전에 N_0진법으로 변환한 수와 비교했다.

 

이후 비교한 결과 값들이 전부 같은 수라면 X값을 그 수로 변환했다. 

 

 

​

[아이디어 정리]

1. 결과 값이 X가 아닌 식들을 이용해 가능한 N진법 List를 만든다.
2. 결과 값이 X였던 식들을 전부 N진법 List에 대해 숫자를 변환해 결과 값이 모두 같은 수로 표현되는지, 다른 값이 있어 ?로 표현되는지 판단한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(vector<int> nodes, vector<vector<int>> edges) {
    vector<int> answer(2,0);
    vector<bool> visited(1000001,false);
    vector<vector<int>> graph(1000001);
    
    for (int i=0; i<edges.size(); i++)
    {
        graph[edges[i][0]].push_back(edges[i][1]);
        graph[edges[i][1]].push_back(edges[i][0]);
    }
    
    for (int i=0; i<nodes.size(); i++)
    {
        if (!visited[nodes[i]]){
            int nn=nodes[i],a;
            vector<int> v(2,0); // 간선%2==노드%2(N), else(M)
            queue<int> q;
            q.push(nn);
            while(!q.empty()){
                nn=q.front();
                q.pop();
                visited[nn]=true;
                for (int j=0; j<graph[nn].size(); j++)
                {
                    if (!visited[graph[nn][j]])
                        q.push(graph[nn][j]);
                }
                if (nn%2==graph[nn].size()%2)
                    v[0]+=1;
                else
                    v[1]+=1;
            }
            
            if (v[0]==1){
                answer[0]+=1;
            }
            if (v[1]==1){
                answer[1]+=1;
            }
        }
        
    }
    
    return answer;
}

---

 

처음에 프로그래머스 코드챌린지에서 봤을 때, 자식 노드를 모든 하위 노드의 수로 잘못 봐서 어떻게 풀어야할지 몰랐다;;

다시 문제를 제대로 읽어보니 자식 노드 = 바로 밑에 연결된 노드임을 눈치챘다...

 

문제를 잘 읽는 습관을 다시 들이자..ㅠㅠㅠㅠ

 

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