Published
Edited
May 10, 2020
1 star
function solve(ns) {
// 길이가 한 개 이하이면 길이를 그대로 반환
if (ns.length <= 1) return ns.length
// [1, 1, 2] 형식의 입력을 [{v:1, cnt: 1}, {v: 1, cnt: 1}, {v: 2, cnt: 1}] 형식으로 변환
const counters = ns.map(v => ({v, cnt: 1}))
// 압축하여 [{v:1, cnt: 2}, {v: 2, cnt: 1}] 형식으로 줄이기
const comped = compress(counters)
// 가장 큰 cnt를 반환
return comped.sort((a, b) => {
if (a.cnt === b.cnt) return 0
return a.cnt > b.cnt ? -1 : 1
})[0].cnt
}
function compress(ns) {
// 정렬하기
ns = ns.sort((a, b) => {
if (a.v === b.v) return 0
return a.v < b.v ? -1 : 1
})
// 짝이 맞는 수는 하나로 합쳐서 저장하고, 안 맞는 수는 그대로 저장
let comped = []
let cur = undefined
for(let i = 0; i < ns.length; i++) {
if(cur === undefined) {
cur = ns[i]
} else {
if(cur.v === ns[i].v) {
comped.push({v: cur.v * 2, cnt: cur.cnt + ns[i].cnt})
cur = undefined
} else {
comped.push(cur)
cur = ns[i]
}
}
}
if(cur !== undefined) comped.push(cur)
// 원래 배열과 길이가 같으면 더이상 줄일 수 없으므로 종료, 그렇지 않으면 더 줄이기
return comped.length === ns.length ? comped : compress(comped)
}
test('Example cases', () => {
expect(solve([1])).toBe(1)
expect(solve([2, 2, 2, 2, 3, 3, 5, 6])).toBe(4)
expect(solve([3, 3, 3, 3, 3, 3, 12])).toBe(5)
expect(solve([16, 16, 16, 16, 16, 16, 16, 16, 1, 1, 2, 4, 4])).toBe(8)
})
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
