[프로그래머스/C#] 점프와 순간 이동

문제

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

프로그래머스

 

 

 

 

---

 

오류났던 코드

using System;

class Solution
{
    const int MAXVALUE = 1000000001;
    int[] weight = new int[MAXVALUE];
    bool[] visited = new bool[MAXVALUE];
    public int solution(int n)
    {
        for(int i=0;i<=n;i++){
            weight[i]=i;
        }
        visited[0]=true;
        this.Dijkstra(n);

        return weight[n];
    }
    
    public void Dijkstra(int n){
        while(true){
            int minWeightNode = this.GetMinWeightNode(n);
            if(minWeightNode==MAXVALUE||minWeightNode==n)
                break;
            visited[minWeightNode]=true;
            int teleportation = minWeightNode*2;
            if(teleportation<=n&&!visited[teleportation]){
                weight[teleportation]=Math.Min(weight[minWeightNode], weight[teleportation]);
            }
            for(int i=minWeightNode;i<=n;i++){
                if(!visited[i])
                    weight[i]=Math.Min(weight[i], weight[minWeightNode]+i-minWeightNode);
            }
        }
    }
    
    public int GetMinWeightNode(int n){
        int minWeight = MAXVALUE;
        int node = MAXVALUE;
        for(int i=0;i<=n;i++){
            if(weight[i]<minWeight&&!visited[i]){
                minWeight=weight[i];
                node = i;
            }
        }
        return node;
    }
}

 

다익스트라를 사용해서 풀었다.

정답처리는 잘만 되는데 효율성에서 자꾸 실패가 떴던 코드

처음에는 전역변수에 있던 배열들을 전부 지역변수로 선언하고 실행하였으나 시간 초과 이슈로 실패

시간 초과를 줄여볼까하고 나름 배열들을 전역변수로 옮겼으나 런타임 에러로 실패

 

아무래도 이 로직 자체가 효율성을 통과하기엔 무리인가 싶어 결국 힌트 사용...

 

---

 

코드

using System;

class Solution
{
    public int solution(int n)
    {
        int answer = 0;
        while(n>0){
            if(n%2==0)
                n/=2;
            else{
                n--;
                answer++;
            }
        }
        return answer;
    }
}

 

 

이렇게 간단하게 된다는 것이 열받는 코드...ㅂㄷㅂㄷ

n을 2진수로 표현했을 때 1의 개수가 곧 answer라고... 그러나 아직도 왜 그런지는 잘 모르겠는 1인.

 

---

다른 사람 풀이

using System;

class Solution
{
    public int solution(int n)
    {
        int result = 0;
        while(n > 1)
        {
            result += n % 2;   
            n = n / 2;
        }
        return result + 1;

    }
}

 

더 간략할 수가 있었다..

answer값의 변동 유무를 n%2에 맡기고 계속 n/2를 하는 방식

0에서부터 출발하니 어쨌든 1로는 무조건 가야 되니까 while의 조건문을 n>1로 두되 마지막 return에 +1 추가

(이런 코드 보면 반성하게 된다,,,)

 

 

더 열심히 살자!😊