c++ 그리디 알고리즘 질문있어요

백준 문제중에 10610번

어떤숫자를 줬을때 30의배수가아니라면 -1을 반환하고
30의배수라면 그숫자들을 섞어서 가장큰수를 출력하는 문제가있습니다.

30의 배수를 구하는방법을 생각해본결과, 0이있어야하고 모든숫자들의 합이 3의 배수이면됬습니다.
코드 짜는순서는
1.char 배열에 숫자를입력해서 숫자를 분리시켰습니다.

2.배열에 0이있을때까지 검색하다가 0이나오면 break
끝까지가도 0이없다 그러면 -1을 출력

3.위의 생각을 토대로 각분리된숫자를 모두더해 3의배수이면 sort함수를써서 가장큰수를 cout
3의배수가아니라면 -1을 출력

이렇게 짰는데 …
2번에서 짜다가 잘안되서 질문드립니다.

bool compare(int a,int b)
{
    return a>b;
}

int main()
{
    int sum;
    char num[100000];
    cin >> num;
    int size=strlen(num);
    
    //여기부터 잘안됨.. 
    for(int i=0; i<size; i++)
    {
        if(num[i]==0)
            break;
        else if(i==size-1)
        {
            cout << "-1";
            return 5;
        }
    }
    // 배열에 0이있을때까지 검색하다가 0이나오면 break  끝까지가도 0이없다 그러면 -1을 출력
   // 0이발견되면 break에서 for문을탈출하는거아닌가요??? 순서가 break->else if->반복문탈출인가요??

    sort(num,num+size,compare);  // 큰숫자대로 분류
    for(int i=0; i<size-1; i++)
    sum+=num[i];
    
    if(sum%3==0)
    {
        for(int i=0; i<size; i++)
        cout << num[i];
    }
    else
        cout <<"-1";
}
1 Like

이런 글 올릴 때는 백준 링크도 같이 다는 것이 좋습니다. 이번에는 제가 임의로 추가했습니다. 다음부터는 꼭 달아주세요.


간단한 코드 리뷰 드리겠습니다.

  1. using namespace std 사용을 지양하세요.

  2. std::string을 사용하세요.

  3. 지역변수 배열을 함부로 크게 잡지 마세요.

  4. sort의 인자로 함수 포인터 보내지 마세요. 함수자나 람다, 혹은 functional 헤더의 객체를 보내세요.

  5. 질문 주신 부분은 i == size - 1인지 체크하는 것보다 goto문을 사용해 예외를 밖으로 빼는 것이 좋아보입니다(개인적인 의견). 제가 사용하던 방법은 이렇습니다. 물론 정답은 없습니다.

    for(int i = 0; i < size; ++i)
        if(!num[ i ]) goto good;

bad:
    std::cout << "-1\n";
    return 0;

good:
    // blabla

std::string이었다면 범위 기반 for문을 사용할 수도 있습니다. 또, algorithm 헤더의 std::any_of를 사용하실 수도 있습니다.

  1. i++ 대신 ++i를 사용해 주세요.

추가적인 설명이나 이유가 필요한 부분이 있으면 말씀드리겠습니다.

1 Like

답변감사합니다!
글은 처음써보는거라 백준링크올리는것은 잘몰랐네요. 다음부터 꼭올리겠습니다.
세세한거 까지 집어주는 좋은 피드백 감사합니다.
시간도늦고 goto에대해 잘몰라서 완벽히 이해하기는 힘들것같네요.
내일 꼼꼼하게 읽고 내용 공부후에 다시한번 짜보도록 하겠습니다.
안녕히주무세요.
막막한거 풀어주셔서 다시한번 감사드립니다.

1 Like

GOTO Statement Considered Harmful이네 어쩌네 하면서 초보자들에서 goto문 사용을 지양하라고는 하지만, 몇몇 상황에서 goto문이 크게 유용한 건 부정할 수 없는 사실입니다. 물론 가독성과 최적화 가능성을 고려하면서 사용하셔야겠습니다.

함수포인터를 지양하는 이유가있나요?

std::sort의 인자로 함수 포인터를 보내면 아무리 함수에 inline을 붙여도 인라이닝이 안됩니다. 포인터는 컴파일 타임에 추적할 수 없기 때문이죠. 하지만 객체를 보내면, 인라이닝이 가능합니다. 다음의 방법들을 권장합니다:


  • functional 헤더의 객체
std::sort(s.begin(), s.end(), std::greater< char >());

  • 람다 객체
std::sort(s.begin(), s.end(), [](auto lhs, auto rhs) {
    return lhs > rhs;
});

  • 함수자

요즘에는 잘 사용하지 않습니다.

struct Cmp {
    inline auto operator()(auto lhs, auto rhs) const {
        return lhs > rhs;
    }
};

std::sort(s.begin(), s.end(), Cmp());

그리고 제발 C++에서 qsort 쓰지 말아주세요. 성능도 구리고, 범용성도 떨어집니다.

1 Like

감사합니다