[프로그래머스] 가장 큰 수

monshell·2021년 10월 27일
0

ALGORITHM

목록 보기
10/17

문제 링크

문제 요약

  • 주어진 숫자들을 조합하여 가장 큰 문자열을 만든다

풀이 흐름

  • 1차 흐름
    그냥 숫자 순으로 정렬하면 안된다. [8, 31] 이 있을 때 318 보단 831이 더 크다. 짧은 수가 항상 앞에 오는것도 안된다. [6, 67] 이 있을 때 667 보단 676이 더 크다. 그럼 숫자 A, B가 있을 때 AB와 BA 중에 더 큰 결과를 내는 순서를 찾고 BA가 더 크면 A와 B의 순서를 바꿔준다.
  • 그래서 그냥 손에 익은 정렬인 버블정렬을 사용했더니 시간초과가 난다! 그럼 버블정렬보다 빠른 퀵소트를 사용해볼까 했는데, 퀵소트를 잘 알지 못하다보니 코드 찾다가 시간이 다 가버렸다.
  • 2차 흐름
    풀이를 보니 Java 내 라이브러리를 사용하여 바로 정렬 시켰다.
    Arrays.sort(arr, new Comparator< String >(){
	public int compare(String s1, String s2){
    	return (s2+s1).compareTo(s1+s2);
      }
    });
  • 위 코드에서 sort()의 두번째 자리는 comparator인게 정해져있으니까 new Comparator 생략, Comparator에는 compare 라는 메소드는 하나 뿐이니까 public int compare 생략, 어차피 여기 들어 올 변수는 String인걸 알고있으니 String 선언을 생략, 결국 구현이 한줄 뿐이니까 리턴값 사용하지 않고 바로 내용만 남겨서 람다함수로 수정하면
   Arrays.sort(arr, (s1, s2) -> 
    	(s2+s1).compareTo(s1+s2));
  • arr.charAt(0) 으로 첫 문자열을 꺼내오는 것 보다는
    arr.startsWith("0") 으로 시작 위치를 가져오는 것을 권장.

  • import java.util.stream.*; 를 사용하여 매개변수로 전달되는 int 배열을 String으로 그대로 전달할 수 있다.

   IntStream.of(numbers)
       .mapToObj(n -> String.valueOf(n))

위 코드도 마찬가지로 아래와 같이 축약 가능

   IntStream.of(numbers)
       .mapToObj(String::valueOf)

그리고 위에서 String으로 변환한 문자열을 sort() 한 뒤 하나로 합침

   String answer = IntStream.of(numbers)
       .mapToObj(String::valueOf)
       .sort((s1,s2) -> (s2+s1).compareTo(s1+s2))
       .collect(Collectors.joining())

코드

풀이 언어 : JAVA
<1차>

class Solution {
    public boolean needSwitch(int a, int b) {
		String ab = String.valueOf(a) + String.valueOf(b);
		String ba = String.valueOf(b) + String.valueOf(a);
		
		if(ab.compareTo(ba) > 0)
			return true;
		else
			return false;
	}
	
	public String solution(int[] numbers) {
        String answer = "";
        
        for(int i = numbers.length - 1; i > 0; --i) {
        	for(int j = 0; j < i; ++j) {
        		if(needSwitch(numbers[i],numbers[j])) {
        			int tmp = numbers[i];
        			numbers[i] = numbers[j];
        			numbers[j] = tmp;
        		}
        	}
        }
        
        int sum = 0;
        for(int num : numbers) {
            sum += num;
        	answer += String.valueOf(num);
        }
        if(sum == 0)
            return "0";
        else
            return answer;
    }
}

<2차 (외부 풀이)>

import java.util.stream.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = IntStream.of(numbers)
           .mapToObj(String::valueOf)
           .sort((s1,s2) -> (s2+s1).compareTo(s1+s2))
           .collect(Collectors.joining())
           
        return answer;
    }
}

0개의 댓글