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

문제

프로그래머스 코딩테스트 고득점 Kit - 정렬

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

코드 구현

def solution(numbers):
    answer = ''

    # 정답 코드
    numbers.sort(key=lambda x: str(x) * 3, reverse=True)    # numbers의 숫자를 str형으로 3번 반복한 값을 기준으로 내림차순 정렬
    for i in numbers:
        answer += str(i)
    answer = str(int(answer))       # 같은 수가 반복되는 정답 케이스가 있다면 걸러주기 (ex. '00' -> 0 -> '0')

    return answer

if __name__ == '__main__':
    print(solution([3, 30, 34, 5, 9]))
    print(solution([0, 0]))
    print(solution([100, 1000]))


### 순열 permutations로 해결하고자 한 코드 -> 시간 초과 발생
# from itertools import permutations
#
# def solution(numbers):
#     answer = ''
#
#     build_num = list(permutations(numbers, len(numbers)))
#     max_num = 0
#
#     for i in range(len(build_num)):
#         make_num = ''
#         for j in range(len(numbers)):
#             make_num += str(build_num[i][j])
#         if(max_num < int(make_num)):
#             max_num = int(make_num)
#
#     answer = str(max_num)
#
#     return answer

### 실패 코드 1
### (dict()으로 설정하니 3번 반복한 후 잘랐을 때 같은 수가 존재한걸 처리할 수 없음)
# num_dict = dict()
#
# for num in numbers:
#     str_num = str(num) * 3
#     num_dict[int(str_num[:3])] = str(num)
#
# print(num_dict)
# ans = list(sorted(num_dict.keys(), reverse=True))
#
# for i in ans:
#     answer += num_dict.get(i)

### 실패 코드 2
### (미완성)
# for num in numbers:
#     if(num < 10):
#         one_len_num.append(num)
#     else:
#         over_len_num.append(num)

# for num in numbers:
#     if (num < 10):
#         one_len_num = num
#     else:
#         over_len_num = num
#
#     if (one_len_num[0] > int(str(over_len_num[0])[0])):
#         ans.append(one_len_num[0])
#
# while (True):
#     for i in range(len(over_len_num)):
#         num_str = str(over_len_num[i])
#         if (int(num_str[0]) <= one_len_num[i]):
#             answer += str(one_len_num[0])
#             one_len_num.pop(0)

풀이

• 처음에는 정렬하는 기준에 있어서 패턴이 존재한다고 생각하여 실패 코드 2를 계속 건들고 있었다.
• 그러나 아무리해도 답이 보이지 않아서 permutations 순열을 통해 모든 경우의 수를 만들고 가장 큰 수를 도출하는 방법도 시도했는데 역시나 예상했던대로 시간초과가 발생하였다.
  • permutations 함수는 시간복잡도가 O(n!) 혹은 O(nr)으로 코테 문제에 쓰기에는 적합하지 않다고 한다…
    • https://school.programmers.co.kr/questions/25658
    • https://stackoverflow.com/questions/58677464/big-o-notation-of-the-permutation-algorithm-in-python-itertools-permutation
• 그래서 결국 다른 아이디어를 찾아보다가 정렬의 패턴을 찾아냈다.
  • numbers 배열에 있는 수를 문자열로 바꾼 뒤, 이를 3번 반복한 수를 기준으로 내림차순 정렬한다.
  • 문자열을 정렬할 경우 아스키코드 값을 기준으로 정렬되는데 이는 첫번째 인덱스 값을 기준으로 정렬된다.
  • ex) 3, 39, 30 이 있다하면 → 333, 393939, 303030 을 정렬하게 되고
    → 첫번째 인덱스인 3 은 우선 다 같은 값이니 → 그 뒤인 3, 9 ,0 의 아스키코드 값을 기준으로 정렬 → 9 > 3 > 0
    → 즉 39, 3, 30 으로 정렬된다.
    
  • 우리가 원했던 가장 큰 수를 도출하는 정렬 패턴이 나온다 !
    
• 이 정렬 패턴을 찾았을 때, 처음에는 3번 반복한 뒤 3자리까지 자른 수를 통해 비교하여 정답을 구할 수 있을거 같아서 실패 코드 1을 작성하였다.
  • 그러나 3번 반복 후 3자리까지 자른 수가 일정한 수들이 배열에 있는 경우, 이에 대해 사전 내에서 구별하기가 너무 어려워지기 때문에 결국 정답 코드를 참고하여 작성하였다.

What I learned

▶️ 배열.sort + lambda x : x 기준값

배열.sort(key = lambda x : str(x)*3, reverse = True)

참고 자료

https://school.programmers.co.kr/questions/41578
https://liveloper-jay.tistory.com/138
https://bio-info.tistory.com/196
https://what-am-i.tistory.com/244
https://wooaoe.tistory.com/82
https://esoongan.tistory.com/103