[알고리즘][Swift] #2. 가장 큰 수

안녕하세요! caution 입니다. '-'

알고리즘 문제 풀이 두 번째 시간입니다. 이번 문제도 카카오 프로그래머스에서 풀어보았습니다!

문제 선정 기준은 따로 없습니다!!!! 재밌을 것 같은 거, 그 중에 풀어서 정답을 맞춘거!!!! 입니다 ㅋㅋㅋㅋㅋㅋ

언젠가 문제 풀이가 세 자리 수가 될 수 있었으면 좋겠네요.

오늘의 문제는 LEVEL 2 가장 큰 수 입니다.

문제 설명

---

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

---

numbers의 길이는 1 이상 100,000 이하입니다.

numbers의 원소는 0 이상 1,000 이하입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

지난 번 문제였던 프린터 문제보단 상당히 설명이 간략한 문제네요. 알고리즘은 처음 문제를 풀 때는 모르지만, 이렇게 문제를 풀어놓고 보면 제시된 설명과 제한 사항에서 많은 힌트가 주어진다는 걸 알게됩니다. 제가 굵게 칠해 놓은 부분이 보이시나요?

0 또는 양의 정수가 담긴 배열 numbers

순서를 재배치하여 만들 수 있는 가장 큰 수

정답이 너무 클 수 있으니 문자열 바꾼다.

요약하자면, 0 이상 1,000 이하의 정수가 들어있는 numbers 가 주어지고, 여기에 주어진 정수들을 이어붙여서 만들 수 있는 가장 큰 수를 만들되, 문자열로 결과값을 알려달라고 하네요.

배열이 주어지고, 그 배열을 하나의 결과로 이어붙여야 하는데, 배열 값의 순서를 재배치 해야 한다. 이 말을 생각해보면, 결국 배열을 정렬해야 하는 문제임을 알 수 있습니다. 프로그래머스에서 보면 카테고리도 정렬 > 가장 큰 수 라고 힌트를 주더라고요.

이번 정렬 문제도 저는 여러번의 시행착오를 겪으며 문제를 풀었답니다!! 첫 번째 시행착오는 마찬가지로 부끄러우니까 접어둘게요 :)

접근 방식

---

저는 서로 다른 크기의 두 숫자를 어떻게 비교해야할까 고민하고 있었습니다. 다음은 제가 시도했던 방법들 입니다.

1. String을 char array로 변환해서 순차적으로 비교를 해 나간다. 만약 987와 98, 988이 있다면 98, 988, 987 순서로 정렬되도록 한다. (비교되는 숫자가 같다가 짧은 배열이 끝나면 짧은 수가 앞으로 정렬된다.)

2. 두 수의 자리수를 비교하여 작은 수에 동일한 숫자가 되도록 10을 자릿수 차만큼 곱해준다. 그리고 수를 비교한다.

 하지만 실패했습니다! 그리고 수가 클수록 계속 for문을 돌아서 그런지 출력 크기 초과가 떠요!! ㅜㅜ

문제 해결

---

사실은 문제에 모두 힌트가 있었습니다!! 바로 문자열과 순서를 재배치하여 라는 말이었죠. 첫 번째 시행착오에서 저는 값을 비교할 수는 있었지만, 제한 사항에 나타난 것처럼 숫자를 키워서 계속 비교를 시도했기 때문에 출력 초과 오류가 발생했었습니다. 그래서 두 번째 방법은, 비교해서 정렬을 하되, "문자열로 합쳐 비교하여 재배치"를 진행하는 방법입니다.

1. 주어진 numbers 배열을 정렬한다. 정렬 방식은 다음과 같다.

1.1 첫 번째 정수값($0)과 두 번째 정수값($1)을 String으로 변환시킨다음 두 String을 붙여 하나의 문자열을 만들어 낸다. 

1.2 첫 번째 정수값을 먼저 배치한 경우와 두 번째 정수값을 먼저 배치한 경우 중 Int로 변환했을 때 어느 값이 더 큰지 비교하여 정렬한다. 예를 들어 0과 9 값이 있다면 "09" 와 "90"을 만들어 Int 로 변환한 뒤 값을 비교한다. 9와 90 중 90이 더 크기 때문에 0이 9의 뒤로 정렬되게 된다.

2. 정렬된 배열의 첫 번째 값이 0인지 확인하여 0 일 경우 "0"을 출력한다. 

- 정렬한 첫 번째 값이 0이라는 것은 모든 배열의 값이 0 일 경우를 의미하게 된다. [0,0,0,0] 이 주어졌을 때 그대로 값을 붙여서 return 하면 "0"이 아니라 "0000" 이 출력되기 때문에 올바르지 않게 된다. 

3. 정렬된 배열의 값을 하나씩 꺼내서 하나의 문자열로 합친(reduce) 결과값을 반환한다.

작성된 코드는 다음과 같습니다.

채점결과는 이러합니다.

여기까지, caution 이였습니다!

주의하세요 :)!