문제 설명
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수(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" |
나의 풀이
문제 풀이에 앞서 넣어줘야할 로직에 대해서 생각해봤다. 주어진 부분은 짝꿍 구하기, 짝꿍이 없을 경우, 짝꿍의 원소가 모두 0일 경우 이렇게 세 가지였다.
짝꿍 배열을 구한 뒤에 배열의 원소의 특성에 맞게 예외처리를 해주면 되겠다고 생각했다.
풀이1 (배열 메서드 사용)
function solution(x, y) {
let commonElements = [];
let xArr = x.split('');
let yArr = y.split('');
xArr.forEach((v) => {
if (yArr.includes(v)) {
commonElements.push(v);
yArr.splice(yArr.indexOf(v), 1);
console.log(yArr);
}
});
console.log(commonElements);
if (!commonElements.length) {
return '-1';
}
if (commonElements.every((v) => v === '0')) {
return '0';
}
const answer = commonElements.sort((a, b) => b - a).reduce((prev, curr) => prev + curr, '');
console.log(answer);
return answer;
}
solution('100', '123450');
문제 풀이 같은 경우에는 조회 메서드를 사용했기 때문에 이미 체크하고 지나간 원소에 있어서도 계속 재차 건드리게 되어 공통요소 배열인 commonElement배열이 늘어나 splice를 이용해 이미 체크한 원소에 대해서는 삭제를 해주었다.
위에서 생각했던 대로 풀어봤는데 몇개 정도는 틀리고 5문제 정도는 시간 초과가 떴다. 아마 배열 조회, 수정 메서드를 많이 써서 그런 것 같았다.
따라서 배열을 건드리는 것보다 시간복잡도 측면에서 효율적인 Set을 써보기로 했다.
풀이2 (Set 사용)
function solution(x, y) {
const xSet = new Set(x.split(''));
const commonElements = [];
for (const v of y) {
if (xSet.has(v)) {
commonElements.push(v);
xSet.delete(v);
}
}
if (commonElements.length === 0) {
return '-1';
}
if (commonElements.every((v) => v === '0')) {
return '0';
}
const answer = commonElements.sort((a, b) => b - a).join('');
console.log(answer);
return answer;
}
위의 풀이 1번에서 중복되는 원소를 삭제하는데 조금 더 효율적으로 하기 위해 Set을 써봤다. 그런데 문제가 있었다. Set을 쓰게되면 중복은 없어지지만 모든 중복을 허용하지 않는 것은 아니었기에 주어진 결과와 다른 결과가 나오는 경우가 몇 가지 생기게 되었다. 예를 들어, X가 "100"이고 Y가 "1100"이라고 가정했을 때 commonElement에 1, 0 만 들어가는 것이 아니라 0이 2번 중복되기 때문에 1, 0, 0이 들어가야 했다. 따라서 이런 경우는 Set을 이용해서 만족시켜줄 수 없는 부분이었다.
풀이3 (Map 사용)
function solution(x, y) {
const xMap = new Map();
const commonElements = [];
for (const v of x) {
xMap.set(v, (xMap.get(v) || 0) + 1);
}
for (const v of y) {
if (xMap.has(v) && xMap.get(v) > 0) {
commonElements.push(v);
xMap.set(v, xMap.get(v) - 1);
}
}
if (commonElements.length === 0) {
return '-1';
}
if (commonElements.every((v) => v === '0')) {
return '0';
}
const answer = commonElements.sort((a, b) => b - a).join('');
return answer;
}
마지막으로 Map을 이용해서 문제를 풀어봤다. 기존의 로직과는 동일하되 Map에서의 key값으로는 X배열의 원소를 넣고 vaule값으로는 그 원소가 몇 개나 있는지에 대한 정보를 넣었다. 그렇게 넣은 정보를 가지고 xMap이 배열 Y의 원소를 가지고 있다면 공통원소 배열에 그 원소를 넣고 xMap에 있는 해당 원소의 개수를 1씩 빼주는 식으로 구성했다.
나머지 로직들은 동일하다.
'Algorithm' 카테고리의 다른 글
로또의 최고 순위와 최저 순위 [프로그래머스] (0) | 2023.12.06 |
---|---|
하샤드 수 [프로그래머스] (1) | 2023.11.10 |
모음 제거 [프로그래머스] (3) | 2023.11.10 |
배열의 유사도 [프로그래머스] (1) | 2023.11.09 |
숫자 짝꿍 [프로그래머스] (1) | 2023.11.07 |