두 정수 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 함수를 완성해주세요.
문제를 보자 마자 들은 생각은
parameter 의 최댓값이 3만이라 for 문을 사용한다면
최대 3만 x 3만 번을 반복해야되기 때문에
효율이 너무 안좋을것 같아서 배열을 비교하는 식으로 해야겠다고 생각했다.
index 자리가 픽스되있지 않은 array list 를 사용해
0 번 요소만 비교하는 방법이 떠올랐다.
public static void main(String[] args) {
String X = "5525";
String Y = "1255";
String answer = "";
//--------------------------------------------//
// 주어진 변수를 char 배열로 변경
char[] x1 = X.toCharArray();
char [] y1 = Y.toCharArray();
// 배열을 정렬해줌
Arrays.sort(x1);
Arrays.sort(y1);
// 배열을 array list 에 넣어줌
ArrayList <Character> x2 = new ArrayList<>();
ArrayList <Character> y2 = new ArrayList<>();
for (char i : x1){ x2.add(i); }
for (char i : y1){ y2.add(i); }
// array list 를 오름차순으로 바꿔줌
Collections.reverse(x2);
Collections.reverse(y2);
// 0번 요소가 동일할경우 answer 에 값 넣고
// 0번 요소 삭제
while (x2.size() >0 && y2.size() > 0){
if (x2.get(0)==y2.get(0)){
answer += x2.get(0);
x2.remove(0);
y2.remove(0);
// 0번 요소가 다를 경우 큰쪽을 삭제
}else if(x2.get(0) > y2.get(0)){
x2.remove(0);
}else {
y2.remove(0);
}
}
// answer 값이 없거나 0 일경우 값 변경
if (answer == ""){
answer = "-1";
} else if (answer.charAt(0)=='0') {
answer = "0";
}
System.out.println(answer);
처음 생각했던 대로 계산하는데 걸리는 시간이 문제였다...
나름 고려해서 최대한 효율적으로 만든다고 했는데 아직 많이 비효율 적인가보다 ㅜㅜ
이전 코드를 다시 리뷰해보니
변수 -> 배열 -> array list
배열이 쓰잘때기 없이 껴있었다.
배열 없이 바로 array list 에서 값을 추출하게 코드를 수정했다.
//--------------------------------------------//
// 주어진 변수를 바로 array list 변경
ArrayList <Character> x = new ArrayList<>();
ArrayList <Character> y = new ArrayList<>();
for(int i=0 ; i<X.length() || i<Y.length() ; i++){
if(i < X.length()) x.add(X.charAt(i));
if(i < Y.length()) y.add(Y.charAt(i));
}
// 내림 차순으로
Collections.sort(x,Collections.reverseOrder());
Collections.sort(y,Collections.reverseOrder());
// 0번 요소가 동일할경우 answer 에 값 넣고
// 0번 요소 삭제
while (x.size() >0 && y.size() > 0){
if (x.get(0)==y.get(0)){
answer += x.get(0);
x.remove(0);
y.remove(0);
// 0번 요소가 다를 경우 큰쪽을 삭제
}else if(x.get(0) > y.get(0)){
x.remove(0);
}else {
y.remove(0);
}
}
// answer 값이 없거나 0 일경우 값 변경
if (answer == ""){
answer = "-1";
} else if (answer.charAt(0)=='0') {
answer = "0";
}
System.out.println(answer);
뭔가 더 빨라진것같은 느낌이 있긴한데 똑같이 시간 초과가 난다 ㅜㅜ
아무래도 코드에 근본적인 문제가 있는것같다..
더 근본적인 해결책을 찾기위해 고민하다 도저히 아이디어가 떠오르지 않아서
다른사람들이 질문한걸 슬쩍봤다.
해결한 사람들의 힌트를 보니 배열 정렬을 통한 풀이는 통과하기 어렵다고 한다.
사람들의 흰트를 참고해 이번엔 Parameter 의 숫자가 0~9 중 한가지라는 점을 이용해서 풀어봤다.
먼저 배열에 0~9 까지 들어갈 수 있는 index 를 생성해주고
Parameter 값의 숫자에 해당하는 배열의 index 에 1씩 추가한후 두 배열의 값을 비교하는식으로 접근했다.
public static void main(String[] args) {
String X = "5525";
String Y = "1255";
String answer = "";
//--------------------------------------------//
// parameter 값의 하나 하나가 0~9 까지의 수 라는걸 이용해
// 0~9 에 해당하는 10개의 index 배열 생성
int[] x1 = new int[10];
int[] y1 = new int[10];
// parameter 값을 쪼개 해당하는 숫자의 index에 1씩 추가해줌
for (String i : X.split("")) x1[Integer.parseInt(i)] ++;
for (String i : Y.split("")) y1[Integer.parseInt(i)] ++;
// 두 배열을 마지막칸 (큰 수) 부터 비교해 더 적은 값을 anser 에 추가해줌
// 겹치는 만큼 추가해야되기 때문에 for 문으로 겹치는 만큼 반복
for (int i =9 ; i>=0 ; i--){
if (x1[i] != 0 && y1[i] != 0){
if (x1[i] <= y1[i]) for (int j=0; j<x1[i]; j++) answer += i;
if (x1[i] > y1[i]) for (int j=0; j<y1[i]; j++) answer += i;
}
}
if (answer == ""){
answer = "-1";
} else if (answer.charAt(0)=='0') {
answer = "0";
}
System.out.println(answer);
코드가 눈부시게 줄어들었지만 여전히 시간초과로 실패..
이번엔 map 을 사용해서 풀어봤다..
결과는 똑같았다..
도대체 어느 부분이 잘못된걸까??ㅜㅜ
HashMap <String,Integer> x1 = new HashMap<>();
HashMap <String,Integer> y1 = new HashMap<>();
StringBuilder build = new StringBuilder();
for (String key : X.split(""))
x1.put(key,x1.getOrDefault(key,0)+1);
for (String key : Y.split(""))
y1.put(key,y1.getOrDefault(key,0)+1);
for (String key : x1.keySet()){
if (!y1.containsKey(key)) continue;
for (int i = 0; i < Math.min(y1.get(key), x1.get(key)); i++) {
build.insert(0, key);
}
}
answer = build.toString();answer = build.toString();
if (answer.equals("")) answer = "-1";
if (answer.charAt(0) == '0') answer = "0";
System.out.println(answer);
지금 내 실력으로는 이게 최선인것같다..
문제를 해결한 사람들의 코드 2가지를 찾아봣다.
솔직히 내 코드와 작동 원리가 어느 부분에서 다른지 잘 모르겠다.
나중에 실력을 더 쌓은 후에 리뷰해봐야겟다..
import java.util.*;
import java.util.stream.*;
class Solution {
public String solution(String X, String Y) {
Map<String, Integer> xMap = new HashMap<>();
Map<String, Integer> yMap = new HashMap<>();
List<String> list = new ArrayList<>();
for(String key: X.split("")) {
xMap.put(key, xMap.getOrDefault(key, 0)+1);
}
for(String key: Y.split("")) {
yMap.put(key, yMap.getOrDefault(key, 0)+1);
}
for(String key: xMap.keySet()) {
if(!yMap.containsKey(key)) continue;
int length = Math.min(xMap.get(key), yMap.get(key));
for(int i = 0; i < length; i++) {
list.add(key);
}
}
String result = list.stream()
.sorted(Collections.reverseOrder())
.collect(Collectors.joining());
if(result.isEmpty()) return "-1";
if(result.replaceAll("0", "").isEmpty()) return "0";
return result;
}
}
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;
}
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();
}
}
}
String x = "12345";
char [] y = x.toCharArray();
ArrayList <Character> x = new ArrayList<>();
for (char i : x1) { x.add(i); }
Collections.sort(x); // 오름차순 정렬
Collections.sort(x,Collections.reverseOrder()); // 내림차순 정렬
String x = "010-1234-5678;
String [] y = x.split("-");
// -> [0] : 010
// -> [1] : 1234
// -> [2] : 5678
String [] z = x.split("-",2); //-를 기준으로 index 두개만 만들라는 뜻
// -> [0] : 010
// -> [1] : 1234-5678
String x = "Hello World";
String [] y = x.split(" ");
// -> [0] : Hello
// -> [1] : World