99클럽 코테 스터디 11일차 TIL /[프로그래머스]가장 큰 수

💡문제

[level 2] 가장 큰 수 - 42746

문제 링크

성능 요약

메모리: 124 MB, 시간: 215.48 ms

 

---

🤔접근법

문제 요약

• 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 문제

범위 체크 및 시간복잡도 예상

• numbers의 길이는 1 이상 100,000 이하
• numbers의 원소는 0 이상 1,000 이하

풀이법

⭕ 접근 방법. 우선순위 큐

🔑 PriorityQueue를 사용하자!

static PriorityQueue<Integer> *pq* = new PriorityQueue<>((o1, o2) -> {return o2-o1;});

위와 같이 PQ를 사용하여 우선순위 조건을 변경하면 큰 값이 우선이 되도록 qp를 생성할 수 있다.

pq 는 힙으로 구성되어 있기 때문에 시간복잡도는 O(logN)을 가진다.

➡️ 해당 풀이법의 시간 복잡도 : $O(NlogN)$

 

---

 

🤯FAIL

답을 봐서 문제를 푼 경우

- 두 문자열을 더해서 길이를 같게 만든 후에 우선순위를 비교한다는 아이디어를 떠올리지 못하였다 🤦‍♀️

 

---

👩‍💻 코드

import java.util.*;

class Solution {
        public String solution(int[] numbers) {
            String nums[] = new String[numbers.length];
            for (int i = 0; i < numbers.length; i++) {
                nums[i] = String.valueOf(numbers[i]);
            }

            Arrays.sort(nums,(o1, o2) -> {
                String s1 = o1 + o2;
                String s2 = o2 + o1;
                return s2.compareTo(s1);
            });

//            System.out.println(Arrays.toString(nums));

            StringBuilder answer = new StringBuilder();
            for (int i = 0; i < nums.length; i++) {
                if(i == 0 && nums[0].equals("0")) return "0";
                answer.append(nums[i]);
            }
            return answer.toString();
        }
}

99클럽 코딩테스트 준비 개발자 취업 항해99 TIL