시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 294 194 166 71.861%

문제

어떤 수 A가 주어졌을 때, A의 다음수를 구하는 프로그램을 작성하시오.

A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수 이다.

A와 B의 구성이 같다는 말은 A를 이루고 있는 각 자리수의 등장 횟수가, B를 이루는 각 자리수의 등장 횟수와 같을 때 이다.

예를 들어 123과 321은 구성이 같다. 왜냐하면 두 수 모두 1이 1번, 2가 1번, 3이 1번 나오기 때문이다. 마찬가지로 14232와 12243도 구성이 같다.

하지만, 14232와 14432는 구성이 같지 않다. 

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 둘째 줄부터 T개 줄에는 각 테스트 케이스가 주어진다. 테스트 케이스는 한 줄로 이루어져 있으며, 수 A이다. A는 최대 80자리 자연수이다.

출력

각 테스트 케이스에 대해서, 한 줄에 하나씩 A의 다음수를 출력한다. 만약, A의 다음수가 없을 때는 BIGGEST를 출력한다.

예제 입력 1

3
123
279134399742
987

예제 출력 1

132
279134423799
BIGGEST
W3sicHJvYmxlbV9pZCI6IjI2OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZTRcdWM3NGNcdWMyMTggXHVhZDZjXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjMjE4IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgQVx1Yzc1OCBcdWIyZTRcdWM3NGNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPkFcdWM3NTggXHViMmU0XHVjNzRjXHVjMjE4XHViMjk0IEFcdWM2NDAgXHVhZDZjXHVjMTMxXHVjNzc0IFx1YWMxOVx1YzczY1x1YmE3NFx1YzExYywgQVx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzIxOCBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFcdWM2NDAgQlx1Yzc1OCBcdWFkNmNcdWMxMzFcdWM3NzQgXHVhYzE5XHViMmU0XHViMjk0IFx1YjlkMFx1Yzc0MCBBXHViOTdjIFx1Yzc3NFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVhYzAxIFx1Yzc5MFx1YjlhY1x1YzIxOFx1Yzc1OCBcdWI0ZjFcdWM3YTUgXHVkNjlmXHVjMjE4XHVhYzAwLCBCXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFjMDEgXHVjNzkwXHViOWFjXHVjMjE4XHVjNzU4IFx1YjRmMVx1YzdhNSBcdWQ2OWZcdWMyMThcdWM2NDAgXHVhYzE5XHVjNzQ0IFx1YjU0YyBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgMTIzXHVhY2ZjIDMyMVx1Yzc0MCBcdWFkNmNcdWMxMzFcdWM3NzQgXHVhYzE5XHViMmU0LiBcdWM2NWNcdWIwZDBcdWQ1NThcdWJhNzQgXHViNDUwIFx1YzIxOCBcdWJhYThcdWI0NTAgMVx1Yzc3NCAxXHViYzg4LCAyXHVhYzAwIDFcdWJjODgsIDNcdWM3NzQgMVx1YmM4OCBcdWIwOThcdWM2MjRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgMTQyMzJcdWM2NDAgMTIyNDNcdWIzYzQgXHVhZDZjXHVjMTMxXHVjNzc0IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCAxNDIzMlx1YzY0MCAxNDQzMlx1YjI5NCBcdWFkNmNcdWMxMzFcdWM3NzQgXHVhYzE5XHVjOWMwIFx1YzU0YVx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgxJmx0Oz1UJmx0Oz0xLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFRcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzIxOCBBXHVjNzc0XHViMmU0LiBBXHViMjk0IFx1Y2Q1Y1x1YjMwMCA4MFx1Yzc5MFx1YjlhYyBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBBXHVjNzU4IFx1YjJlNFx1Yzc0Y1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgQVx1Yzc1OCBcdWIyZTRcdWM3NGNcdWMyMThcdWFjMDAgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YjI5NCBCSUdHRVNUXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIE5leHQgUGVybXV0YXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHRha2VzIGEgKHBvc3NpYmx5IGxvbmcpIHN0cmluZyBvZiBkZWNpbWFsIGRpZ2l0cywgYW5kIG91dHB1dHMgdGhlIHBlcm11dGF0aW9uIG9mIHRob3NlIGRlY2ltYWwgZGlnaXRzIHRoYXQgaGFzIHRoZSBuZXh0IGxhcmdlciB2YWx1ZSAoYXMgYSBkZWNpbWFsIG51bWJlcikgdGhhbiB0aGUgaW5wdXQgbnVtYmVyLiBGb3IgZXhhbXBsZTombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuMTIzIC0mZ3Q7IDEzMlxyXG4yNzkxMzQzOTk3NDIgLSZndDsgMjc5MTM0NDIzNzk5PFwvcHJlPlxyXG5cclxuPHA+SXQgaXMgcG9zc2libGUgdGhhdCBubyBwZXJtdXRhdGlvbiBvZiB0aGUgaW5wdXQgZGlnaXRzIGhhcyBhIGxhcmdlciB2YWx1ZS4gRm9yIGV4YW1wbGUsIDk4Ny48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGlzIGEgc2luZ2xlIGxpbmUgdGhhdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBmb2xsb3dlZCBieSBhIHNwYWNlLCBmb2xsb3dlZCBieSB1cCB0byA4MCBkZWNpbWFsIGRpZ2l0cyB3aGljaCBpcyB0aGUgaW5wdXQgdmFsdWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0LiBJZiB0aGVyZSBpcyBubyBsYXJnZXIgcGVybXV0YXRpb24gb2YgdGhlIGlucHV0IGRpZ2l0cywgdGhlIG91dHB1dCBzaG91bGQgYmUgdGhlIGRhdGEgc2V0IG51bWJlciBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIHN0cmluZyBCSUdHRVNULiBJZiB0aGVyZSBpcyBhIHNvbHV0aW9uLCB0aGUgb3V0cHV0IHNob3VsZCBiZSB0aGUgZGF0YSBzZXQgbnVtYmVyLCBhIHNpbmdsZSBzcGFjZSBhbmQgdGhlIG5leHQgbGFyZ2VyIHBlcm11dGF0aW9uIG9mIHRoZSBpbnB1dCBkaWdpdHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest E번