https://school.programmers.co.kr/learn/courses/30/lessons/42746
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이 접근 방법
1. 일의 자리가 가장 큰 값이 앞으로 와야하므로, 그 값을 기준으로 정렬한다.
2. 일의 자리 숫자가 같을 때, compareTo()를 사용하여 나머지 숫자를 비교하고 정렬한다.
3. 일의 자리를 기준으로 오름차순 되어있으므로, 뒤에서 부터 String 결과값에 더해준다.
import java.util.*;
class Solution {
public String solution(int[] numbers) {
String answer = "";
boolean flag = true;
for(int num : numbers) {
if (num != 0) {
flag = false;
break;
}
}
if (flag) return "0";
String [] str = new String[numbers.length];
for(int i = 0; i < str.length; i++) str[i] = String.valueOf(numbers[i]);
Arrays.sort(str, (n1, n2) -> {
if (n1.charAt(0) != n2.charAt(0)) {
return n1.charAt(0) - n2.charAt(0);
}
String s1 = n1 + n2;
String s2 = n2 + n1;
return s1.compareTo(s2);
});
for(int i = str.length - 1; i >= 0; i--) {
answer += str[i];
}
return answer;
}
}
문제풀이 회고
길이가 100,000 이므로 O(N^2)인 로직을 짜면 최악의 경우 100억이 되므로 시간 복잡도를 개선해야한다. O(NlogN)은 길이가 5백만 까지 수용 가능하니 정렬을 사용 가능하다.
문자열 내 마음대로 정렬하기 문제를 풀고 나니 쉬웠다. 그런데, 로직을 비슷하게 짜니
[3, 30, 34, 5, 9]
위 예제가 주어졌을 때 "9534330"이 결과값으로 나와야 했는데 내 로직은 "9534303"이 나왔다.
"3", "30"에서 나올 수 있는 결과쌍인 "330"과 "303"에 대해서 비교가 필요했다.
String s1 = n1 + n2;
String s2 = n2 + n1;
return s1.compareTo(s2);
그래서 두 값을 비교하게 해서 "330"이 올 수 있도록 구현하였다.
Edge Case
모든 테케를 통과했다. 11번 빼고....
힌트를 찾아보니 [0, 0, 0] 처럼 모든 정수가 0인 경우의 수가 있었다. 그래서 코드 처음에 모든 정수가 0이면 바로 0을 return하고, 정수가 하나라도 0이 아니라면 바로 break를 해서 시간복잡도를 줄여보았다.
'Algorithm > 프로그래머스 코딩테스트 문제풀이전략' 카테고리의 다른 글
[프로그래머스] Lv.2 순위 검색 (0) | 2024.05.05 |
---|---|
[프로그래머스] Lv.2 메뉴 리뉴얼 (0) | 2024.05.03 |
[프로그래머스] Lv.2 문자열 내 마음대로 정렬하기 (0) | 2024.05.02 |
[프로그래머스] Lv.1 문자열 내림차순으로 배치하기 (0) | 2024.05.02 |
[프로그래머스] Lv.2 H-index (0) | 2024.05.02 |