문제
https://school.programmers.co.kr/learn/courses/30/lessons/42746
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
numbers | return |
[6, 10, 2] | "6210" |
[3, 30, 34, 5, 9] | "9534330" |
풀이
접근
처음엔 그냥 정렬하면 되겠지, 생각했다.
리스트들을 돌면서 가장 큰 수를 만들면 되는 거 아닌가? 했는데
생각해보니 이건 자릿수에 함정이 있었다.
이어붙인다고 생각하면, 당장 numbers
리스트에 들어있는 수가 큰 것이 중요한 게 아니다.
이어 붙이면 어차피 자릿수는 같으니 결국 앞자리에 오는 숫자 하나하나가 커야 한다.
numbers = [3, 30, 34, 5, 9]
의 예시에서,
30과 9를 비교하면 이어 붙일 땐 9를 앞에 붙여야 한다.
그러므로 sorted
를 사용해 문자열로 변환해 비교한다.
문자열로 비교하면 맨 앞자리부터 비교하므로, sorted(['30','9'],reverse=True)
를 하면 ['9','30']
이 되기 때문이다.
그런데 30과 3처럼 앞자리가 같은 애들은 30이 먼저 정렬되게 된다.
하지만 이어 붙인다고 생각하면 330 > 303 이기 때문에 3이 앞에 와야 하는데,
그러려면 이 숫자들이 높은 자릿수에 있을 때를 가정해서 비교해야 한다는 거다. (3이 더 높은 자릿수일 때 > 30이 더 높은 자릿수일때 )
따라서 문자열을 세번 반복해 이어붙이면 뒷자리는 상관없이 높은자리로 가정해서 비교할 수 있다.
sorted(['30','3'])
는 ['30','3']
이 되지만, sorted(['303030','333'])
은 ['333', '303030']
이기 때문
def solution(numbers):
# 3번씩 이어 붙인 문자열들을 내림차순으로 정렬
numbers = sorted(numbers, key=lambda x: str(x)*3, reverse=True)
#문자열들을 전부 이어 붙인다.
answer = ''.join(map(str, numbers))
이렇게 완성했는데,
실패한 테스트 케이스가 있었다.
도저히 어디서 문제가 생긴 건지 모르겠어서 질문하기에 들어가봤는데,
['0', '0', '0', '0']
처럼 모든 원소가 0인 반례가 있다는 것...
나는 아직 멀었다...
아무튼 그래서 해당 조건을 추가해주고 다시 완성했다.
풀이 코드
def solution(numbers):
# 3번씩 이어 붙인 문자열들을 내림차순으로 정렬
numbers = sorted(numbers, key=lambda x: str(x)*3, reverse=True)
#문자열들을 전부 이어 붙인다.
answer = ''.join(map(str, numbers))
# numbers의 원소가 모두 0일 때
return answer if int(answer) != 0 else '0'
GitHub 댓글