글 읽기 - 반례 부탁드립니다..

lwh1992 4년 전 0

배열을 퀵소트 할지 몰라 버블정렬 사용했습니다..

문제가 시간초과가 아니라 틀렸습니다로 뜹니다..

예시는 되는데 어떤게 안되는지 여쭤보려 합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[20001][51];
int d[20001][2];

int main(){
	int n;
	scanf("%d",&n);
	
	for(int i=0;i<n;i++){
		scanf("%s",a[i]);
		d[i][0]=i;
		d[i][1]=strlen(a[i]);
	}
	
	for(int i=n-1;i>0;i--){
		for(int j=0;j<i;j++){
			if(d[j][1]>d[j+1][1]){
				int tmp=d[j][1];
				d[j][1]=d[j+1][1];
				d[j+1][1]=tmp;
				tmp=d[j][0];
				d[j][0]=d[j+1][0];
				d[j+1][0]=tmp;
			}
			else if(d[j][1]==d[j+1][1]){
				if(strcmp(a[d[j][0]],a[d[j+1][0]])==1){
					int tmp=d[j][1];
					d[j][1]=d[j+1][1];
					d[j+1][1]=tmp;
					tmp=d[j][0];
					d[j][0]=d[j+1][0];
					d[j+1][0]=tmp;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		if(i!=0 && strcmp(a[d[i-1][0]],a[d[i][0]])==0)
			continue;
		printf("%s\n",a[d[i][0]]);
	}
	
    return 0;
}

park780172 4년 전 0

O(n²) 정렬말고, O(nlogn) 정렬을 사용하시는게 좋을 것 같습니다.

kipa00 4년 전 0

이 글을 참고하세요. 반례입니다.

4
k
i
p
a

lwh1992 4년 전 0

input:

4 k i p a

output:

a i k p

로 나오는데 맞는거 아닌가요??

kipa00 4년 전 1

Return Value
Negative value if lhs appears before rhs in lexicographical order.

Zero if lhs and rhs compare equal.

Positive value if lhs appears after rhs in lexicographical order.

언제나 1을 돌려주는 게 아니고, 상황에 따라 적절한 양수를 돌려주기만 하면 되기 때문에, 28번째 줄이 잘못 동작할 가능성이 있습니다.

28번째 줄의 ==1를 >0으로 고쳐 보세요.

lwh1992 4년 전 0

도와주셔서 감사합니다!!!

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

문제

문제

출처

ICPC

반례 부탁드립니다..

lwh1992 4년 전 0

park780172 4년 전 0

kipa00 4년 전 0

lwh1992 4년 전 0

kipa00 4년 전 1

lwh1992 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말