링크
https://school.programmers.co.kr/learn/courses/30/lessons/131128
문제 설명
(정답률 56%)
두 정수 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 함수를 완성해주세요.
입출력 예제
| X | Y | result |
|---|---|---|
| "100" | "2345" | "-1" |
| "100" | "203045" | "0" |
| "100" | "123450" | "10" |
| "12321" | "42531" | "321" |
| "5525" | "1255" | "552" |
나의 코드
import java.util.*;
import java.util.stream.Collectors;
class Solution {
public String solution(String X, String Y) {
ArrayList<Character> list = new ArrayList<>();
HashMap<Character, Integer> mapX = new HashMap<>();
HashMap<Character, Integer> mapY = new HashMap<>();
//HashMap에 X와 Y 문자열의 각 문자의 수를 카운트해서 저장한다
//getOrDefault 메서드를 이용해 중복된 값을 구분하여 카운트
//ex) mapX = {2=1, 5=3}, mapY = {1=1, 2=1, 5=2}
for (int i = 0; i < X.length(); i++) {
mapX.put(X.charAt(i), mapX.getOrDefault(X.charAt(i), 0) + 1);
}
for (int j = 0; j < Y.length(); j++) {
mapY.put(Y.charAt(j), mapY.getOrDefault(Y.charAt(j), 0) + 1);
}
//mapX와 mapY의 키 값을 비교
//키 값이 같은 경우 list에 키 값을 작은 value 값만큼 반복해서 추가한다
//반복 횟수는 삼항 연산자를 이용하여 작은 value 값을 결정
for (Character x : mapX.keySet()) {
for (Character y : mapY.keySet()) {
if (x == y) {
for (int i = 0; i < (mapX.get(x) > mapY.get(x) ?
mapY.get(x) : mapX.get(x)); i++) {
list.add(x);
}
}
}
}
//가장 큰 수를 만들어야 하므로 list를 내림차순으로 정렬
list.sort(Collections.reverseOrder());
//StringBuilder 객체를 생성해 list 원소값을 String 클래스로 변환한다
//stream을 사용하여 list를 String 객체로 생성할 수도 있다
//코드는 한 줄로 간단해 지지만 속도는 느려진다
//String answer = list.stream().
// map(String::valueOf).
// collect(Collectors.joining());
StringBuilder answer = new StringBuilder();
for (Character c : list)
answer.append(c);
if (answer.length() == 0)
return "-1";
//list가 0으로만 구성될 경우 Character 타입이기 때문에
//따로 하나의 문자열 0으로 반환
if (list.get(0).equals('0'))
return "0";
return answer.toString();
}
}다른 사람의 풀이
class Solution {
public String solution(String X, String Y) {
StringBuilder answer = new StringBuilder();
int[] x = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int[] y = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//배열을 사용하여 주어진 문자열의 갯수를 카운트
for (int i = 0; i < X.length(); i++){
x[X.charAt(i) - 48] += 1;
}
for(int i= 0; i < Y.length(); i++){
y[Y.charAt(i) - 48] += 1;
}
//같은 문자를 추가할 횟수를 min 메서드를 이용하였다
for (int i = 9; i >= 0; i--){
for (int j = 0; j < Math.min(x[i], y[i]); j++){
answer.append(i);
}
}
if ("".equals(answer.toString())){
return "-1";
} else if (answer.toString().charAt(0) == 48){
return "0";
} else {
return answer.toString();
}
}
}정리
마냥 간단히 풀리지는 않았다.
처음에는 이중for문으로 두 문자열을 비교하여 같으면 List에 추가하고
List에 이미 문자가 있을시 continue 하는 식으로 했는데
중복된 문자의 반복횟수가 두 문자열 중 적은 경우를 기준으로 했어야 했기 때문에 통과가 되지 않았다.
그래서 다시 숫자의 횟수를 카운트하기 위해 HashMap 객체를 각각 생성하였다.
반복 횟수는 getOrDefault 메서드를 이용하여 결정하였다.
추천 수가 높은 풀이를 보니 참 아이디어가 좋은거 같다..
숫자 카운트를 그냥 배열을 사용했고
특히 answer에 추가하는 과정이 신박했다.
for (int i = 9; i >= 0; i--){
for(int j = 0; j < Math.min(x[i], y[i]); j++){
answer.append(i);
}
}바깥 for문은 i = 9부터 줄여나가서 따로 내림차순으로 정렬 할 필요도 없고
반복 횟수는 그냥 min메서드로 최솟값으로 구했다..
