[프로그래머스] 예상대진표

문제

 

풀이 1

#include <vector>
using namespace std;


int solution(int n, int a, int b)
{
    int answer = 0;
    vector<int> v;
    v.assign(n, 0);
    v[a-1] = a;
    v[b-1] = b;
    bool roof = true;
    while(roof){
        answer ++;
        for(int i=0; i<v.size(); i++){
            v[i] = v[i] + v[i+1];
            v.erase(v.begin() + i + 1);
            if( v[i]  == (a + b)){
                roof = false;
                break;
            }
        }
    }
    
    return answer;
}

 

계속해서 실행시간 오류가 났던 풀이이다.

아무래도 많은 값의 데이터를 이중 반복문으로 탐색하려니 시간이 많이 걸린 모양이었다.

 

 

풀이 2 (다른 사람 풀이)

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    while(a!=b){
        answer ++;
        if(a%2==1) a++;
        if(b%2==1) b++;
        a/=2;
        b/=2;
    }
    
    return answer;
}

결국 다른 사람의 풀이를 참고하였고 수학적 해결법으로 문제를 풀었다.

 

어느 문제든 효율적으로 코드를 구현하는것이 힘든 것 같다.

최단 실행시간을 구하기 위해 알고리즘을 짜는 방법을 문제를 풀어가며 학습해가야겠다.

 

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges