CodeWars 알고리즘 문제 풀기
May 09, 2021최근에 codewars를 통해 알고리즘 문제를 일주일에 한두개씩 풀고 있다. 그 중에 자바스크립트 reduce 메서드를 이용한 기억할만한 문제가 있어서 블로그에 따로 정리하고자 한다.
문제는 아래와 같다.
A format for expressing an ordered list of integers is to use a comma separated list of either
- individual integers
- or a range of integers denoted by the starting integer separated from the end integer in the range by a dash, ’-‘. The range includes all integers in the interval including both endpoints. It is not considered a range unless it spans at least 3 numbers. For example “12,13,15-17”
Complete the solution so that it takes a list of integers in increasing order and returns a correctly formatted string in the range format.
Example:
solution([-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]);
// returns "-6,-3-1,3-5,7-11,14,15,17-20"
푸는 과정
해당 문제는 어레이 형태의 자료 구조에 속한 엘러먼트들을 3개 이상의 연속된 숫자일 경우에 중간에 '-'
스트링을 추가하여 스트링으로 변환하고, 연속된 숫자가 아닐 경우 그냥 스트링으로 변환하며 각자의 엘러먼트 구분은 ,
로 처리해야한다.
나는 처음에는 인자로 주어진 어레이를 한바퀴 돌면서 연속된 엘러먼트들이 들어간 sub 어레이와 그렇지 않은 sub 어레이로 변환해야 겠다고 생각했다. 그러다가 굳이 .map → .reduce를 거칠 필요 없이 한번에 .reduce 메서드를 통해서 연속된 엘러먼트들을 붙인 어레이를 생성한 후에 이를 스트링 형태로 바꿀 수 있지 않을까? 고민을 하게 되었고 아래와 같이 로직을 짰다.
자바스크립트 어레이 메서드 reduce에 관한 설명은 내 지난 포스트를 참조하면 된다.
const list = [-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17];
// 이 list를 "-6,-3-1,3-5,7-11,14,15,17" 으로 리턴하는 것이 과제이다.
let firstEl = true; // 처음으로 연속되는 숫자가 등장하는지에 대한 불린 값
let count = 1; // 연속되는 빈도 수
const moreList = list.reduce((acc, cur, idx) => {
if (cur + 1 !== list[idx + 1]) {
// 해당 조건은 -6처럼 다음 인덱스의 값이 연속으로 이어지는 지 여부를 판단한다.
// 이 조건에 합당하다면 해당 cur 값의 다음 값은 cur 값과 연속되지 않는다.
if (cur - 1 === list[idx - 1] && count > 2) {
// 이 조건은 1과 같이 1 다음 인덱스는 1과 연속되지 않지만 1이 연속되는 숫자의 마지막 값임을 판별하기 위해 사용된다.
// 3번 이상 연속되어야 함을 판별한다.
acc.push(`-${cur}`); // -을 붙여서 어레이에 푸시한다.
} else {
acc.push(cur); // 연속되지 않으므로 그냥 푸시한다.
}
firstEl = true;
count = 1;
// 연속은 이제 끊겼으므로 firstEl, count를 초기화한다.
} else {
// 해당 조건은 -3과 같이 다음 인덱스가 cur의 숫자에 연속되는 경우이다.
if (count === 1) {
// 첫번째 연속되는 숫자가 등장한 경우
acc.push(cur);
count++;
firstEl = false;
} else {
count++;
}
}
return acc;
}, []); // 초깃값이 주어지면 인덱스는 0부터 시작함
console.log('moreList:', moreList);
// 'moreList:' [-6, -3, '-1', 3, '-5', 7, '-11', 14, 15, 17];
[-6, -3, '-1', 3, '-5', 7, '-11', 14, 15, 17]
이런 형태의 어레이가 나왔다. 이제 바라는 값에 좀 더 가까워졌다. 이 어레이에서 연속되는 값의 마지막 값은 string 형태이므로 이를 이용해서 로직을 짜면 될 것 같다.
let str = moreList[0]; // str 초깃값 지정
moreList.forEach((el, idx) => {
const nextIdx = idx + 1;
if (moreList.indexOf(moreList[nextIdx]) !== -1) {
if (typeof moreList[nextIdx] === 'string') {
str += moreList[nextIdx];
} else {
str += `,${moreList[nextIdx]}`;
}
}
});
console.log(str); // '-6,-3-1,3-5,7-11,14,15,17'
위의 두 단계 솔루션을 이어붙여서 솔루션 도출에 성공했다.
function solution(list) {
let firstEl = true;
let count = 1;
const moreList = list.reduce((acc, cur, idx) => {
if (cur + 1 !== list[idx + 1]) {
if (cur - 1 === list[idx - 1] && count > 2) {
acc.push(`-${cur}`); // 마지막임
} else {
acc.push(cur);
}
firstEl = true;
count = 1;
} else {
if (count === 1) {
acc.push(cur);
count++;
firstEl = false;
} else {
count++;
}
}
return acc;
}, []);
let str = moreList[0];
moreList.forEach((el, idx) => {
const nextIdx = idx + 1;
if (moreList.indexOf(moreList[nextIdx]) !== -1) {
if (typeof moreList[nextIdx] === 'string') {
str += moreList[nextIdx];
} else {
str += `,${moreList[nextIdx]}`;
}
}
});
return str;
}