2870번: 수학숙제 [C++]

수학숙제 

다국어

한국어   

시간 제한            메모리 제한                      제출                         정답                          맞힌 사람              정답 비율

1 초

128 MB

6069

2025

1583

33.503%

문제

상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

입력

첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

출력

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

예제 입력 1 복사

2
lo3za4
01

예제 출력 1 복사

1
3
4

예제 입력 2 복사

4
43silos0
zita002
le2sim
231233

예제 출력 2 복사

0
2
2
43
231233

예제 입력 3 복사

4
01bond
02james007
03bond
04austinpowers000

예제 출력 3 복사

0
1
2
3
4
7

 

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

2870번: 수학숙제

 

흐름

 

 

메모리 초과가 난 코드 (cmp 문제)

bool cmp(string a, string b){
    if(m[a]>m[b]) return a>b;
    return a<b;
}

여기서 map은 문자열에 대한 count를 저장한다.

 

백준 Q&A를 보고 cmp 부분 복사해서 돌렸더니 맞았다.

https://www.acmicpc.net/board/view/14855

글 읽기 - 문자열로 비교했는데 왜 틀린걸까요..?

메모리 초과가 난 이유는 map에 문자열을 저장했기때문일수도 있을것같다.

그리고 비교함수를 너무 대충 감으로 만들었기때문이다.

 

선생님 풀이를 듣고 이 코드를 보니 틀렸음을 알 수 있다.

우리가 첫번째로 비교해야할 것은 글자수이고(숫자 자리수가 클수록 큰 숫자)

글자수가 같을 경우에 두번째로 비교해야할 것이 문자이다.

 

그러므로

bool cmp(string a, string b){
    if(m[a]==m[b]) return a<b;
    return m[a]<m[b];
}

가 의도에 맞는 코드이다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int n;
string inp, str, temp;
bool flag;
vector<string> v;
map<string, int> m; //숫자 자릿수 저장
bool cmp(string a, string b){
    int lenA = a.length();
    int lenB = b.length();
    //길이 비교
    if(lenA<lenB) return true;
    else if(lenA>lenB) return false;
    //길이가 같다면 앞 자리수부터 비교
    for (int i = 0; i < lenA; i++) {
		if (a[i] < b[i]) return true;
		if (a[i] > b[i]) return false;
	}
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> n;
    while (n--){
        //초기값 설정
        str="";
        flag=false;

        cin >> inp;
        //2. 숫자를 찾아 저장
        for(char c:inp){
            temp=c; //atoi 함수 이용하기위해 char -> 문자열로 바꿈
            if(atoi(temp.c_str()) || c=='0'){ //숫자이면
                str += c; //한글자씩 저장
                flag=true; 
            }
            else{ //숫자가 아니면
                if(flag==true) { //직전까지 숫자였으면 그 숫자덩어리 저장
                    while (str.front()=='0' && str.length()>1){
                        str.erase(str.begin()); //맨 앞에 0이있는 두자리 이상 숫자는 0 제거
                    }
                    v.push_back(str); //추가
                    if(str=="0") m[str]=1;
                    str=""; //초기화
                }
                flag=false;
            };
        }
        if(str!="") {
             while(str.front()=='0' && str.length()>1){
                        str.erase(str.begin()); //맨 앞에 0이있는 두자리 이상 숫자는 0 제거
            }
            v.push_back(str); //저장되지 않은 마지막 숫자가 있다면 저장
            if(str=="0") m[str]=1;
        }
    }
    //3. 오름차순으로 정렬
    sort(v.begin(), v.end(), cmp); //오름차순
    //4. 출력
    for(string s:v) cout << s << "\n";
    return 0;    
}

맞았다.

0을 따로 제거하는 부분이나 글자수를 더하는 부분에서 여러 예외가 많아서 시간이 많이 걸렸던 문제이다.

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

int n;
vector<string> v;
string s,ret;

void go(){
    while(true){
        if(ret.size() && ret.front()=='0')ret.erase(ret.begin()); //앞이 0이면 지우기
        else break;
    }
    if(ret.size()==0) ret="0"; //000일 경우 0으로 만들기
    v.push_back(ret);
    ret="";
}

bool cmp(string a, string b){
    if(a.size()==b.size()) return a<b;
    return a.size()< b.size();
}

int main(){
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> s;
        ret="";
        //2. 숫자 만들기
        for(int j=0;j<s.size();j++){
            if(s[j]<65) ret += s[j]; //문자열이면 추가
            else if(ret.size()) go(); //숫자일 경우 go
        }
        if(ret.size()) go(); //숫자로 끝났을 경우 추가하기
    }
    //3. 오름차순으로 출력하기
    sort(v.begin(), v.end(), cmp);
    //4. 정답 출력
    for(string i:v) cout << i << " \n";
    return 0;
}

숫자인지 판별할때 s[j]<97도 맞다.(문제에서는 소문자와 숫자로만 구성된다고 했기때문)

 

유의점

• 문자열이 클 경우에(이 문제에서는 최대 100글자) string으로 처리하자.
• string sort시에 아스키코드 기준으로 정렬되므로 (10<2, 앞에서부터 차례대로 비교) 따로 cmp 비교함수를 만들어야한다.
• 문자열에서 이 문자가 숫자인지 판별할때 atoi함수보다 아스키코드 값으로 비교하는것이 편하다.
• 함수로 쪼개서 작성하면 보기 쉽고 편하다.