[백준] 10610. 30 (+ string)

문제

https://www.acmicpc.net/problem/10610


풀이

개인적으로 string을 사용하는게 좀 약하다고 생각하고 있었는데, 그걸 제대로 느끼게 해준 문제이다. 문제 분류가 그리디 알고리즘으로 되어있는데 사실 거기까지 미치지 않고 단순 수학 및 구현 문제라고 생각이 든다. (아마 가장 큰 수라 내림차순으로 정렬하면서 고려해줘야 한다는 부분에서 그리디 알고리즘으로 분류한게 아닐까 생각한다.) 일단 문제 자체는 매우 간단하다. 어떤 수가 주어졌을 때, 그 수의 각 자리를 재배열해서 30으로 나누어지는가 이다. 풀이방식은 아래와 같다.

• 10^5개의 숫자로 이루어져있으므로, unsigned long long도 불가능하다. 따라서 string으로 입력받는다.
• string에서 0이 있는지 확인한다. (30으로 나누어져야 하므로) 없으면 -1 출력.
• 0이 한개 이상 있으면 한개만 지워준다.
• 3의 배수인지 판단하려면 수의 모든 자리의 숫자의 합이 3의 배수여야한다.
• 각 자리 숫자의 합이 3의 배수이면 내림차순으로 sort한 후 뒤에 0을 붙여서 출력.
• 3의 배수가 아니면 -1 출력 

소스코드

//
//  Thirty.cpp
//  test
//
//  Created by 신기열 on 27/05/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm.h>

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

int main(){
    
    //문제에서 string의 길이가 매우 기므로 unsinged long long으로 표현
    unsigned long long pos, sum = 0, size;
    
    string s;
    cin >> s;
    
    //string 의 길이 구하기
    size = s.length();
    
    //s에 0이 포함되어 있으면 0 한개 지워주기 (30의 배수이므로 10의 배수이기도 하니까)
    if(s.find("0") != string::npos){
        pos = s.find("0");
        s.erase(pos, 1);
        
        //그 후 각 자리를 모두 더해서 3의 배수인지 확인 (3의 배수인 수는 각 자리를 모두 더한 합이 3의 배수가 됨)
        for(int i = 0; i < s.size(); i++){
            int n = s[i] - 48;
            sum += n;
        }
        
        //3의 배수라면 compare 함수로 내림차순 정렬하고 마지막에 아까 지워준 0을 붙여서 출력, 3의 배수가 아니면 30의 배수도 아니므로 -1 출력
        if(sum % 3 == 0){
            sort(s.begin(), s.end(), compare);
            cout << s + "0";
        }
        else{
            cout << -1;
        }
    }
    
    //s에 0이 포함되어 있지 않으면 30의 배수가 아니므로 -1 출력
    else{
        cout << -1;
    }

    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/Greedy/Thirty.cpp



++
1. string.find() 

string.find() 함수는 index를 return한다. 만약 find를 해서 찾은 문자열이 존재하는지 안하는지 알고 싶으면 npos를 이용할 수 있다. npos는 string.find()에서 반환값이 존재하지 않을 때 return해주는 값이다.

if(s.find("0") != string::npos){
        //string s에 0이 존재 할 경우 (npos가 아니니까)
    }

if(s.find("0") == string::npos){        
        //string s에 0이 존재하지 않는 경우 (npos니까)
    }

2. string의 각 자리수 int로 변환

string이나 char가 한자리 숫자일 때, atoi를 이용해서 int로 변환할 수도 있지만 ASCII 코드를 알고 있다면 그냥 48만 빼줘도 나온다. 여기서는 각 자리의 숫자를 더해주기 위해서 사용하였다.

for(int i = 0; i < s.size(); i++){
            int n = s[i] - 48;
            sum += n;
        }

3. string 내림차순 정렬 및 string 합치기

string을 재정렬해서 0을 붙이는 과정이 있었는데, 배열은 sort(array, array + size)와 같은 방식으로 sort함수를 사용했지만, string은 이렇게 하면 오류가 난다. 벡터와 같은 방식으로 "처음부터 끝까지"라는 의미로 표현해준다.
또한 sort함수는 오름차순으로 정렬이 되는데, 내림차순 정렬을 원한다면 sort함수에 비교함수를 작성하여 넣어주면 된다. 단순히 크기비교일 뿐이므로 굳이 char사이의 크기 비교를 할 필요 없이 강제 int 변환 후 비교해주기만 해도 충분하다.
string에 string을 붙이는 건 "+"를 이용할 수 있다.

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

sort(s.begin(), s.end(), compare);
cout << s + "0";