프로그래머스 - 가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

 

 

 

 

 

문제

• 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수 구하기

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하
• numbers의 원소는 0 이상 1,000 이하
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return

 

입출력 예시

numbers	return
[6, 10, 2]	[3, 30, 34, 5, 9]
[3, 30, 34, 5, 9]	"9534330"

[6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210

 

 

 

 

 

 

풀이

 예시를 보고 처음 떠오른 풀이는 순열(DFS)로 가능한 모든 경우의 수에 대해 문자를 이어붙어 최댓값을 구하는 것이었다. 하지만 제한 사항을 보면 길이가 최대 100,000로 n!을 하게 된다면 시간초과가 날 것이다.

 

• 내림차순 정렬

 그래서 다른 풀이를 떠올리다가 내림차순으로 정렬한 다음 문자를 이어붙이면 되겠다는 풀이가 떠올랐다. 하지만 내림차순으로 정렬할 때 고려해야 될 것이 있다.

 

입력 예시에서처럼 [3, 30]의 경우, 만들 수 있는 숫자는 "330"과 "303"이다. "330"이 최댓값이 된다. 그냥 내림차순으로 정렬하면 [30, 3]이 될 것이고, 문자열로 만든 수는 "303"이 될 것이다. 최댓값인 "330"이 아니다.

 

최댓값을 구하기 위해 3, 30을 정렬해서 붙인 값이 303이 아니라 330이 되게 하기 위해서는 붙인 문자 값을 비교해 정렬해야 한다.

 

 

 

.sorted((o1, o2) -> (o2 + o1).compareTo(o1 + o2));

람다식에 compareTo 메소드를사용해서 정렬했다.

 

*A.compareTo(B) 메소드 : A와 B를 비교했을 때, A가 크다면 양수, 같으면 0, B가 크면 음수를 반환한다. 따라서 정렬을 하게 되었을 때, 양수라면 오름차순 정렬을 하고, 음수라면 내림차순 정렬을 한다.

 

 

 

 

• Stream API 사용

제한 사항을 보면 정답이 너무 클 수 있으니 문자열로 바꾸어 리턴하라고 하고, 정렬도 해야하니 Stream API를 사용하는 것이 편하겠다고 생각했다.

 

 

 Stream 과정은 크게 3가지로 나뉜다.

 

1. Stream 생성

Arrays.stream(numbers)

 

2. 가공하기

• map으로 데이터 변환

.mapToObj(String::valueOf)

int 형태의 배열을 String 배열으로 변환해준다.

 

• 정렬

.sorted((o1, o2) -> (o2 + o1).compareTo(o1 + o2))

 

붙인 문자값을 비교해 내림차순으로 정렬을 한다.

 

 

3. 결과 만들기

• 데이터 수집(collect)

.collect(Collectors.joining());

정렬된 배열의 원소들을 1개의 String으로 이어붙인다.

 

 

 

• 반례

 제한 사항을 보면 "numbers의 원소는 0 이상 1,000 이하"다. [0, 0, 0]일 경우 결과값은 000이 된다. 하지만 이를 수로 만들었을 때는 0이므로, 000인 경우에는 0으로 반환되게 해야 한다.

 

 

 

 

 

코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = Arrays.stream(numbers) //stream 생성
                        .mapToObj(String::valueOf) //String으로 변환
                        .sorted((o1, o2) -> (o2 + o1).compareTo(o1 + o2)) //내림차순 정렬 : 3 30 34 -> 34 3 30
                        .collect(Collectors.joining()); //문자를 이어붙임
        
        return answer.startsWith("0") ? "0" : answer; //000인 경우는 0으로 반환
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• Stream API
  1. 스트림 생성하기
  2. 가공하기
     1. 필터링(filter)
     2. 데이터 변환(map)
     3. 정렬(sorted)
  3. 결과 만들기
     1. 집계(max, min, sum, count..)
     2. 수집(collect) : list로 반환받기, 1개의 String으로 이어붙이기..

 

 

 

 

 

참고

• Stream 활용한 풀이 : https://school.programmers.co.kr/questions/52623

프로그래머스

• stream 기초1 : https://mangkyu.tistory.com/112

[Java] Stream API에 대한 이해 - (1/5)

• stream 기초2 : https://mangkyu.tistory.com/114

[Java] Stream API의 활용 및 사용법 - 기초 (3/5)