알고리즘
프로그래머스 - 숫자 짝꿍
계양 꿀주먹
2024. 5. 6. 17:01
import java.util.*;
class Solution {
public String solution(String X, String Y) {
List<Character> listX = new ArrayList<>();
List<Character> listY = new ArrayList<>();
List<Integer> couple = new ArrayList<>();
StringBuilder sb = new StringBuilder();
for(char c : X.toCharArray()) listX.add(c);
for(char c : Y.toCharArray()) listY.add(c);
for(int i = 0; i < listX.size(); i++) {
for(int j = 0; j < listY.size(); j++) {
if(listX.get(i) == listY.get(j)) {
couple.add(listY.get(j) - '0'); // 같은 짝꿍이 있다면, 짝궁 리스트에 추가
listY.remove(j); // 비교 리스트에서 삭제
}
}
}
// 겹치는 수가 없을 때
if(couple.size() == 0) return "-1";
Collections.sort(couple);
Collections.reverse(couple); // 내림차순으로 정렬
// 내림차순 정렬 후, 처음으로 오는 수가 0 일 때 -> 모든 수가 0
if(couple.get(0) == 0) return "0";
for(int c : couple) sb.append(c);
return sb.toString();
}
}
문제를 처음 시도했을 때의 코드입니다.
3,000,000 까지의 자리수가 있지만 생각없이 2중 for문을 사용하여.. 시간 초과가 났었습니다.
개선 전 시간
import java.util.*;
class Solution {
public String solution(String X, String Y) {
HashMap<Integer, Integer> mapX = new HashMap<>();
HashMap<Integer, Integer> mapY = new HashMap<>();
StringBuilder couple = new StringBuilder();
// 0 ~ 9 초기화
for(int i = 0; i < 10; i++) {
mapX.put(i, -1);
mapY.put(i, -1);
}
// X, Y가 갖고 있는 수 체크
for(char c : X.toCharArray()) mapX.put(c - '0', mapX.getOrDefault(c - '0', 0) + 1);
for(char c : Y.toCharArray()) mapY.put(c - '0', mapY.getOrDefault(c - '0', 0) + 1);
// X, Y 비교하여 List 추가
for(int i = 0; i < 10; i++) {
for(int j = 0; j <= (Math.min(mapX.get(i), mapY.get(i))); j++) {
couple.append(i);
}
}
if(couple.toString().equals("")) return "-1";
if(couple.toString().endsWith("0")) return "0";
return couple.reverse().toString();
}
}
코드를 개선하여 map을 사용해 X, Y에서 각각 0 ~ 9 가 몇 개 있는지 갯수를 구하고, 둘 중 비교하여 작은 수만큼 같은 숫자를 공유하는 것이기 때문에 작은 숫자를 구해 StringBuilder를 이용해 0부터 시작하는 문자열을 만들었고, 뒤집어서 가장 큰 수로 만들어주었습니다.
각 조건에 맞춰 겹치는 숫자가 없으면 -1, 또한 겹치는 숫자가 0으로만 이루어져 있다면 00000 이 있을 수 있는데 만약 9120 처럼 마지막이 0으로 끝날 수 있기 때문에 뒤집기 전에 마지막이 0으로 끝나는지 확인하여 0으로 시작하는 문자열인 경우 0을 반환하도록 했습니다.
개선 후 시간
시간 초과 이외에도 전체적인 시간 소요가 절반정도 줄었습니다.