글 읽기 - 1181번 c++ 반례 질문입니다.

rhehdtor 1년 전 0

우선 길이를 기준으로 정렬하고, 그 다음 사전순으로 정렬하는 함수를 작성했습니다. 예제나 게시판에 있는 반례들은 맞게 나오는데 왜 틀렸는지 모르겠네요 ㅠㅠ 정렬할 때는 bubble sort를 활용해봤는데 혹시 시간복잡도 때문에 틀린건지 아니면 반례가 있어서 틀린거지 생각해봐도 모르겠어서 질문드립니다.

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

string str[20002];
int num[20002];

void sort_by_len(int n);
void sort_by_dic(int n);


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> str[i];

        num[str[i].size()-1]++;
    }

    sort_by_len(n);
    sort_by_dic(n);
    

    // 중복 출력 제거
    cout << str[0] << '\n';

    for(int i=1; i<n; i++){
        if(str[i-1] == str[i]) continue;
        cout << str[i] << '\n';
    }

    return 0;
    
}

void sort_by_len(int n){

    string temp;
    for(int i=0; i<n-1; i++){
        for(int j=1; j<n-i; j++){
            if(str[j-1].size() > str[j].size()){
                
                swap(str[j-1], str[j]);
            }
        }
    }

}

void sort_by_dic(int n){
    int cur = 0;
    

    for(int i=0; i<n; i++){
        if(num[i] == 1){
            cur++;
            continue;
        }

        if(num[i] == 0)continue;
        
        int k=cur;
        int d= 0;

        for(int p=k; p < k + num[i] - 1; cur++, p++,d++){
            for(int j=k+1; j<k+num[i]-d && j < n; j++){
                if(str[j].compare(str[j-1]) == -1){
                    swap(str[j], str[j-1]);
                }

            }
        }
        
        cur++;

    }
}

djm03178 1년 전 0

string::compare는 비교 결과에 따라 음의 정수, 0, 양의 정수를 반환하는 것만 보장됩니다. 음의 정수라고 해서 그 값이 반드시 -1이어야 할 필요는 없고, 실제로 채점 환경에서는 -1로 고정되어 있지 않습니다.

rhehdtor 1년 전 0

djm03178// 답변 지금 봤네요. 감사합니다! 바꿔보니까 시간 초과 뜨는데 다시 고민해보고 작성해봐야겠네요. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1181번 c++ 반례 질문입니다.

rhehdtor 1년 전 0

djm03178 1년 전 0

rhehdtor 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말