Programmers: 더 맵게(C++)

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) priority_queue를 이용하여 문제를 해결하고자 한다면 쉽게 풀 수 있는 문제이다.

2) 조건을 상세하게 살피는 것이 매우 중요하다

(정확성 테스트 16 만 막히는 분들은 맨 밑에 도움이 될 말을 적어두었다.)

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=0; i<scoville.size();i++)
    {
        q.push(scoville[i]);
    }
    while(1)
    {
        if(q.size()==1)
        {
            if (q.top() >= K)
            {
                answer++;
            }
            else if (q.top() < K)
            {
                answer = -1;
            }
            break;
        }
        else
        {
            if(q.top()<K)
            {
                int a=q.top();
                q.pop();
                int b=q.top()*2;
                q.pop();
                q.push(a+b);
                answer++;
            }
            if(q.top()>=K)
            {
                break;
            }
        }
    }
    return answer;
}

더 클린하게 최종 코드를 첨부할 수 있었지만 위와 같은 코드의 형태로 첨부한 이유는 정확성 테스트 16에서 막히는 분들을 위함이다. 

if(q.top()<K)
{
    int a=q.top();
    q.pop();
    int b=q.top()*2;
    q.pop();
    q.push(a+b);
    answer++;
}
if(q.top()>=K)
{
	break;
}

q의 사이즈가 2 이상일 경우 해당 코드에서 두번째 if문인 q.top()>=K를 잘 못 적게 되는 경우 오류가 발생한다.

 

// 틀린 코드
if(q.top()<K)
{
    int a=q.top();
    q.pop();
    int b=q.top()*2;
    q.pop();
    q.push(a+b);
    answer++;
}
else if(q.top()>=K)
{
	break;
}

연속적인 if문이 아닌 else if문을 넣는 경우 문제가 발생할 수 있다.

배열의 값이 [1,2,3]에 K가 13일 경우, 정상적으로 나와야 하는 값은 2이다.

if(q.size()==1)
{
    if (q.top() >= K)
    {
    	answer++;
    }
    else if (q.top() < K)
    {
    	answer = -1;
    }
    break;
}

허나 필자 처럼 size가 1일 경우 탈출 조건을 위의 코드와 같이 작성했다면 3의 값이 나온다.

종료 조건을 깔끔하게 처리하거나, else if문을 활용한다면 정확성 테스트 16을 해결할 수 있을 것이다.