⚠️JAVA 언어를 사용합니다.
🔒문제
두 정수 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 함수를 완성해주세요.
제한사항
- 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
- X, Y는 0으로 시작하지 않습니다.
- X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.
입출력 예
| X | Y | result |
| "100" | "2345" | "-1" |
| "100" | "203045" | "0" |
| "100" | "123450" | "10" |
| "12321" | "42531" | "321" |
| "5525" | "1255" | "552" |
🗝️정답
class Solution {
public String solution(String X, String Y) {
StringBuffer answer = new StringBuffer("");
int[] x = {0,0,0,0,0,0,0,0,0,0};
int[] y = {0,0,0,0,0,0,0,0,0,0};
boolean[] key = {true, true};
for(int i=0; i<X.length() || i<Y.length(); i++){
if(i<X.length())
x[X.charAt(i)-'0']++;
if(i<Y.length())
y[Y.charAt(i)-'0']++;
}
for(int i=9; i>=0; i--){
if(x[i]!=0 && y[i]!=0){
key[0] = false;
for(int j=0; j<x[i] && j<y[i]; j++){
answer.append(i);
}
if(i!=0) key[1] = false;
}
}
if(key[0]){
answer.append(-1);
}else if(key[1]){
answer = new StringBuffer("0");
}
return answer.toString();
}
}
💡풀이해석
- 숫자 0-9까지의 갯수를 파악해야 하므로, 10사이즈의 배열을 두개(X,Y) 만들어서 각자 카운팅한다.
- 카운팅된 갯수가 둘 다 0이 아니면 그 수를 저장한다. 이때 둘 중 더 작은 수가 서로 중복되는 갯수이므로 작은 수 만큼만 반복한다.
// 선언 및 초기화
- int[] x, int[] y : 카운팅을 위한 두 변수 생성
- boolean[] key : 마지막에 사용된다. 인덱스 0은 같은 수가 하나도 없는지 판단, 인덱스 1은 같은 수가 모두 0인지 판단
// 각 숫자 카운트
- for(int i=0; i<X.length() || i<Y.length(); i++) : 둘 다 끝나야 반복문이 종료된다. 길이가 다를 수 있기 때문에 설정
- 주어진 숫자에 해당하는 인덱스를 하나씩 증가해주면 된다.
// X와 Y에서 같은 수 판단
- for(int i=9; i>=0; i--) : 만들 수 있는 가장 큰 수를 반환해야 하므로 큰 수부터 판단하여 문자열에 넣는다.
- if(x[i]!=0 && y[i]!=0) : 둘 다 0이 아니라면 둘이 같은 수를 가지는 것이므로 key[0]을 바꿔주고, 몇 번 중복되는지 확인하여 문자열에 추가한다.
- if(i!=0) : 이 때 0이 아닌 수가 담기는 것이라면 숫자 0만 반복되는 일이 없으므로 두번째 키값(key[1])을 바꿔준다.
// 문자열 정리
- if(key[0]) : true라면 같은 수가 하나도 없으므로 -1 반환
- else if(key[1]) : true라면 0만 반복된 문자열 이므로 0 중복 제거
채점 결과
✏️자기 분석
숫자가 0-9까지만 있는 것을 고려하여 배열을 만드는걸 생각해내지 못했다.
방향을 카운팅이 아니라 직접 비교하는 쪽으로 잡아서 시간이 오래 걸렸다.
첫 번째 풀이
import java.util.*;
class Solution {
public String solution(String X, String Y) {
StringBuffer answer = new StringBuffer("");
ArrayList<String> same = new ArrayList<>();
String lon = X, shor = Y;
if(X.length()-Y.length()<0){
lon = Y;
shor = X;
}
String[] ch = shor.split("");
for(int i=0; i<shor.length(); i++){
if(lon.contains(ch[i])){
lon = lon.replaceFirst(ch[i]," ");
same.add(ch[i]);
}
}
Collections.sort(same, Collections.reverseOrder());
if(same.size()==0){
answer.append("-1");
}else if(same.get(0).equals("0")){
answer.append("0");
}else{
for(int i=0; i<same.size(); i++){
answer.append(same.get(i));
}
}
return answer.toString();
}
}- 더 짧은 문자열을 큰 문자열과 하나씩 대조하며 같은 수를 찾는다.
- 찾는 방식은 작은 문자열을 하나씩 잘라 배열로 저장하고 배열의 값이 큰 문자열에 있으면 문자열에서 그 수 즉, 문자를 하나만 제거하고, 그 값을 list에 저장한다.
- 리스트를 내림차순으로 정렬하여 문자열로 변환한다.
replaceAll()도 많이 사용되고, 과정에 필요한 로직이 많아서 시간 초과에 걸렸다.
두 번째 풀이
import java.util.*;
class Solution {
public String solution(String X, String Y) {
StringBuffer answer = new StringBuffer("");
ArrayList<Character> same = new ArrayList<>();
char[] x = X.toCharArray();
char[] y = Y.toCharArray();
Arrays.sort(x);
Arrays.sort(y);
for(int i=0, j=0; i<x.length && j<y.length; i++){
if(x[i]<y[j]) continue;
while(j<y.length){
if(x[i] != y[j])
j++;
else{
same.add(x[i]);
j++;
break;
}
}
}
Collections.sort(same, Collections.reverseOrder());
if(same.size()==0){
answer.append("-1");
}else if(same.get(0)=='0'){
answer.append("0");
}else{
for(int i=0; i<same.size(); i++){
answer.append(same.get(i));
}
}
return answer.toString();
}
}이번엔 둘 다 배열로 접근해 보았다. 두 문자열(배열)을 정렬하고 X를 중심으로 하나씩 비교하는데, X의 비교 값이 Y의 현재 비교값 보다 크거나 같을 때만 Y를 다음 순서로 넘긴다. 이건 말로 설명해놓기 어려운 것 같다. 나중에 궁금하면 직접 돌려보자..
어쨋든 이것도 실패했다. 이거는 진짜 왜 실패한건지 아직도 모르겠다.(문제 푼지 4시간 지남)
세 번째 풀이(정답)
import java.util.*;
class Solution {
public String solution(String X, String Y) {
StringBuffer answer = new StringBuffer("");
int[] x = {0,0,0,0,0,0,0,0,0,0};
int[] y = {0,0,0,0,0,0,0,0,0,0};
char[] xchar = X.toCharArray();
char[] ychar = Y.toCharArray();
boolean[] key = {true, true};
for(int i=0; i<xchar.length || i<ychar.length; i++){
if(i<xchar.length)
x[xchar[i]-'0']++;
if(i<ychar.length)
y[ychar[i]-'0']++;
}
for(int i=9; i>=0; i--){
if(x[i]!=0 && y[i]!=0){
key[0] = false;
for(int j=0; j<x[i] && j<y[i]; j++){
answer.append(i);
}
if(i!=0) key[1] = false;
}
}
if(key[0]){
answer.append(-1);
}else if(key[1]){
answer = new StringBuffer("0");
}
return answer.toString();
}
}두 번째 풀이 이후 도저히 안되겠다 싶어서 질문을 보았고, 다룰 데이터의 범위가 0-9이기 때문에 메모리를 많이 차지하지 않는 배열을 선택하여 카운트 한 것을 보고 바로 적용해 보았다.
이 코드는 정답이랑 같은 코드이다. 두 문자열을 문자 배열로 먼저 만들어 놓느냐, 증가시킬 때마다 메소드를 사용해서 문자를 가져오느냐 차이이다.
전부터 차이가 궁금했는데, 크게 차이가 있진 않아 보인다.
🚩결론
1. 접근은 신박하고 좋았으나 효율적이진 못했다.
2. 역시나 오늘 푼 문제들은 문자열과 관련하여 시간복잡도를 고려하지 않았다. 다음부터 신경쓰자.
