[프로그래머스] 가장 큰 수

가장 큰 수 

문제

• 가장 큰 수(https://programmers.co.kr/learn/courses/30/lessons/42746)

풀이

1. 모든 경우 수 구하기

[코드]

• 결론부터 말하면 테스트 케이스 통과 실패가 뜨며 다른 접근 방법이 필요하다. 아래 2번 풀이를 보자. 모든 경우 수 구하기 코드는 생략

[접근법]

• 단순하게 DFS 알고리즘을 이용해서 모든 경우를 구하여 비교
• ex. numbers = [6, 10, 2]이 입력일 때 [6102, 6210, 1062, 1026, 2610, 2106]를 모두 찾아 비교

[장점]

• 장점이랄것도 없지만... 가장 직관적으로 떠올릴 수 있는 방법이다

[단점]

• (len(numbers)!) 경우 수를 모두 탐색해야하기에 시간이 엄청나게 걸린다...
• 제한 사항에 보면 numbers의 길이는 최대 10만개까지라고 하는데 (10만!)을 찾다가 한 세월 걸린다... 채점하면 시간 초과가 우르르 보일 것이다
• 다른 방법이 필요하다!!😅😅

2. 전처리 후 숫자 정렬

[코드]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def solution(numbers): if len(set(numbers)) == 1 and numbers[0] == 0: return '0' def fill_number(number, length): # 자릿수 변경하는 함수 filled_number = '' while True: filled_number += number if len(filled_number) > length: break return filled_number[:length] max_length = len('1000') # filled_numbers = [[ 자릿수 변경 후 숫자, 자릿 수 변경 전 숫자], ... ] filled_numbers = [[int(fill_number(str(n), max_length)), n] for n in numbers] filled_numbers = sorted(filled_numbers, reverse=True, key=lambda x: x[0]) answer = ''.join([str(n[1]) for n in filled_numbers]) return answer

[접근법]

• 전처리를 하여 최대한 루프를 적게 돌면서 정렬 시킬 수 있는 방법을 찾는다
• 제일 큰 수를 찾으므로 numbers의 입력 중 앞자리 수가 가장 큰 경우부터 앞에 배치시키는 것을 생각할 수 있을 것이다
• ex. numbers = [34, 65] 일 때, 앞자리 수들은 [3, 6]이 된다. 6이 더 크므로 65를 앞에 배치시킨다 → [65, 34]
• 만약에 자릿수가 다르면 어떻게 될까? 자릿수가 더 작은 수는 큰 수와 비교하려도 비교할 숫자가 없다
• ex. numbers = [3, 39]가 들어 올 때, 두 수 모두 앞자리가 3이다. 39는 다음 자리수인 9를 선정하면되지만, 3은 어떤 수를 비교해야 할까??
• 모든 수들이 제한 조건의 최대 입력수(1000)와 같은 자리수를 가지도록 만들어 준다
• ex. numbers = [3, 39] 일 때, [3000, 3900]로 만들어 비교할 수 있을 것이다

👏👏👏 드디어 비교를 하여 숫자를 선정할 수 있게 되었다!! 구현하여 채점해 보자! 👏👏👏

• 안타깝지만 아직도 실패 케이스가 있는 것을 확인할 수 있다 😂
• 자리수 변경 전에는 다른 값이지만 변경 후에는 같은 값을 가지는 경우가 문제가 된다
• ex. numbers = [3, 30] → [3000, 3000] 이 된다. 이 때 변경 후 값이 같다고해서 아무 수나 선정하면 [30, 3]이 최대값으로 선정되는 불상사가 생긴다
• 위 경우를 막기 위해선 입력값들의 우선순위를 구분할 필요가 있다
• 같은 자리수를 가지도록 변경할 때 원래 숫자를 반복해서 채워주고, 그 중 제일 큰 값을 선정하자
• ex. numbers = [3, 30] → [3333, 3030] 이 된다. 3333이 가장 크므로 이를 선정한다. 결국 [3, 30]을 최대값으로 찾을 수 있다
• 원래 숫자를 반복함으로써 자연스레 어떤 숫자가 우선되는지 정해진다
• 마지막으로 아예 모든 값들이 0인 경우는 0을 반환하도록 하자
• ex. numbers = [0, 0] 일 때는 값 비교가 무의미하므로 바로 0을 Return

여기까지 완료하면 모든 테스트 케이스를 통과하는 것을 볼 수 있다!!!😊😊😊 

[추가 테스트 케이스]

• 프로그래머스 질문하기에서 다른 분들이 올려주신 테스트 케이스가 있다. 구현하면서 한번씩 체크해보는 것을 추천 드린다😃
• [383, 38] → 38383
• [838, 83] → 83883
• [0, 0, 0] → 0