글 읽기 - 제가 고려하지 않은 tc가 어떤게 있을까요

wondy1128 7년 전 0

총 2가지 경우로 나누어 제거를 했습니다.

1. 뒷자리에 위치한 값보다 값이 작은 경우 -> 제거

2. 1의 경우에 모두 제거 되지 않은 경우 자릿수 맨 뒤부터 작은 값제거

두가지 제거를 하고 출력을 했을 때

테스트케이스가 안되는 것이 어떤게 있는지 잘모르겠습니다....

// 크게 만들기

#include<cstdio>
#define MAX 700000
int main(){
	int n,k;
	char string[MAX] = {0,};
	scanf("%d %d", &n, &k);
	scanf("%s",string);
	bool loopout = false;
	while(1){ // 제거 1: 뒤에 숫자가 더 큰지 아닌지 확인 후 제거
		if(k==0 || loopout) break;
		for(int i = 0 ; i < n ; i++){
			if('0' <= string[i] && string[i] <= '9'){
				for(int j = i+1 ; j < n ; j++ ){
					if(k==0) break;
					if('0' <= string[i] && string[i] <= '9'){
						if(string[i] <= string[j]){
							string[i] = 0;
							k--;
							break;
						}
						break;
					}
				}
			}
			if(i==n-1) loopout = true;
		}
	}
	while(k!=0){ // 제거 2 :모든 수가 오름인경우 작은 값부터 제거
		for(char v = '0' ; v <= '9' ; v++){
			for(int i = n-1 ; i >= 0 ; i--){
				if(k==0)break;
				if(string[i] == v){
					k--;
					string[i] = 0;
				}
			}
		}
	}
	for(int i = 0 ; i < n ; i++){
		if(string[i]!=0){
			printf("%c",string[i]);
		}
	}
}

sgc109 7년 전 6

6 2
436436

한번해보세요 ㅎ

6436 나와야하거든여

간과하기쉬운부분을 간과하셨어요 좀더 생각해보세요~

wondy1128 7년 전 1

@sgc109

해결하였습니다...

시간초과가 나는데 이건 고민해보겠습니다......

// 크게 만들기
#include<cstdio>
#define MAX 700000
int main(){
	int n,k;
	char string[MAX] = {0,};
	scanf("%d %d", &n, &k);
	scanf("%s",string);

	// 제거 1: 뒤에 숫자가 더 큰지 아닌지 확인 후 제거
	// O(n^2)
	for(int i = 0 ; i < n ; i++){  // n
		if('0' <= string[i] && string[i] <= '9'){
			for(int j = i+1 ; j < i+1+k ; j++ ){ // n
				if(k==0) break;
				if(string[i] < string[j]){
					string[i] = 0;
					k--;
					break;
				}
			}
		}
	}
	//O(9*n)
	// 제거 2 :모든 수가 오름인경우 작은 값부터 제거
	for(char v = '0' ; v <= '9' ; v++){ // 9
		for(int i = n-1 ; i >= 0 ; i--){ // n
			if(k==0)break;
			if(string[i] == v){
				k--;
				string[i] = 0;
			}
		}
	}

	// 결과출력
	for(int i = 0 ; i < n ; i++){
		if(string[i]!=0) printf("%c",string[i]);
	}
	return 0;
}

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

문제

문제

출처

ICPC

제가 고려하지 않은 tc가 어떤게 있을까요

wondy1128 7년 전 0

sgc109 7년 전 6

wondy1128 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말