[정렬] 가장 큰 수

[jeeyeonLIM]

문제 설명

• 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

• 출처 : https://programmers.co.kr/learn/courses/30/lessons/42746

참고, 목표

• 본격적인 코테 준비 시작인데 ㅠㅠ 이것조차 어렵다
• 차근히 함수 정리하고 암기하자

[jeeyeonLIM]

작성코드

• 아쉽게도 요건 내가 처음부터 작성한게 없어 공백이다.
• 나중에 다시 풀 때 처음부터 스스로 해보자.

  ~ㅠ_ㅠ~

[jeeyeonLIM]

최종 코드를 작성하기까지

알고리즘 설명 - 참고링크

METHOD1 - 참고 링크❌

• 모든 조합 리스트에 넣고 최대값 추출하기
• 위에 요런식으로 모든 조합을 리스트에 넣어주고 max추출하려 했다 (ㅎㅎ코테알못)

  
  import itertools
  def solution(numbers):
  numbers_str = [str(i) for i in numbers]
  comb = itertools.permutations(numbers_str)  # input_list 원소값을 2개씩 조합
  comb = [int("".join(i)) for i in comb]       # comb = map(int, ["".join(i) for i in comb])
  return str(max(comb))

solution([6, 10, 2])

![image](https://user-images.githubusercontent.com/45617225/83649987-cbe9fe80-a5f2-11ea-8e5b-6c455f764862.png)
- 결과는 시간 초과로 모두 실패, 게다가 패키지 썼음ㅠㅠ

#### 추가 설명
- 즉 밑에와 같이 "".join() 써주면 "" 기준으로 각각의 원소를 join해줌.
![image](https://user-images.githubusercontent.com/45617225/83646814-23866b00-a5ef-11ea-8341-f2b0255bceb5.png)
- `itertools` 모듈의 `permutations` 함수는 이렇게 모든 가능한 조합 추출해준다.
![image](https://user-images.githubusercontent.com/45617225/83661817-aadcda00-a601-11ea-9c03-04fec3d720d7.png)
- 참고로 ```itertools.permutations(s_num,2)``` 이렇게 하면 2개씩 가능한 조합 추출해준다 3개니깐 총 3! 만큼 값 추출됨.
![image](https://user-images.githubusercontent.com/45617225/83661931-cfd14d00-a601-11ea-9da2-a81f0f55038e.png)

- [참고] 문자열 list 조인시 👇 요런식으로 공백 단위로 join해서 붙여줄 수 있음.

["".join(i) for i in list]

### METHOD2 - [참고 링크](https://sinsomi.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Python-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%88%98-%EC%B4%88%EC%BD%94%EB%8D%94)
- 요 티스토리 글 보고 이해됨. 처음에 문자열 리스트를 그대로 앞으로 가져와서 첫자리부터 대소비교하는 개념이 잘 와닿지 않았는데 생각보다 간단한 개념이였다 ..! 

#### VER1.❌
```python
def solution(numbers):
    numbers_str = [str(i) for i in numbers]
    numbers_str.sort(key = lambda x:(x*6)[:6], reverse = True)
    return "".join(numbers_str)

solution([6, 10, 2])

• 하지만! Test case 11 에서 실패했다.

VER2. 수정된 최종본.⭕

def solution(numbers):
    if sum(numbers) == 0: # 만약 [0,0,0] 같은 원소 모두 0인값 들어온다면
        return "0" # str변환하고 공백기준으로 붙여라
    else: 
        numbers_str = [str(i) for i in numbers]
        numbers_str.sort(key = lambda x:(x*6)[:6], reverse = True) # 6번 반복해준다음 앞자리 6개만 파싱하여 값 비교
        return "".join(numbers_str) 

# solution([6, 10, 2])
solution([0, 0, 0])

• 앞서 case 11은 [0,0,0,0] 이렇게 들어오는 경우였고 이 경우를 고려해주지 않았다. 즉 '0000' 요렇게 나온다.
• [1,1,1,1]과 같이 모두 1인경우엔 '1111'이렇게 출력되어 원하는 결과가 맞지만 위와 같은 경우 '0000' 이라는 숫자는 없어 0으로 출력되어야 한다.
• [0,0,0,0] 문제를 해결하기 위해서 다른 사람은 아래와 같이 했다

  def solution(numbers):
  numbers = list(map(str, numbers))
  numbers.sort(key=lambda x: x*3, reverse=True)
  return str(int(''.join(numbers)))

• 마지막에 int로 변환한 뒤 str으로 재변환하여 0000이 아닌 0으로 출력되도록! 👍
• 이런 센스!

[jeeyeonLIM]

느낀점

계속 고민해보고 노가다를 하더라도 무조건 output 을 내봐야 한다고 생각한다. 하지만 함수도 잘 모르고 list 다루기조차 아직 익숙치 않았다. 그래서 코드를 찾아보게 되었고 공부하면서 익혀갔다. 코테라는 게 답을 찾는 것이 절대 아니고 제한 시간 내 답을 찾는것이다. 무조건 시간 효율적인 코드로 작성해 내야 한다 처음이라 이렇게 엄청나게 자세하게 설명을 써버렸지만 점점 코드만 쓰게 되겠지. ~나중에 요 정리해 놓은 것보고 이런것까지 정리했단 말이야 했음 좋겠다~

[jeeyeonLIM]

다시 풀기

• 쉽지가 않다
• numbers [3, 30, 34, 5, 9] 이렇게 있을 때 각각 원소가 1,000 미만이므로
• 3이라고 하면 3333, 3030, 3434, 5555, 9999 이렇게 비교해준다는 의미가 된다.
• 즉, 9999 > 5555 > 3434 > 3333 > 3030 이런 대소 관계에 의하여 정렬이 됨.

• 그 후 join하여 문자열로 만들어주면 된다.

  def solution(numbers):
  
  numbers= sorted( map(str, numbers),   # 원소를 전부 str로 치환하기
                  reverse=True,         # x*3이 큰 숫자대로 역순 정렬
                  key = lambda x : x*3) # 3자리를 뒤에 더해주기(최대 천의자리)
  return ''.join(numbers)