urie1   1년 전

저는 입력값의 자릿수를 참고하여, 입력값을 모두 10^10자리로 변환후, int로 바꾸어 크기 비교하는 방법을 사용하였습니다. 

각 입력값은 [10^10으로 변환된 문자열, 본래 문자열의 길이(자릿수)] 으로 sliced_n에 저장됩니다. (sliced_n=2차원 배열)

입력값[0]을 큰 순서로 정렬후 이 값이 같다면 , [1]즉 자릿수가 작은 순으로 정렬합니다. 

sliced_n.sort(key=lambda x: (int(x[0]),-x[1]),reverse=True)

3,30->330으로 판별하기 위해서입니다. 

하지만 반례가 있습니다. 

ex) 9 91

->919 (91000000...>90000000..., 오답)

->990(정답)

이 반례를 제 알고리즘 상에서 해결하는 방법을 모르겠습니다. 

제 접근방법이 틀렸던 걸까요?

lcr7324   1년 전

"변환"의 방법을 정확히 어떻게 해야 할까요? 단순히 뒤에 0을 붙여서 자릿수가 같게 맞추는 것이면 충분할까요?

a자리인 수 x와 b자리인 수 y가 주어졌을 때, x 뒤에 y를 붙여서 쓴 것과 y 뒤에 x를 붙여서 쓴 것 중 어느 하나가 다른 하나보다 더 컸다고 합시다.

이 비교 결과를 가지고, x와 y를 비교할 수 있는, 그리하여 어느 것을 뒤에 써야 하는지 결정할 수 있는 일관적인 기준을 만드는 것이 우리의 목표일 겁니다.

이러한 일관적인 기준이 만들어지는 것이 가능하다면 이 기준을 가지고 정렬하는 그리디 방식의 풀이가 가능할 것이며, 불가능하다면 다른 방법을 고려해야겠죠.

"xy와 yx중 어느 하나가 다른 것보다 크다"라는 상황을 수식으로 만들어보시고 이 수식을 이리저리 조합해보세요.

yoonjaek000   8달 전

문자열로 해보세요

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