시소 짝꿍 ❓
위 문제는 하루동안 고민했지만 풀지못했다. 질문하기 카테고리에 들어가서 다른 분들의 힌트를 보고 풀게되어 조금은 찜찜하지만 그래도 힌트를 최소한으로 얻고 나머지는 최대한 스스로 생각해보았다. 문제는 다음과 같다.
그냥 시소가 있고 시소가 평행이 될 때가 몇번이나 있는지를 물어보는 문제이다.
weights :[100, 180, 270, 100 ,360] 으로 주어졌다.
사실 그냥 반복문으로 완전탐색으로 풀어보려했다. weights의 길이는 최대 10만으로 n2의 시간 복잡도를 갖는 알고리즘을 사용하면 ?? 100000 * 100000으로 1000억이 넘어간다;;;;;
흠.. 위 주어진 조건으로는 그럼 단순 반복문으로 푸는 문제는 아님을 알 수 있다.
그럼 내가 알고있는 알고리즘 중 한번의 반복으로 문제를 풀 수 있는건 뭐가 있나?
이분탐색, 해시, 투포인터 등이 있다. 그럼 이 문제에 어떤 걸 적용해볼까
해시를 적용하다 ❗️
해시를 사용해서 한 무게마다 가능한 무게를 모두 저장 후 가능한 무게가 겹칠 때 count를 높여주면서 문제를 푸는 것이다.
예를들어 100은 총 1,2,3,4를 곱해준 100,200,300,400이 가능하다
근데 여기서 필자가 발견한 치명적 실수가 있었다..
문제를 다시보면 ?? 시소는 2m 3m 4m의 거리에 자리가 있다는 거
왜 1m의 거리에도 있는 줄 알았을까.. 그렇기 때문에 결국
2M . 3M . 4M의 거리에 놓였을 때 최종 무게를 map에 저장하면서 배열을 순회하며 겹치는 부분은 count++하며 문제를 풀어갈 생각이었다. 코드는 다음과 같다.
첫번째 시도 👀(...실패)
function solution(weights) {
let answer = [];
let saved = new Map();
for (let i = 0; i < weights.length; i++) {
let target = weights[i];
for (let j = 0; j < 4; j++) {
if (saved.get(target) === undefined) {
saved.set(target, [i]);
} else {
saved.get(target).forEach((item) => {
const test = `${String(item)},${String(i)}`;
if (!answer.includes(test)) {
answer.push(test);
}
});
saved.set(target, [...saved.get(target), i]);
}
target = target + weights[i];
}
}
return answer.length;
}결과는 23점
일단 잘못된 점이 크게 2가지가 있다.
첫 번째 시소는 2m. 3m. 4m의 거리에 자리가 있기 때문에 1m의 자리는 배제해주어야한다는 점
두 번째 굳이 saved.set할때 index를 비교하지 않아도 된다는점
아마 이 부분은 중복을 생각해서 index를 비교하고 이미 가능하다고 여겨진 몸무게의 인덱스끼리는 더이상 계산을 하지 않으려 한 코드이지만 시간 초과의 원인이 된다.
100과 100은 200 300 400 으로 계속 겹쳐지는 부분이 발생할 수 있다.
(왜냐면 hash에 각 2 3 4를 곱한 값을 저장하고 비교하여 count를 높이기 때문)
그를 방지하기 위해 index를 사용했지만 그렇게 하는 건 복잡도를 높이는 원인이 된다.
두번째 시도 👀(...실패)
function solution(weights) {
let answer = 0;
let saved = new Map();
for (let i = 0; i < weights.length; i++) {
let target = weights[i];
for (let j = 0; j < 4; j++) {
if (saved.get(target) === undefined) {
saved.set(target, [i]);
} else {
saved.set(target, [...saved.get(target), i]);
}
target = target + weights[i];
}
}
const checkCase = (num) => {
if (num === 1) {
return 0;
}
return checkCase(num - 1) + (num - 1);
};
saved = [...saved]
.map((arr) => arr.filter((item, index) => index === 1))
.map((item) => item.join(``));
saved = saved.map((item) =>
item
.split(``)
.filter((item2) => item2 !== ",")
.join(``)
);
saved = [...new Set(saved)].filter((item) => item.length > 1);
saved.forEach((item) => {
answer = answer + checkCase(item.length);
});
return answer;
}이건 그냥 겹치는 모든 index를 저장한 후에 후처리를 해주는 형식인데
saved는 {} 형태로 spread operator를 사용해서 또 [] 로 바꿔주고 split, filter,map,join등 배열을 순회하는 요소가 너무 많아
실패했다.
checkCase 함수는 재귀함수로 순서의 경우를 계산해주는 함수인데 귀엽다 ㅋ
재귀에 요즘 자신이 붙었나보다 ㅋㅋ
아무튼 위 코드도 시간통과에실패했고 또 정확도에서도 더 낮은 점수를 받게되었다.
그럼 어떻게 해야할까
세번째 시도 👀 (성공 🖖)
흠.. 그럼 비율로 문제를 풀어야하나?
맞다 비율로 풀어야한다. 각 2m 3m 4m 니까
각 무게의 비율이
2:3, 2:4, 3:2, 4:2, 2:2, 3:3, 4:4 중 하나면 되는 거다.
그럼 ? 2:3, 1:2, 3:2, 2:1, 1:1 로 줄일 수 있고 배열을 정렬하면
앞에서 뒤까지는 커지거나 작아지는 비율로만 정의할 수 있다.
필자는 오름차순을 선택했다.
[100, 100, 180, 270, 360]
그럼 앞에서 뒤까지는 높은 비율의 무게만 존재하겠다.
비율은 2:3, 1:2, 3:4, 1:1 뿐이다 !
해쉬에 각 비율을 곱한 수를 저장하면서 뒤에 배열의 몸무게 원소를 비교하면 ?? 문제를 해결할 수 있지 않을까? 코드는 다음과 같다.
function solution(weights) {
const saved = new Map();
let count = 0;
weights.sort((a, b) => a - b);
// 오름차순으로 정렬
const ratio = [1, 2, 4 / 3, 3 / 2];
for (let i = 0; i < weights.length; i++) {
if (saved.get(weights[i]) !== undefined) {
//이미 있으면?
// +를 해주는게맞지
count = count + saved.get(weights[i]);
}
for (let j = 0; j < 4; j++) {
if (saved.get(weights[i] * ratio[j]) === undefined) {
saved.set(weights[i] * ratio[j], 1);
} else {
saved.set(weights[i] * ratio[j], saved.get(weights[i] * ratio[j]) + 1);
}
}
}
return count;
}다음과 같이 비율 arr을 만들어서 각 비율을 곱해준 값들을 해쉬에 저장한다 이때 만약 저장된 값이 없다면 1 을 저장하고 이미 존재한 값이면 기존에 +1을 해줘서 그 값을 가질 수 있는 원소의 개수를 저장한다. 그 후 배열을 순회하면서 saved(해시)에 존재하는 값이면? 그 안의 get값을 가져와서 count에 더해주면된다.
위 문제는 천천히 생각을 오래 한 후에 문제를 풀어야 잘풀렸을 거 같은데 너무 무턱대도 덤볐던 거 같다. 항상 문제를 오래 읽고 생각하는 힘을 길러야겠다.
