문제 출처
문제 출처 : 숫자 짝궁
문제 이해하기
두 정수 x,y가 주어졌을 때 임의의 자리에서 공통으로 나타나는 정수들을 이용해서 만들 수 있는 가장 큰 정수를 두 수의 짝궁이라고 한다. 더 쉽게 이야기하면 문자열 형태로 주어진 두 정수에 존재하는 수를 추출해서 가장 큰 수를 만들어야 하는 문제이다.
주요 조건 이해하기 ⭐️
이 문제에 제한사항은 굉장히 친절하게 잘 되어있어서 크게 고려할만한 사항이 존재하지 않는다.
어떤 방법으로 풀지 고민해보자, 잘 관찰을 해보면 두 정수에서 공통적으로 나오는 숫자를 카운팅 해준 후 큰 숫자로 만들어주면 끝나는 문제이다.
관찰결과 대략 4가지 방법으로 풀 수 있다고 생각하여 하나씩 접근해봤다.
- x, y 각각 HashMap을 이용해 숫자를 key 빈도수를 value로 잡고 서로 빈도수가 같다면 공통으로 나타난다.
- x = 5525, y = 1255인 경우에 반례가 존재한다.
- 1번과 동일하지만 하나의 HashMap을 이용해 서로의 빈도수를 합친다.
- x = 100, y = 2345인 경우에 반례가 존재한다.
- 2번에 연장으로 value 값이 2이상인 key만 별도로 추출한 후 탐색, key값을 가져온 후 value - 2 값으로 갱신
- 이때 탈출 조건은 value가 1 or 0일 때까지
- 마찬가지로 반례가 존재한다. x = 100, y = 2345 일 때 3번 방법으로 풀면 0이 출력된다.
- 0 ~ 9까지의 빈도수를 저장하는 배열을 2개 생성하여 각각 빈도수를 체크한 후 배열을 순회하면서 두 개의 배열에 공통적으로 가지고 있는 원소를 구한다.
- 1 ~ 3번 풀이로 접근했을 때 보다 더 높은 확률로 정답을 구할 수 있을 것 같다.
풀이 순서는 다음과 같다.
- 입력으로 들어오는 문자열 X, Y의 숫자 하나 하나를 xArr, yArr 인덱스에 빈도수를 체크한다.
- xArr, yArr 순회하면서 둘 다 공통적으로 가지고 있는 원소를 StringBuilder에 append 한다.
- 이 때 조건으로 배열 x, y의 원소 둘다 0이거나, 둘 중 하나라도 1이상인 경우는 공통으로 나타나는 정수가 아니다.
- 완성된 StringBuilder를 조건에 맞게 출력한다.
제출 코드
class Solution {
StringBuilder sb = new StringBuilder();
int[] xArr = new int[10];
int[] yArr = new int[10];
/*
* 입력으로 들어오는 문자열 X, Y의 숫자 하나 하나를 xArr, yArr 인덱스에 빈도수를 체크하는 메소드
*/
private void countFrequency(String X, String Y) {
for (int i = 0; i < X.length(); i++) {
int element = Integer.parseInt(String.valueOf(X.charAt(i)));
xArr[element] += 1;
}
for (int i = 0; i < Y.length(); i++) {
int element = Integer.parseInt(String.valueOf(Y.charAt(i)));
yArr[element] += 1;
}
}
/*
* xArr, yArr 순회하면서 둘 다 공통적으로 가지고 있는 원소를 StringBuilder에 append 하는 메소드
*/
private void findCommonCharacters() {
for (int i = 0; i < 10; i++) {
/* 배열 x, y의 원소 둘다 0이거나, 둘 중 하나라도 1이상인 경우는 공통으로 나타나는 정수가 아님 */
while ((xArr[i] != 0 || yArr[i] != 0) && (xArr[i] != 0 || yArr[i] < 1) && (xArr[i] < 1 || yArr[i] != 0)) {
sb.append(i);
xArr[i] -= 1;
yArr[i] -= 1;
}
}
}
/*
* StringBuilder의 결과를 출력하는 메소드
*/
private String printAnswer() {
String answer = sb.reverse().toString();
if (answer.equals("")) {
return "-1";
}
if (answer.startsWith("0")) {
return "0";
}
return answer;
}
public String solution(String X, String Y) {
countFrequency(X, Y);
findCommonCharacters();
return printAnswer();
}
}