programmers.co.kr/learn/courses/30/lessons/42746
코딩테스트 연습 - 가장 큰 수
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰
programmers.co.kr
내림차순 정렬을 풀 수 없는 문제다.
예제에서 [3, 30, 34, 5, 9] 의 경우를 살펴보자
이를 내림차순 해보자 => [34, 30, 9, 5, 3] 답 : 3430953
그렇다면 맨 앞자리부터 순서대로 큰 순서로 정렬을 한다면?
[9, 5, 34, 30, 3] or [9, 5, 34, 3, 30] 이런식으로 나온다.
하지만 30, 3의 경우처럼 정렬하기 애매한 경우가 생긴다.
여기서 생각이 떠오른것이 만약 두수를 이어 붙였을 때 어떤 수가 더 큰가?
30, 3을 가지고 예를 들자면
303 < 330 의 방식이 되므로 이를 통해 문제를 해결하였다.
(사실 이 과정까지 도출하는데 4시간걸림..)
코드
백준에서 비슷한 문제를 발견했다.
난이도는 플레5지만 위의 아이디어를 이용하여 접근하면 쉽게 해결이 가능하다.
문제 링크
1422번: 숫자의 신
첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보
www.acmicpc.net
해설
백준 - 1422번(숫자의 신) / C++
www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에
wizii.tistory.com
'Algorithm' 카테고리의 다른 글
| 프로그래머스 - 키 순서 / C++ (0) | 2021.02.23 |
|---|---|
| 백준 - 1422번(숫자의 신) / C++ (0) | 2021.02.22 |
| 프로그래머스 - Summer/Winter Coding(2019)(멀쩡한 사각형) / C++ (0) | 2020.10.28 |
| 백준 - 17070번(파이프 옮기기 1) / C++ (0) | 2020.08.23 |
| 백준 - 15686번(치킨 배달) / C++ (0) | 2020.07.09 |