프로그래머스. 가장 큰 수

티스토리 뷰

tose33 2021. 9. 28. 15:46

코딩테스트 연습 - 가장 큰 수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰

programmers.co.kr

이 문제는 처음에 순열을 만들어서 때려박는 브루트포스로 풀었다가 시간초과가 났다.

벡터의 길이는 10만까지 가능하고, 문자열인 원소 하나의 길이는 4자리까지 가능하므로 생각해보면 당연히 브루트포스로 안되는데, 백준과 다르게 처음에 시간제한이 안써있다보니 시간을 고려안하고 풀어버렸다.

다음으로 생각한건 그리디 방법으로 앞자리부터 비교해서 정렬하는 방법이다.

그런데 이방법은 자릿수가 다를때 처리방법을 애를 먹었는데

결론적으로 두 문자열 a,b를 a+b한 문자열과 b+a한 문자열을 비교하면 된다.

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함