2.7프로그래머스 Lv.1 #78~82
프로그래머스 Lv.1 78~82번
개요
프로그래머스에 자바스크립트로 풀 수 있는 Lv.1 문제는 총 82문제가 있다. 정답률 높은 문제 순, 78 ~ 82번 문제 풀이 중 배울 점이 있는 풀이들에서 배운 개념들을 내 것으로 만들고자 정리해본다.
78. 붕대 감기
붕대 감기는 게임에서 붕대 감기라는 기술을 통해 회복을 하는데, 최대 연속 붕대감기 시간을 채우면 보너스로 체력을 더 얻고(단, 최대 체력을 초과한 회복은 불가) 몬스터로부터 공격이 들어오면 붕대감기 시간이 리셋될 때 붕대 감기 기술의 시전 시간, 1초당 회복량, 보너스 회복량을 담은 배열과 최대 체력, 몬스터가 공격하는 시간과 피해량을 담은 배열이 주어질 때 모든 공격이 끝난 직후 남은 체력을 반환하는 함수를 작성하는 문제다.
나는 이렇게 단순하게 매 초를 진행하며 for문으로 풀었다. 아이디어가 있다면, 공격 시점이 2초, 3초, 11초 이런 식으로 불규칙적이고 배열에서 찾으려면 시간 낭비가 있으므로 set으로 바꾼 후 set.has()로 해당 시점이 공격시점인지, 방해받지 않은 회복 시점인지 체크했다는 것.
javascriptfunction solution(bandage, health, attacks) { const [dur, healPerSec, bonusHeal] = bandage; const endTime = attacks[attacks.length - 1][0]; const maxHealth = health; let curHealth = health, continuedDur = 0; const attackMap = new Map(attacks); for(let t = 1; t <= endTime; t++){ let temp = curHealth; if(attackMap.has(t)) { temp -= attackMap.get(t); continuedDur = 0; if(temp > 0){ curHealth = temp; } else return -1; } else { continuedDur++; if(continuedDur === dur){ temp += bonusHeal + healPerSec; if(temp > maxHealth) temp = maxHealth; continuedDur = 0; curHealth = temp; } else { temp += healPerSec; if(temp > maxHealth) temp = maxHealth; curHealth = temp; } } } return curHealth; }
78-1. 개선(리팩토링)
여러가지 개선이 가능하다.
우선은 변수명부터.
- curHealth는 어차피 체력을 다루는 함수이므로 cur이라는 이름으로 간소화
- attackMap보단 hit과 같이 다른 보다 간결하면서 같은 의미의 표현으로
- continuedDur같이 너무 긴 변수명보다 명확한 streak으로
다음으로, temp는 사실 필요하지 않다. 분기가 갈리는 부분(최대 체력을 넘어서서, temp에 다시 cur를 할당하는 부분)은 그냥 삼항 연산자로 조건을 걸고 해당 조건으로 분기하면 된다.
마지막으로, 기본 회복과 연속 dur초 달성 보너스를 아예 분기하기보단, 하나로 묶고 보너스일때 보너스만 추가하고 streak을 초기화하는 방식으로 진행해도 된다. 코드로 하면 아래와 같다.
javascriptfunction solution(bandage, health, attacks) { const [dur, x, bonus] = bandage; const maxHealth = health; const hit = new Map(attacks); const endTime = attacks[attacks.length - 1][0]; let cur = health; let streak = 0; for (let t = 1; t <= endTime; t++) { if (hit.has(t)) { cur -= hit.get(t); if (cur <= 0) return -1; streak = 0; continue; } // 기본 회복 cur = Math.min(maxHealth, cur + x); streak++; // 연속 dur초 달성 보너스 if (streak === dur) { cur = Math.min(maxHealth, cur + bonus); streak = 0; } } return cur; }
78-2. 공격 사이 구간을 한번에 처리
초 단위로 루프한 위의 방식도 물론 가능하지만, 공격이 띄엄띄엄하다는 점에서 공격 사이는 그냥 수식으로 처리해버리고 공격에 대해서만 순회를 해도 된다. 물론, 말이 '그냥 수식으로 처리'지 섬세한 처리가 필요하다. 보너스 횟수를 계산해야하기 위해선 연속으로 회복한 횟수와 공격을 받지 않은 시간 길이를 알고 dur로 나누는 작업을 해야 한다.
javascriptfunction solution(bandage, health, attacks) { const [dur, x, bonus] = bandage; const maxHealth = health; let cur = health; let streak = 0; // 이전 공격 이후의 연속 초 let prevTime = 0; // 마지막으로 본 시각(0에서 시작) for (const [time, dmg] of attacks) { const gap = time - prevTime - 1; // 공격 사이 비공격 구간 길이 if (gap > 0) { const full = Math.floor((streak + gap) / dur) - Math.floor(streak / dur); // 이번 gap 동안 추가로 달성한 보너스 횟수(streak을 몇번 채웠는가?) cur = Math.min(maxHealth, cur + x * gap + bonus * full); streak = (streak + gap) % dur; } // 공격 시점: 회복 없이 체력 차감 및 연속 초기화 cur -= dmg; if (cur <= 0) return -1; streak = 0; prevTime = time; } return cur; }
79. 신고 결과 받기
신고 결과 받기는 아이디 리스트와 신고 내역, 정지 당할때까지의 신고 횟수가 주어지면 각 아이디 리스트들에게 몇 개의 신고 처리 메일을 보내야하는지를 구하는 함수를 작성하는 문제다.
나는 각 이용자별로 신고당한 횟수를 객체로 만들고, 중복을 제거하고(한 유저가 다른 특정 유저를 여러번 신고하는데 이건 중복하면 안된다), 정지된 이용자들을 추린 후 아이디 리스트에서 매핑하였다.
javascriptfunction solution(id_list, report, k) { // 각 이용자별로 신고당한 횟수 객체로 const status = Object.fromEntries(id_list.map(id => [id, 0])); // 중복 제거 const reported = [...new Set(report)].map(str => str.split(" ")); for(const r of reported){ status[r[1]]++; } // 정지된 이용자 const mailList = []; for(const banned in status){ if(status[banned] >= k) { for(let i = 0; i < reported.length; i++){ reported[i][1] === banned && mailList.push(reported[i][0]); } } } // 정지된 이용자들을 신고한 이용자들 매핑 return id_list.map(id => mailList.filter(mail => mail === id).length); }
79-1. 개선(리팩토링)
현재 메일 받을 사람들을 모두 mailList에 모은 후 filter로 세는 방식은 불필요한 O(R * U)비용이 든다. (U = 유저 수, R = 신고수) 각 유저별 메일 수를 객체로 만들고 id_list를 매핑하는게 더 효율적이고 읽기도 편하다.
javascriptfunction solution(id_list, report, k) { // 1) 중복 신고 제거 const dedup = [...new Set(report)].map(s => s.split(' ')); // [reporter, reported] // 2) 각 유저의 신고 당한 횟수 const reportedCnt = Object.fromEntries(id_list.map(id => [id, 0])); for (const [, reported] of dedup) { reportedCnt[reported]++; } // 3) 정지 대상 집합 const banned = new Set(id_list.filter(id => reportedCnt[id] >= k)); // 4) 각 유저의 메일 수 (정지자를 신고했으면 +1) const mailCnt = Object.fromEntries(id_list.map(id => [id, 0])); for (const [reporter, reported] of dedup) { if (banned.has(reported)) mailCnt[reporter]++; } // 5) id_list 순서대로 결과 배열 return id_list.map(id => mailCnt[id]); }
80. 동영상 재생기
동영상 재생기는 동영상 길이, 현재 위치, 오프닝 시작/엔딩 시각 및 사용자 입력을 나타내는 배열이 주어지면 사용자 입력이 모두 끝난 후의 동영상 위치를 반환하는 함수를 작성하는 문제다.
개인적으로 이 문제의 핵심은 현재 재생 위치가 오프닝 구간 안에 있으면 자동으로 오프닝이 끝나는 위치로 이동, 그리고 시작/끝나기 10초 범위 내에 있으면 양 끝으로 보내는 것을 어떻게 처리하냐라고 생각한다. 이 처리는 우선 맨 처음에 주어진 현재 위치에서도 적용되어야 하고, 매 사용자 입력이 끝난 후마다도 적용되어야 한다. 나는 init이라는 함수를 만들고 이를 처음에 실행시키고 명령을 순회하면서도 매번 실행시키는 식으로 처리했다.
javascriptfunction solution(video_len, pos, op_start, op_end, commands) { function toSec(timeStr){ const [min, sec] = timeStr.split(":"); return +min * 60 + +sec; }; const command = { next : 10, prev : -10, }; let cur = toSec(pos), max = toSec(video_len), ops = toSec(op_start), ope = toSec(op_end) function init(){ if(cur > max - 10) cur = max; if(cur < 10) cur = 0; if(cur >= ops && cur <= ope) cur = ope; } init(); for(c of commands){ cur += command[c] init(); } return `${Math.floor(cur / 60)}:`.padStart(3, 0) + `${cur % 60}`.padStart(2, 0) }
80-1. 개선(리팩토링)
여러가지 방면에서 리팩토링이 가능하다.
next와 prev는 이 시점에선 객체로 만드는게 오버킬이다. 나중에 더 많은 명령어가 추가되면 몰라도, 현재는 그냥 cur += 10등으로 처리하는게 낫다.
또, max, ops, ope는 모두 변동하지 않으므로 const로 정의해야 한다.
그리고 사소하지만 toSec에 대비되는 toTime도 비록 마지막에 1번만 쓰긴 하지만 만들면 좀 더 가독성이 좋아진다.
javascriptfunction solution(video_len, pos, op_start, op_end, commands) { const toSec = (s) => { const [mm, ss] = s.split(':').map(Number); return mm * 60 + ss; }; const toTime = (sec) => { const mm = String(Math.floor(sec / 60)).padStart(2, '0'); const ss = String(sec % 60).padStart(2, '0'); return `${mm}:${ss}`; }; const max = toSec(video_len); const ops = toSec(op_start); const ope = toSec(op_end); let cur = toSec(pos); // 시작 시점: 오프닝 구간이면 즉시 스킵 if (cur >= ops && cur <= ope) cur = ope; for (const cmd of commands) { // 1) 이동 if (cmd === 'next') cur += 10; else cur -= 10; // 2) 클램프 (0 ~ max) if (cur < 0) cur = 0; if (cur > max) cur = max; // 3) 오프닝 구간이면 즉시 스킵 if (cur >= ops && cur <= ope) cur = ope; } return toTime(cur); }
81. 택배 상자 꺼내기
이 문제는 상자 n개가 있으면 한 층에 w개씩 상자를 쌓고, num이 주어지면 해당 번호의 상자를 꺼내기 위해선 총 몇개의 상자를 꺼내야 하는지를 묻는 문제다. 쌓는 방식은 오른쪽으로 쭉 쌓다가 다음 층에선 왼쪽으로, 다음 층에선 오른쪽으로...를 반복한다.
나는 스택 문제로 파악했고, w의 길이를 가진 배열을 만들고 각각의 인덱스를 배열로 스택처럼 활용했다.
javascriptfunction solution(n, w, num) { const stacks = Array.from({length: w}, () => []); let dir = 'r', idx = 0, stackIdx = 0; for(let i = 1; i <= n; i++){ if(dir === 'r'){ idx = i % w === 0 ? (w - 1) : (i % w) - 1; } else { idx = i % w === 0 ? 0 : w - (i % w) } stacks[idx].push(i); if(i === num) stackIdx = idx; if(i % w === 0) dir === "l" ? dir = "r" : dir = "l"; } return stacks[stackIdx].length - stacks[stackIdx].indexOf(num); }
81-1. 스택 만들지 않고 찾는 박스의 행/열 계산하기
옳거니 스택이다!하고 접근했지만 사실 이 문제는 그냥 찾고 있는 박스의 행/열을 찾고 박스의 위치를 찾으면 된다. 왜냐하면 모든 열들이 거의 균등(크게 차이 나봐야 1)하게 채워지기 때문이다.
따라서 우선 num의 행과 열을 구하는데, 왼쪽 -> 오른쪽으로 채우는 중인지 오른쪽 -> 왼쪽으로 채우는 중인지는 몇 행에 있는지만 보면 된다. 즉, 행이 홀수 행이면 오른쪽 -> 왼쪽일 것이고 짝수 행이면 반대일 것이다.
이후 그렇게 구한 열에 대해 num이 있는 행 위쪽의 박스 수를 세는데, 맨 마지막 행(가장 위에 있는 박스들)이 부분적으로만 찼을때 그 열에 박스가 있는지 없는지를 체크하면 된다.
javascriptfunction solution(n, w, num){ // num의 (행, 열) const row = Math.floor((num - 1) / w); const idxInRow = (num - 1) % w; const col = (row % 2 === 0) ? idxInRow : (w - 1 - idxInRow); const rows = Math.ceil(n / w); // 전체 행 수 const last = n - (rows - 1) * w; // 마지막 행 채워진 칸 수(가득차면 0) // num이 마지막 행일 경우 if(row === rows - 1) return 1; // 마지막 행이 가득 찬 경우 if(last === 0) return rows - row; // 마지막 행이 부분만 찼을 때, num의 열은 찼는지 체크 let lastHasCol; if((rows - 1) % 2 === 0){ // 마지막 행이 왼 -> 오 lastHastCol = (col < last); } else { // 마지막 행이 오 -> 왼 lastHasCol = col >= w - last } return (rows - row) + (lastHasCol ? 1 : 0); }
82. 가장 많이 받은 선물
아주 문제 설명이 긴 문제로, 문제의 핵심은 입출력 예에 있는 표 두개를 만들어 서로 선물을 어떻게 주고 받았는지 내역을 어떻게 기록할 것인지, 또 선물 지수를 어떻게 구현할지라고 생각한다.
나는 friends라는 배열이 주어진 만큼, 이 friends 배열의 인덱스를 이용해 표와 선물지수를 구하는데 필요한 배열들을 만들었다. 개인적으로 사소한 포인트 하나가 더 있다면 표에서 i와 j가 같을때 Array[i][j]는 반드시 0이기 때문에 이중 for문에서 이는 배제하고, 앞선 중복을 피하기 위해 안쪽 for문에는 j를 i + 1부터 시작했다는 것.
javascriptfunction solution(friends, gifts) { // 준 선물/받은 선물 기록 const logs = gifts.map(l => l.split(" ")); const fIdx = Object.fromEntries(friends.map((f, i) => [f, i])); const len = friends.length; // 주고받은 선물 표 const count = Array.from({length: len}, () => Array(len).fill(0)); // 선물 지수 계산용 const give = Array(len).fill(0); const receive = Array(len).fill(0); for(const l of logs){ const [giver, receiver] = l; const gIdx = fIdx[giver]; const rIdx = fIdx[receiver]; count[gIdx][rIdx]++; give[gIdx]++; receive[rIdx]++; } const nextReceive = Array(len).fill(0); const giftIdx = give.map((v, i) => v - receive[i]); // 두 사람이 선물을 주고받은 기록이 있다면 for(let i = 0; i < count.length; i++){ for(let j = i + 1; j < count[0].length; j++){ const a = count[i][j]; const b = count[j][i]; if(a > b){ nextReceive[i]++; } else if (b > a){ nextReceive[j]++; } else { // 기록이 없거나 주고받은 수가 같다면 선물 지수로 비교 if(giftIdx[i] > giftIdx[j]) nextReceive[i]++ if(giftIdx[j] > giftIdx[i]) nextReceive[j]++; // 같으면 아무도 선물 안 받음 } } }; return nextReceive.reduce((acc, cur) => acc = Math.max(acc, cur),0); }
82-1. 약간의 개선
약간의 리팩토링을 해보자면, logs는 아주 간단한 로직으로 만들어진 배열이기 때문에 그냥 gifts에 바로 적용하여 순회하는게 메모리나 속도에 유리하다.
또, 배열 내에서 최댓값을 반환하기 위해 reduce를 썼는데, Math.max(...Array)형태가 보다 알아보기도 쉽고 간단하다.
사소하지만 len은 약간 모호한 표현일 수 있다. 카카오 친구들의 수이기 때문에 n으로 더 간결하고 정확하게 표현할 수 있다.
javascriptfunction solution(friends, gifts) { const n = friends.length; const idx = Object.fromEntries(friends.map((name, i) => [name, i])); const count = Array.from({ length: n }, () => Array(n).fill(0)); const give = Array(n).fill(0); const recv = Array(n).fill(0); // 기록 누적 for (const line of gifts) { const [from, to] = line.split(' '); const i = idx[from], j = idx[to]; count[i][j]++; give[i]++; recv[j]++; } const giftIndex = give.map((g, i) => g - recv[i]); const nextRecv = Array(n).fill(0); // 쌍 비교 (i < j) for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { const a = count[i][j]; const b = count[j][i]; if (a > b) nextRecv[i]++; else if (b > a) nextRecv[j]++; else { if (giftIndex[i] > giftIndex[j]) nextRecv[i]++; else if (giftIndex[j] > giftIndex[i]) nextRecv[j]++; } } } return Math.max(...nextRecv); }
이렇게 프로그래머스 사이트에 있는 자바스크립트 lv.1 문제를 모두 풀었다. 어떤 문제들은 알고리즘이라고 보기 어려울 정도로 쉬운 문자열 파싱 문제였지만, 어떤 문제들은 스택과 같은 데이터 구조를, 어떤 문제들은 꽤 복잡한 조건들을 요구하기도 했다. 상위 알고리즘 문제를 푸는데 앞서 좋은 연습이 되었다고 생각한다.