문제 설명
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.
내가 작성한 코드
시간 초과
import java.util.Stack;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public String solution(String X, String Y) {
Stack<Character> stackA = new Stack<>();
Stack<Character> stackB = new Stack<>();
List<Character> answerList = new ArrayList<>();
// 1. X,Y를 int 배열로 변환
char[] XArr = X.toCharArray();
char[] YArr = Y.toCharArray();
// 2. X, Y를 하나씩 분리하여 Stack에 넣기, 이때 더 자릿수가 긴 String을 stackA에 넣기
if(X.length() >= Y.length()){
for(char xChar : XArr){
stackA.push(xChar);
}
for(char yChar : YArr){
stackB.push(yChar);
}
}else{
for(char xChar : XArr){
stackB.push(xChar);
}
for(char yChar : YArr){
stackA.push(yChar);
}
}
// 3. stackA의 값을 stackB에 있는지 확인 후 pop()하여 answerList에 넣기
while (!stackA.isEmpty()) {
char a = stackA.pop();
if (stackB.contains(a)) {
answerList.add(a);
stackB.remove(Character.valueOf(a));
}
}
// 4. answerList를 큰 값부터 정렬
Collections.sort(answerList, Collections.reverseOrder());
// 5. 정답을 StringBuilder 사용하여 String으로 변환하여 리턴
if (answerList.isEmpty()) {
return "-1";
} else {
StringBuilder sb = new StringBuilder();
for (char ch : answerList) {
sb.append(ch);
}
// "0"만으로 이루어진 경우 "0" 반환
if (sb.toString().matches("0+")) {
return "0";
}
return sb.toString();
}
}
}테스트 1 〉 통과 (0.44ms, 74.4MB)
테스트 2 〉 통과 (0.45ms, 75.1MB)
테스트 3 〉 통과 (0.66ms, 74.2MB)
테스트 4 〉 통과 (0.47ms, 71.3MB)
테스트 5 〉 통과 (1.01ms, 72.8MB)
테스트 6 〉 통과 (3.61ms, 75.6MB)
테스트 7 〉 통과 (2.64ms, 66.4MB)
테스트 8 〉 통과 (3.93ms, 73.5MB)
테스트 9 〉 통과 (3.10ms, 75.2MB)
테스트 10 〉 통과 (4.56ms, 77.6MB)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 실패 (시간 초과)
테스트 14 〉 실패 (시간 초과)
테스트 15 〉 실패 (시간 초과)
테스트 16 〉 통과 (0.54ms, 74.5MB)
테스트 17 〉 통과 (0.60ms, 70.3MB)
테스트 18 〉 통과 (0.61ms, 73.2MB)
테스트 19 〉 통과 (0.67ms, 76.7MB)원인
Stack을 활용한 문자 비교와 삭제는 시간 복잡도가 높다
contains와 remove의 높은 시간 복잡도
- 스택에서 특정 문자를 찾고 제거하는 작업이 반복되면서 시간 복잡도가 증가합니다. 각 연산이 O(n) 시간이 소요되므로 전체 시간 복잡도가 O(n^2)으로 증가합니다.
LIFO 특성의 부적절성
스택의 LIFO 특성으로 인해 두 스택의 비교와 제거가 비효율적으로 수행됩니다.
해결 방안
다른 콜렉션 타입을 사용해보자.. List? Map?
해시맵 vs 리스트
1) 시간 복잡도
HashMap: 키-값 쌍으로 데이터를 저장하며, 특정 키에 대한 값을 조회하거나 삽입할 때 평균 O(1)의 시간 복잡도
List: 특정 값을 찾기 위해 리스트 전체를 순회해야 하므로, 조회와 삽입이 O(n)의 시간 복잡도를 가집니다.
2) 빈도 계산
HashMap: 문자의 빈도를 쉽게 계산할 수 있습니다.
예를 들어, countX.put(x, countX.getOrDefault(x, 0) + 1)는 특정 문자의 빈도를 간단히 증가시킵니다.
List: 빈도를 계산하려면 리스트를 순회하면서 각 문자의 빈도를 수동으로 세야 합니다. 이는 비효율적입니다.
3) 중복 처리
HashMap: 중복된 문자를 키로 하여 빈도수를 값으로 저장합니다. 중복된 문자를 쉽게 처리할 수 있습니다.
List: 중복된 문자를 처리하려면 리스트의 각 요소를 개별적으로 관리해야 합니다. 이는 더 많은 코드와 복잡성을 요구합니다.
4) 공통 문자 찾기
HashMap: 두 해시맵을 비교하여 공통된 문자를 찾고, 빈도수를 쉽게 조정할 수 있습니다.
List: 두 리스트를 비교하여 공통된 문자를 찾으려면, 중첩 루프를 사용하여 각 요소를 비교해야 합니다. 이는 시간 복잡도가 O(n^2)로 증가합니다.
다른 사람이 작성한 코드
StringBuilder 사용
class Solution {
public String solution(String X, String Y) {
// 결과를 저장할 StringBuilder
StringBuilder sb = new StringBuilder();
// 각 숫자의 빈도를 저장할 배열
int[] x = new int[10];
int[] y = new int[10];
// X 문자열에서 각 숫자의 빈도를 세어 x 배열에 저장
// - '0'은 char > int 역할을 함
for (int i = 0; i < X.length(); i++) {
x[X.charAt(i) - '0']++;
}
// Y 문자열에서 각 숫자의 빈도를 세어 y 배열에 저장
for (int i = 0; i < Y.length(); i++) {
y[Y.charAt(i) - '0']++;
}
// 9부터 0까지 숫자를 비교하여 공통으로 존재하는 숫자를 StringBuilder에 추가
for (int i = 9; i >= 0; i--) {
int count = Math.min(x[i], y[i]);
for (int j = 0; j < count; j++) {
sb.append(i);
}
}
// 공통 숫자가 없다면 -1 반환
if (sb.length() == 0) {
return "-1";
}
// 결과가 0으로만 이루어져 있다면 0 반환
// 이 과정 없으면 '0000' 형식으로 리턴 된다.
else if (sb.charAt(0) == '0') {
return "0";
}
// 결과 문자열 반환
return sb.toString();
}
}0.04~ 61.22ms 대로 가장 짧은 시간을 기록했다.
int count = Math.min(x[i], y[i]);을 사용하여 둘의 빈도 중에 더 작은 쪽, 즉 공통되게 중복된 숫자를 저장한다.
HashMap 사용
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
class Solution {
public String solution(String X, String Y) {
Map<Character, Integer> countX = new HashMap<>();
Map<Character, Integer> countY = new HashMap<>();
// X에 있는 각 숫자의 빈도수를 계산
for (char x : X.toCharArray()) {
countX.put(x, countX.getOrDefault(x, 0) + 1);
}
// Y에 있는 각 숫자의 빈도수를 계산
for (char y : Y.toCharArray()) {
countY.put(y, countY.getOrDefault(y, 0) + 1);
}
// 우선순위 큐를 사용하여 가장 큰 숫자를 형성
PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// 공통 숫자를 찾아 maxHeap에 추가
for (char key : countX.keySet()) {
if (countY.containsKey(key)) {
int commonCount = Math.min(countX.get(key), countY.get(key));
for (int i = 0; i < commonCount; i++) {
maxHeap.add(key);
}
}
}
// 공통 숫자가 없으면 "-1" 반환
if (maxHeap.isEmpty()) {
return "-1";
}
// 가장 큰 숫자가 0이면 "0" 반환
if (maxHeap.peek() == '0' && maxHeap.size() == 1) {
return "0";
}
// 결과 문자열을 생성
StringBuilder result = new StringBuilder();
while (!maxHeap.isEmpty()) {
result.append(maxHeap.poll());
}
return result.toString();
}
}위 코드는 시간 초과가 나왔다...
학습한 내용
Stack의 메소드
char to Character
List 정렬
String to Character
