etc
2023.09.10 22:23:43
09/10 스킬트리(프로그래머스)
문제명 : 스킬트리
레벨 : 2
문제유형 : 문자열, 위상정렬(큐)
나의 풀이 (해시맵)
문제 풀이의 아이디어
- 해시맵 사용 : 필수 스킬들을 가진 배열 skill의 모든 스킬을 배웠는지를 탐색하려 하였으나, 이렇게 되면 매번 문자열 전체를 탐색해야하므로 시간복잡도가 늘어난다. 필수 스킬들을 해시맵 형태로 관리하여 탐색 시간을 줄이려고 했다.
- 직전 스킬만 확인 : 문제를 풀이하다보니 '직전에 배워야할 스킬만 확인하면 된다'는 점을 깨닫고, 해시맵은 '문자열-인덱스'를 가진 맵으로 바꾸었다.
- 추가로 배운 문법 : 맵을 사용할 때에는
const map = new Map()으로 선언하고,map.set(key, value)형태로 값을 추가하며,map.has(key)로 값의 존재유무를 확인한다....만 이게 기억나지 않았다. object에서 값의 존재유무를 확인할 때에는map.hasOwnProperty(key)로 확인한다.
풀이
function solution(skill, skill_trees) {
var answer = 0;
// 각 스킬들이 문자열 skill에서 차지하는 인덱스를 저장한다.
const skillIndexMap = Object()
for(let index = 0; index < skill.length; index++) {
const skillName = skill[index]
skillIndexMap[skillName] = index
}
skill_trees.map(skillTree => {
// 스킬의 배움 여부를 저장하는 skillArray를 만들고 초기화한다.
const skillArray = []
let canCompleted = true
for(let index = 0; index < skill.length; index++) {
skillArray[index] = false
}
// 스킬어레이[현재스킬인덱스-1]이 false인 경우에는 배울 수 없다.
for(let index = 0; index < skillTree.length; index++) {
const currentSkill = skillTree[index] //현재의 스킬값
let currentIndex = -1 //문자열 skill에서 현재 스킬이 차지하는 인덱스(없으면 -1)
if(skillIndexMap.hasOwnProperty(currentSkill)){
currentIndex = skillIndexMap[currentSkill]
}
// 만약 문자열 skill에 현재 스킬이 있으면
if(currentIndex >= 0) {
// (현재스킬의 인덱스 -1)이 스킬배움여부 skillArray에 있는지 확인.
// (현재 스킬의 인덱스가 0인 경우를 예외처리)
if(currentIndex === 0 || !!skillArray[currentIndex - 1]) {
skillArray[currentIndex] = true
continue
}
// 만일 스킬배움여부 skillArray에 있는 (현재스킬의 인덱스 -1)의 값이 false이면 선행 스킬을 배우지 않았으므로 false
if(!skillArray[currentIndex-1]) {
canCompleted = false
break
}
}
}
if(canCompleted) {
answer = answer + 1;
}
})
return answer;
}
if(currentIndex) 부근을 비롯해 리팩토링해야할 부분이 몇개 보이지만, 의도한 대로 작동한다.
문자열을 이용한 풀이
문제 해결 아이디어
다른 사람들의 문제 풀이를 보니, 해당 문제를 문자열로 접근했다.
- 'target'이 될 'skill' 문자열에 포함되지 않는 문자열은 skill_tree에서 지워버린다.
- 지운 결과가 skill과 패턴 일치하는지를 검증한다.
- (예외처리) skill_tree에서 skill 문자열에 포함된 문자열이 전혀 없는 경우에도 가능한 케이스이므로 answer는 1 증가시켜야 한다.
정규표현식을 이용한 풀이
function solution(skill, skill_trees) {
var answer = 0;
const regexp = new RegExp(`[${skill}]`, 'g');
skill_trees.map((skillTree, i) => {
const mathedArray = skillTree.match(regexp)
if(!mathedArray?.length) return answer = answer + 1
if(skill.startsWith(mathedArray.join(""))) answer = answer + 1
})
return answer;
}
new RegExp로 선언하는 부분은 문자열 변수를 regExp에 적용하는 사실상 유일한 방법이니 참고하자.
09/11 요격 시스템(프로그래머스)
문제명 : 요격 시스템
레벨 : 2
문제유형 : 배열, 정렬
나의 풀이 (배열)
문제 해결 아이디어
- 가장 왼쪽에서부터 탐색을 시작한다.
- 타겟의 가장 오른쪽에 미사일을 배치한다.
- 만일 새로 만난 타겟이 기존 미사일에 포함되지 않으면 새로운 미사일을 배치한다.
- 만일 새로 만난 타겟이 기존 미사일에 포함된다면, 새로 만난 타겟과 기존 타겟 중 오른쪽 끝이 더 짧은 쪽에 배치한다.
풀이코드
function solution(targets) {
var answer = 0;
let end = 0;
targets.sort((a,b)=> a[0]-b[0]).forEach(e=>{
const [crrStart, crrEnd] = e
if(crrStart >= end) {
answer += 1;
end = crrEnd
} else if (crrEnd < end) {
end = crrEnd
}
})
return answer;
}
정렬을 이용한 풀이
문제 해결 아이디어
해당 문제는 Greedy 알고리즘의 '활동 선택 문제' 유형이다.
하나의 기준점, 즉 활동이 일어날 때, 한 번의 활동으로 최대한 많은 작업을 처리하도록 한다.
유사 문제로는 백준의 1931번 회의실 배정 문제가 있으며,
Stranger's lab 블로그에 잘 설명이 되어 있다.
해당 풀이로는 아래와 같이 풀이된다.
[s, e]형태의 요소를 끝나는 위치 e를 기준으로 정렬한다.- 가장 앞에서 하나(prev)를 고르고 answer를 1 증가시킨다. (즉, 끝나는 위치가 가장 빠른 녀석을 고른다.)
- 영역에 prev를 포함하고 있는 녀석들을 제외시킨다. (미사일에 맞은 애들이니까)
- 제외되지 않는 녀석 중 가장 앞에서 하나를 고르며 2, 3 과정을 반복한다.
풀이코드
function solution(targets) {
let answer = 0, prev = -1;
const len = targets.length
targets.sort((a, b) => a[1] - b[1])
for (let i = 0; i < len; i++) {
const [a, b] = targets[i]
if (prev <= a) {
prev = b
answer += 1
}
}
return answer;
}
09/11 두 원 사이의 정수 쌍(프로그래머스)
문제명 : 두 원 사이의 정수 쌍
레벨 : 2
문제유형 : Greedy
나의 풀이
문제 해결 아이디어
간단하게 피타고라스 정리를 이용했다.
정수 쌍을 받아 a**2 + b**2 로 거리를 구한다.
해당 거리가 작은 원의 반지름 r1**2 이상이고, 큰 원의 반지름 r2**2 이하라면 포함된다.
function solution(r1, r2) {
var answer = 0;
//x나 y는 -r2~r2까지
for (let x = -r2; x <= r2; x++) {
for(let y = -r2; y <= r2; y++) {
const distanceSqr = x**2 + y**2
if(distanceSqr <= r2**2 && distanceSqr >= r1**2) {
answer = answer + 1
}
}
}
return answer;
}
그리고 해당 풀이는 시간초과가 발생한다.
그래서 1사분면만 구하도록 만들었다.
function solution(r1, r2) {
var answer = 0;
//x나 y는 -r2~r2까지
for (let x = 0; x <= r2; x++) {
for(let y = 1; y <= r2; y++) {
if(Math.abs(x)+Math.abs(y) < r1) continue
const distanceSqr = (x**2 + y**2)
if(distanceSqr <= r2**2 && distanceSqr >= r1**2) {
answer = answer + 1
}
}
}
answer *= 4
return answer;
}
..그래도 안된다.
면적을 이용한 풀이
제육's 휘발성 코딩
위의 그림에서,
x값이 1씩 증가한다고 해보자.
5^2 >= x^2 + y^2을 충족하는 정수 y의 최대값을 구한다.
가령 x가 1일 때,
5^2 >= 1 + y^2
24 >= y^2
y는 약 4.899이고, 정수값으로는 4이다.
이 말은 해당 원 안에서 x가 1인 점은 총 4개가 된다는 것을 의미한다.
이번엔 원이 두 개 있다.
바깥쪽 원은 정수 r2^2 >= x^2 + y^2에서 정수 y의 최대값을 구한다.
안쪽 원은 (안쪽원의 지름에 걸치는 값도 답에 포함되므로) r2^2 > x^2 + y^2에서 정수 y의 최대값을 구한다.
이렇게 구한 최대값들을 서로 빼면 답 answer가 된다.
기존 코드가 O(n^2)이었다면, 본 코드는 O(n)의 시간복잡도를 갖는다.
09/11 당구 연습(프로그래머스)
문제 해결 아이디어
- 당구공은 상, 하, 좌, 우의 쿠션을 맞출 수 있으며, 예외적으로 움직이는 네 귀의 모서리까지 총 8방향으로 칠 수 있다.
- 이때 '최소 거리'를 구해야 하므로, (예각이 180도가 되는) 네 귀의 모서리를 맞추어 공을 맞추는 경우는 없다.
- 상, 하, 좌, 우의 쿠션을 맞추어 목적구를 맞추는 경우의 수를 구하면 된다. 이때
- 쿠션으로 가는 길에 목적구가 있는 경우는 제외한다. 즉 목적구가 수평/수직 상태인 경우에 대한 예외처리를 해준다.
풀이
function solution(m, n, startX, startY, balls) {
var answer = [];
// 위로치는 경우 (ball의 y좌표를 더한다.), 왼쪽으로 치는 경우(ball의 x좌표를 뺀다), 아래로 치는 경우(ball의 y좌표를 뺀다), 오른쪽으로 치는 경우 (ball의 x좌표를 더한다.)
// 이때 y좌표가 같으면, x1, xball을 뺐을 때, 값이 음수면 왼쪽으로 못치고, 값이 양수면 오른쪽으로 못친다.
// 만일 x좌표가 같으면, y1, yball을 뺐을 때, 값이 양수면 위쪽으로 못치고, 값이 음수면 아래쪽으로 못친다.
balls.forEach(ball=>{
const [targetX, targetY] = ball
const distances = []
// 위로 친다.
if(startX !== targetX || (startY - targetY) > 0) {
const yGap = n - targetY
distances.push(Math.pow((targetX- startX), 2) + Math.pow(((targetY + 2*yGap) - startY),2))
}
// 아래로 친다
if(startX !== targetX || (startY - targetY) < 0) {
distances.push(Math.pow((targetX- startX), 2) + Math.pow((- targetY - startY),2))
}
// 왼쪽으로 친다
if(startY !== targetY || (startX - targetX) < 0) {
distances.push(Math.pow((targetY - startY), 2) + Math.pow((- targetX - startX),2))
}
// 오른쪽으로 친다.
if(startY !== targetY || (startX - targetX) > 0) {
const xGap = m - targetX
distances.push(Math.pow((targetY- startY), 2) + Math.pow(((targetX + 2*xGap) - startX),2))
}
answer.push(Math.min(...distances))
})
return answer;
}
09/11 혼자서 하는 틱택토(프로그래머스)
- 소위말하는 '빡구현' 문제이다.
- 특정 조건에서 answer flag를 1로 만들어 둔 후,
- 예외가 되는 조건을 하나하나 추가해가며 answer flag가 0이 되도록 바꿔주는 방식으로 작성했더니 가독성이 좋다.
....많이 틀렸다.
function solution(board) {
var answer = 0;
let countO = 0;
let countX = 0;
// O와 X의 갯수를 셉니다.
board.forEach((str)=>{
str.split("").forEach(s => {
if(s==="X") countX += 1
else if(s==="O") countO += 1
})
})
if((countO - countX) === 0 || (countO - countX) === 1) {
answer = 1
}
// 승리 여부를 체크합니다.
let winO = 0;
let winX = 0;
if(answer) {
//가로를 체크합니다.
board.forEach(line => {
if(line === "OOO") {
winO += 1
} else if(line === "XXX") {
winX += 1
}
})
//세로를 체크합니다.
for(let x = 0; x < 3; x++) {
let countO = 0
let countX = 0
for(let y = 0; y < 3; y++){
if(board[y][x]==="O") countO += 1
if(board[y][x]==="X") countX += 1
}
if(countO === 3) winO += 1
if(countX === 3) winX += 1
}
// // 대각선을 체크합니다.
let countLTO = 0
let countLTX = 0
let countRTO = 0
let countRTX = 0
for(let i = 0; i < 3; i++) {
const ltPoint = board[i][2-i]
const rtPoint = board[i][i]
if(ltPoint==="X") countLTX += 1
else if(ltPoint==="O") countLTO += 1
if(rtPoint==="X") countRTX += 1
else if(rtPoint==="O") countRTO += 1
}
if(countLTO === 3) winO += 1
if(countLTX === 3) winX += 1
if(countRTO === 3) winO += 1
if(countRTX === 3) winX += 1
}
if(winO>=3 || winX>=3 || winO && winX) answer = 0
else if((winO >= 1) && (countO <= countX)) answer = 0
else if((winX >= 1) && (countO > countX)) answer = 0
return answer;
}
09/11 달리기 경주
문제명 : 달리기 경주
레벨 : 2
문제유형 : Greedy
1차 풀이(배열)
정직하게 배열에서 값들의 위치를 바꾸주었다.
function solution(players, callings) {
var answer = [...players];
callings.forEach(name => {
const crrIndex = answer.findIndex((e) => e===name)
// [answer[crrIndex], answer[crrIndex-1]] = [answer[crrIndex], answer[crrIndex]]
const temp = answer[crrIndex - 1]
answer[crrIndex-1] = answer[crrIndex]
answer[crrIndex] = temp
})
return answer;
}
시간 초과가 난다.
2차 풀이 (해시맵)
인덱스를 key로 갖는 해시맵과, 이름을 key로 갖는 해시맵을 만들었다.
function solution(players, callings) {
var answer = [];
const map = {}
const indexMap = {}
players.map((e,i)=>{
map[e] = i
indexMap[i] = e
})
callings.forEach(name => {
const crrIndex = map[name]
const prevName= indexMap[crrIndex-1]
map[name] = crrIndex-1
map[prevName] = crrIndex
indexMap[crrIndex-1] = name
indexMap[crrIndex] = prevName
})
Object.entries(map).map((e)=> {
const [name, index] = e
answer[index] = name
})
return answer;
}
09/11 추억 점수
문제명 : 두 원 사이의 정수 쌍
레벨 : 1
문제유형 : Greedy
풀이 코드
function solution(name, yearning, photo) {
var answer = Array.from({length:photo.length}).fill(0);
const map = {}
for(let index = 0; index < name.length; index++) {
map[name[index]] = yearning[index]
}
photo.forEach((currentPhoto, index) => {
currentPhoto.forEach(name=>{
if(map.hasOwnProperty(name)) answer[index] += map[name]
})
})
return answer;
}
null이나 undefined는 더하기가 안 되기 때문에
answer를 0으로 초기화해야 더하기 코드가 작동한다. (아니면 if문으로 처리해주거나..)
map객체를 사용하면 아래와 같다.
function solution(name, yearning, photo) {
var answer = Array.from({length:photo.length}).fill(0);
const map = new Map()
for(let index = 0; index < name.length; index++) {
map.set(name[index], yearning[index])
}
photo.forEach((currentPhoto, index) => {
currentPhoto.forEach(name=>{
if(map.has(name)) answer[index] += map.get(name)
})
})
return answer;
}
09/11 공원 산책
문제명 : 공원 산책
레벨 : 1
문제유형 : Greedy, 2차원 배열 탐색
나의 풀이
이동시킬 값을 vector라는 배열로 만들고, 이를 hashMap을 통해 관리하면 성능상에도 이점이 있고, 내 코드를 보기도 편하다.
2차원 배열탐색 문제의 경우 if문을 통한 예외처리문이 항상 복잡하게 나오는 건 어쩔 수 없는 것 같다.
(문제를 풀다보니 구조분해 할당이 편해서, 배열을 그냥 새로 할당했다. 다행이 성능은 통과했다.)
function solution(park, routes) {
var answer = [];
const vectorMap = {
E : [0, 1],
S : [1, 0],
W : [0, -1],
N : [-1, 0]
}
let startsPosition = []
for(let x = 0; x < park.length; x++){
for(let y = 0; y < park[0].length; y++){
if(startsPosition.length) break
if(park[x][y] === "S") startsPosition.push(x, y)
}
if(startsPosition.length) break
}
routes.forEach(str=>{
let crrPosition = [...startsPosition]
const [vectorName, counts] = str.split(" ")
const vector = vectorMap[vectorName]
let counter = 0
let canMove = true
while(counter < counts) {
const newPosition = [crrPosition[0]+vector[0], crrPosition[1]+vector[1]]
//이 부분에서 런타임 에러 주의. !park[newPosition[0]] || 로 한번 걸러줘야함
if(!park[newPosition[0]] || !park[newPosition[0]][newPosition[1]] || park[newPosition[0]][newPosition[1]] === "X") {
canMove = false
break
} else {
crrPosition = [...newPosition]
}
counter += 1
}
if(canMove) startsPosition = [...crrPosition]
})
return startsPosition;
}
09/12 바탕화면 정리
문제명 : 바탕화면 정리
레벨 : 1
문제유형 : 구현, 2차원 배열
나의 풀이
function solution(wallpaper) {
var answer = [];
let minX = 50
let minY = 50
let maxX = 1
let maxY = 1
wallpaper.forEach((rowData, row) => {
for(let col = 0; col < rowData.length; col++) {
const currentSpot = rowData[col]
if(currentSpot === "#") {
minX = Math.min(minX, col)
minY = Math.min(minY, row)
//비교할 때 +1 해주기!
maxX = Math.max(maxX, col+1)
maxY = Math.max(maxY, row+1)
}
}
})
answer = [minY, minX, maxY, maxX]
return answer;
}
09/12 덧칠하기
문제명 : 덧칠하기
레벨 : 1
문제유형 : 배열
나의 풀이 (슬라이딩 윈도우, 큐)
function solution(n, m, section) {
var answer = 0;
let lp = 1
let rp = lp+m-1
while(rp <= n) {
if(lp === section[0]) {
answer += 1
while(true) {
if(section.length && section[0] <= rp) {
section.shift()
} else {
break
}
}
// m을 한 번에 더해서 성능최적화
lp += m
rp += m
} else {
lp += 1
rp += 1
}
}
// 페인터가 끝에 다다랐을 때의 예외처리
if(section.length && section[0] <= rp) {
answer += 1
}
return answer;
}
성능이 좋지 않다.
다른 사람의 풀이 (다른 기준점)
다른 사람이 푼 답을 보니 성능이 월등히 좋아 여기에 남긴다.
function solution(n, m, section) {
let tried = 0
let maxRange = -Infinity
section.forEach(range=>{
if(maxRange < range){
tried++
maxRange = range+m-1
}
})
return tried
}
빠른 성능의 비결은 기준점을 다르게 한 것인데,
'n'을 길이로 한 칸씩 탐색하는 나의 코드와 달리,
칠해야하는 칸의 리스트 section을 기준으로 탐색을 진행한다.
이처럼 무엇을 기준으로 알고리즘을 작성하고 풀이할 것인가에 따라 알고리즘의 효율이 달라질 수 있으므로 설계에 주의할 필요가 있다.
09/12 대충 만든 자판
문제명 : 대충 만든 자판
레벨 : 1
문제유형 : 해시맵, 최대/최소
나의 풀이
각 문자별로 최소값을 저장하는 맵을 만들어 풀이하였다.
다른 사람들의 풀이도 비슷하여 설명생략.
function solution(keymap, targets) {
var answer = Array.from({length: targets.length}).fill(0);
const minMap = new Map()
keymap.forEach((str, index) => {
for(let i = 0; i < str.length; i++){
const char = str[i]
let value = i+1
if(minMap.has(char)) {
value = Math.min(minMap.get(char), value)
}
minMap.set(char, value)
}
})
for(let targetIndex = 0; targetIndex < targets.length; targetIndex++) {
const str = targets[targetIndex]
for(let i = 0; i < str.length; i++) {
const char = str[i]
if(minMap.has(char)) {
answer[targetIndex] += minMap.get(char)
} else {
answer[targetIndex] = -1
break
}
}
}
return answer;
}
09/12 카드 뭉치
문제명 : 카드 뭉치
레벨 : 1
문제유형 : 문자열, 1차원 배열
나의 풀이
- 처음엔 map으로 풀이했다가 문제의 제약조건 '배열의 순서를 고려'한다는 점으로 인해 다시 풀었다.
- 성능 향상을 위해 배열에서 shift를 실행하기 보다는 index를 사용하였다.
- 배열을 다루는 도중 '두 배열에 같은 단어가 있으면 로직이 복잡해지겠는데?' 라고 생각했으나... 다행히 문제의 제약조건에 '두 배열은 서로 다른 단어만 있다'고 하여 쉽게 풀렸다.
문제의 제약조건을 잘 읽자.
function solution(cards1, cards2, goal) {
var answer = "Yes";
// 잘못된 풀이 - 순서가 중요하기 때문에 Map을 사용할 수 없음.
// const map = new Map()
// goal.forEach((word)=> {
// if(!map.has(word)) map.set(word, 0)
// map.set(word, map.get(word)+1)
// })
// cards1.forEach((word)=>{
// if(map.has(word)) map.set(word, map.get(word)-1)
// })
// cards2.forEach((word)=>{
// if(map.has(word)) map.set(word, map.get(word)-1)
// })
// map.values(value => {if(value > 0) answer = "No"})
// return answer;
let card1Index = 0
let card2Index = 0
let goalIndex = 0
while(goalIndex < goal.length) {
const target = goal[goalIndex]
// cards1과 cards2에는 서로 다른 단어만 존재합니다.
if(cards1[card1Index] === target) {
goalIndex += 1
card1Index += 1
} else if(cards2[card2Index] === target) {
goalIndex += 1
card2Index += 1
} else {
break
}
}
if(goalIndex < goal.length) {
answer = "No"
}
return answer;
}
09/12 연속 펄스 부분 수열의 합
문제명 : 연속 펄스 부분 수열의 합
레벨 : 3
문제유형 : 1차원 배열, DP
나의 풀이 (틀림)
function solution(sequence) {
var answer = 0;
// 1, -1, 1, -1 로 진행된다고 가정하고, 해당 펄스배열의 절대값의 최대에 대해서만 계산
// memo 배열은 '해당 인덱스에서 끝나는 펄스 배열의 합 절대값이 최대인 경우' 를 저장. (저장할 때에는 절대값이 아닌 실제값을 저장)
const memo = Array.from({length:sequence.length}).fill(0)
sequence.forEach((element, index)=>{
const sign = index % 2 ? -1 : 1
const currentValue = (element * sign)
const memoCase = (memo[index-1] || 0) + (element * sign)
if(Math.abs(currentValue) > Math.abs(memoCase) ) {
memo[index] = currentValue
} else {
memo[index] = memoCase
}
answer = Math.max(answer, Math.abs(memo[index]))
})
return answer;
}
일단 배열의 길이가 1 ≤ sequence의 길이 ≤ 500,000와 같이 주어진 것을 보며
memo를 떠올린 것은 좋았고,
기준점도 잘 잡았고,
'펄스배열'이 문제 풀이에서 중요한 해답이 아니라는 것은 잘 파악했는데...
문제는 '펄스배열' 이기 때문에(혹은 절댓값 문제이기 때문에) 음수의 절대값이 최대일 때와 양수의 절대값이 최대일 때 등 음수와 양수 둘 다 살펴봐야 한다는 점을 놓쳤다.
맞는 풀이
최대값을 저장하는 dp, 최소값을 저장하는 dp를 만들고,
마지막에 Math.abs를 통해 절대값을 비교한다.
function solution(sequence) {
var answer = 0;
// 1, -1, 1, -1 로 진행된다고 가정하고, 해당 펄스배열의 절대값의 최대에 대해서만 계산
// memo 배열은 '해당 인덱스에서 끝나는 펄스 배열의 합 절대값이 최대인 경우' 를 저장. (저장할 때에는 절대값이 아닌 실제값을 저장)
const maxMemo = Array.from({length:sequence.length}).fill(0)
const minMemo = Array.from({length:sequence.length}).fill(0)
sequence.forEach((element, index)=>{
const sign = index % 2 ? -1 : 1
const currentValue = (element * sign)
const maxMemoCase = (maxMemo[index-1] || 0) + (element * sign)
const minMemoCase = (minMemo[index-1] || 0) + (element * sign)
minMemo[index] = Math.min(minMemoCase, currentValue)
maxMemo[index] = Math.max(maxMemoCase, currentValue)
// if(Math.abs(currentValue) > Math.abs(memoCase) ) {
// memo[index] = currentValue
// } else {
// memo[index] = memoCase
// }
answer = Math.max(answer, Math.abs(minMemo[index]), Math.abs(maxMemo[index]))
})
return answer;
}
누적합으로도 풀 수 있다.
09/13 인사고과
문제명 : 연속 펄스 부분 수열의 합
레벨 : 3
문제유형 : 1차원 배열
문제 풀이
문제 풀이의 아이디어
일단 틀렸다..ㅠ
1차원 배열이라 간단한 문제 같지만,
생각할거리가 많은 문제이다.
아래와 같이 작은 문제들로 쪼개어 생각해보는 것이 문제 해결의 열쇠이다.
-
완호의 등수를 구한다. => 모든 사원들의 합계 점수를 구한 후, 합계 점수가 큰 순으로 sort 한다.
-
동일한 점수는 동일한 등수로 친다.(가령 5, 3, 3 인 경우, 3점은 2등이다.) => 고려해야 하는 것은 완호의 등수만 알면 된다. 완호의 인덱스는 항상 0이므로, sort를 할 때 점수가 같으면, 인덱스가 가장 낮은 사람을 앞으로 오도록 sort를 실행하면 된다.
-
(예외처리) 이때,
어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다.. => 해당 조건에 해당하는 사원들은 배열의 맨 뒤로 보낸다. 점수를 '-1'로 바꾸는 식으로도 처리가 가능하다.
1번 작은 문제
먼저 1번 문제를 풀어보자.
점수의 합을 구한후 [점수, 인덱스]와 같은 형식의 요소를 가진 배열을 만든다.
이후 배열을 정렬한다.
function solution(scores) {
var answer = 0;
const coupledArray = scores.map((score, index)=> {
const totalScore = score.reduce((a,b)=>a+b)
return [totalScore, index]
// [ [ 4, 0 ], [ 5, 1 ], [ 5, 2 ], [ 5, 3 ], [ 3, 4 ] ]
}).sort((a,b) => b[0] - a[0])
console.log(coupledArray)
// [ [ 5, 1 ], [ 5, 2 ], [ 5, 3 ], [ 4, 0 ], [ 3, 4 ] ]
}
2번 작은 문제
2번 문제를 풀어보자.
위의 풀이에서는 이미 배열에서 높은 인덱스가 뒤로 가도록 배치었다.
그 이유는....map()에서 반환된 함수가 인덱스 순으로 이미 정렬되었기 때문이다.
정렬되어 있지 않다면
sort 함수의 콜백을 아래와 같이 변경해주자
.sort((a,b) => b[0] - a[0] || a[1] - b[1])
(양수와 음수는 trusy한 값이고, 0만이 falsy한 값이다. 따라서 a[0]과 b[0]이 같은 경우에만 뒤쪽의 a[1] - b[1]을 평가한다.)
3번 작은 문제
이제 중요한 3번 문제를 풀어보자. 시간 복잡도가 적잖게 걸릴 것만 같다..
일단 단순무식하게 출어본다.
function solution(scores) {
const coupledArray = scores
.map((score, index) => {
let totalScore = score.reduce((a, b) => a + b);
for (let i = 0; i < scores.length; i++) {
const targetScore = scores[i];
if (score[0] < targetScore[0] && score[1] < targetScore[1]) totalScore = -1;
}
return [totalScore, index];
})
// [ [ 5, 1 ], [ 5, 2 ], [ 5, 3 ], [ 4, 0 ], [ -1, 4 ] ]
.sort((a, b) => b[0] - a[0] || a[1] - b[1]); // [ [ 5, 1 ], [ 5, 2 ], [ 5, 3 ], [ 4, 0 ], [ 3, 4 ] ]
return coupledArray.findIndex(e => !e[1]) + 1
}
정렬이 잘 되는 것을 알 수 있다. 제출해보면... 한가지 틀렸다.
const wanhoIndex = coupledArray.findIndex(e => !e[1])
return coupledArray[wanhoIndex][0] >= 0? wanhoIndex + 1 : -1
...완호가 -1일때에는 -1을 반환해줘야...
정답풀이
해당 문제의 시간복잡도가 매우 민감하게 설정되어 있는 것으로 보인다.
if문만 넣어줘도 통과가 되지 않던 테케가 통과되는 등이 발생한다.
접근 방법을 달리 할 필요가 있다.
크크루쿠쿠 님 블로그 정답을 참고하자.
def solution(scores):
answer = 1
target = scores[0]
target_score = sum(scores[0])
scores.sort(key=lambda x: (-x[0], x[1]))
threshold = 0
for score in scores:
if target[0] < score[0] and target[1] < score[1]:
return -1
if threshold <= score[1]:
if target_score < score[0] + score[1]:
answer += 1
threshold = score[1]
return answer
function solution(scores) {
let answer = 1;
let target = scores[0];
let targetScore = target.reduce((a, b) => a + b);
scores.sort((a, b) => b[0] - a[0] || a[1] - b[1]);
let threshold = 0;
for (let i = 0; i < scores.length; i++) {
const score = scores[i];
if (target[0] < score[0] && target[1] < score[1]) {
return -1;
}
if (threshold <= score[1]) {
if (targetScore < score[0] + score[1]) {
answer += 1;
}
threshold = score[1];
}
}
return answer;
}
09/14 미로 탈출
문제명 : 미로 탈출
레벨 : 2
문제유형 : 2차원 배열, BFS
나의 풀이
평범한 que와 while문으로 풀었다. (BFS)
하지만 처음 제출에서는 오답이었는데...
-
visited 문을 초기화한다! 이때 visited 문에는 weight를 담고 있어야 "지금껏 방문했던 길이보다 작을 때에만 que에 넣는다" 와 같은 방식으로 초기화한다.
-
2차원 배열을 초기화하는 방법을 잘 익히자.
오답코드const exitVisited = Array.from({length: maps.length}).fill(Array.from({length: maps[0].length}).fill(100*100 + 1))
주어진 코드에서 문제는 내부 fill 호출 때 동일한 배열 객체를 공유한다는 것입니다. 이렇게 하면 모든 행이 같은 배열을 참조하게 되므로 한 행을 수정하면 모든 행이 수정됩니다. 이를 해결하기 위해 각 행을 별도의 배열로 초기화해야 합니다. - ChatGPT
수정된 코드 const exitVisited = Array.from({ length: maps.length }, () => Array.from({ length: maps[0].length }, () => 100 * 100 + 1) );
function solution(maps) {
var answer = 0;
let startPosition
for(let row = 0; row < maps.length; row++) {
const string = maps[row]
for(let col = 0; col < string.length; col++) {
if(string[col] === "S") {
startPosition = [row, col]
break
}
}
if(startPosition) break
}
const deltas = [[1,0], [0,1], [0,-1], [-1,0]]
let leverPosition
const leverQue = []
// const leverVisited = Array.from({length: maps.length}).fill(Array.from({length: maps[0].length}).fill(100*100 + 1))
const leverVisited = Array.from({ length: maps.length }, () =>
Array.from({ length: maps[0].length }, () => 100 * 100 + 1)
);
leverQue.push([startPosition, 0]) //[[x, y], w]
leverVisited[startPosition[0]][startPosition[1]] = 0
while(leverQue.length && !leverPosition) {
const [[crrRow, crrCol], crrWeight] = leverQue.shift()
const canMoveArray = ["O", "E", "S"]
deltas.forEach((delta)=>{
const [dX, dY] = delta
const newRow = crrRow+dX
const newCol = crrCol+dY
const newWeight = crrWeight + 1
if(!maps[newRow]) return
if(!maps[newRow][newCol]) return
if(canMoveArray.includes(maps[newRow][newCol])) {
if(newWeight < leverVisited[newRow][newCol]) {
leverQue.push([[newRow, newCol], newWeight])
leverVisited[newRow][newCol] = newWeight
}
} else if (maps[newRow][newCol] === "L") {
answer += newWeight
leverPosition = [newRow, newCol]
}
})
}
if(!leverPosition) {
console.log("레버못가")
return -1
}
let exitPosition
const exitQue = []
// const exitVisited = Array.from({length: maps.length}).fill(Array.from({length: maps[0].length}).fill(100*100 + 1))
const exitVisited = Array.from({ length: maps.length }, () =>
Array.from({ length: maps[0].length }, () => 100 * 100 + 1)
);
exitQue.push([leverPosition, 0]) //[[x, y], w]
exitVisited[leverPosition[0]][leverPosition[1]] = 0
while(exitQue.length && !exitPosition) {
const [[crrRow, crrCol], crrWeight] = exitQue.shift()
const canMoveArray = ["O", "L", "S"]
deltas.forEach((delta)=>{
const [dX, dY] = delta
const newRow = crrRow+dX
const newCol = crrCol+dY
const newWeight = crrWeight + 1
if(!maps[newRow]) return
if(!maps[newRow][newCol]) return
if(canMoveArray.includes(maps[newRow][newCol])) {
if(newWeight < exitVisited[newRow][newCol]) {
exitQue.push([[newRow, newCol], newWeight])
exitVisited[newRow][newCol] = newWeight
}
} else if (maps[newRow][newCol] === "E") {
answer += newWeight
exitPosition = [newRow, newCol]
}
})
}
if(!exitPosition) return -1
return answer;
}
09/16 최댓값과 최솟값
function solution(s) {
let min = Number.MAX_SAFE_INTEGER
let max = Number.MIN_SAFE_INTEGER
s.split(" ").forEach(e=> {
min=Math.min(e, min)
max=Math.max(e, max)
})
return min+" "+max;
}
09/16 정수 삼각형
function solution(triangle) {
var answer = 0;
const newTriangle= []
triangle.forEach(((nums, row)=>{
const newRow = nums.map((num, col)=>{
const prevRow = newTriangle[row-1]
if(prevRow) {
const prevLeft = prevRow[col-1] || 0
const prevRight = prevRow[col] || 0
return num + Math.max(prevLeft, prevRight)
} else return num
})
newTriangle.push(newRow)
}))
answer = Math.max(...newTriangle.at(-1))
return answer;
}
효율성 테스트
테스트 1 〉 통과 (6.25ms, 41.2MB)
테스트 2 〉 통과 (5.28ms, 40.2MB)
테스트 3 〉 통과 (27.87ms, 41.3MB)
테스트 4 〉 통과 (6.18ms, 41.3MB)
테스트 5 〉 통과 (7.18ms, 40.9MB)
테스트 6 〉 통과 (7.08ms, 42.4MB)
테스트 7 〉 통과 (6.58ms, 41.8MB)
테스트 8 〉 통과 (5.80ms, 40.7MB)
테스트 9 〉 통과 (9.61ms, 41MB)
테스트 10 〉 통과 (6.81ms, 41.7MB)
삼각형을 한 단계씩 내려가며,
이전 삼각형의 좌, 우 중에서 더 큰 값을 더해간다.
이렇게 새로운 삼각형을 만든 후, 마지막 단계의 가장 큰 값을 리턴하는 간단한 DP 문제이다.
해당 답안의 공간 복잡도를 줄여보자.
'현재의 단계'를 알기 위해서는 '직전의 단계'만 알면 된다.
function solution(triangle) {
var answer = 0;
// const newTriangle= []
let prevRow
triangle.forEach(((nums)=>{
const newRow = nums.map((num, col)=>{
// const prevRow = newTriangle[row-1]
if(prevRow) {
const prevLeft = prevRow[col-1] || 0
const prevRight = prevRow[col] || 0
return num + Math.max(prevLeft, prevRight)
} else return num
})
prevRow = newRow
}))
// answer = Math.max(...newTriangle.at(-1))
answer = Math.max(...prevRow)
return answer;
}
테스트 1 〉 통과 (5.72ms, 41.3MB)
테스트 2 〉 통과 (5.31ms, 40.2MB)
테스트 3 〉 통과 (7.07ms, 42MB)
테스트 4 〉 통과 (6.62ms, 41.3MB)
테스트 5 〉 통과 (5.66ms, 40.9MB)
테스트 6 〉 통과 (6.29ms, 42MB)
테스트 7 〉 통과 (6.65ms, 41.8MB)
테스트 8 〉 통과 (5.46ms, 40.8MB)
테스트 9 〉 통과 (5.87ms, 40.9MB)
테스트 10 〉 통과 (6.01ms, 41.7MB)
...별 차이가 없다.
09/17 등굣길
등굣길
간단한 DP문제이다.
Greedy한 성격이 짙어서 2차원 배열 greedy 문제로 보아도 무방하다.
그리디 문제를 풀 때에는 문제의 요건을 잘 맞추도록 주의한다.
function solution(m, n, puddles) {
var answer = 0;
// 2차원 배열을 초기화 할 때에는 Array.from의 두번째에 맵 함수를 넘겨준다.
const table = Array.from({length: n+1}, (v, col)=> {
// 이때 x좌표 혹은 y좌표가 0인 경우에는 -1로 초기화하였다.
return Array.from({length:m+1}, (v, row)=> (col && row)? 0 : -1)
})
// 문제의 조건에 맞에 [x, y]의 위치를 정확히 다룬다.
puddles.forEach((pos)=> {
const [x, y] = pos
table[y][x] = -1
})
// (매우 중요)시작지점을 1로 초기화 한다.
table[1][1] = 1
// (최적화) 우측 상단에서부터 우측으로 쭉쭉 완전탐색한다.
for(let row = 1; row < n+1; row++) { //이때 2차원 배열을 m+1 * n+1까지 초기화했음을 상기한다.
for(let col = 1; col < m+1; col++) {
if(table[row][col] < 0) continue
const left = table[row][col - 1]
const top = table[row - 1][col]
if(left > 0) table[row][col] += left
if(top > 0) table[row][col] += top
// (중요) 문제의 효율성 조건에 맞게 1000000007로 나눈 나머지를 저장한다.
table[row][col] %= 1000000007
}
}
answer = table.at(-1).at(-1)
return answer;
}
09/18 억억단을 외우자
나의 풀이(오답)
수학적 원리를 이용하는 간단한 문제인데,
greedy하게 푸니 O(n^2)의 시간 복잡도가 나온다.
function solution(e, starts) {
var answer = [];
// n이 등장하는 갯수는, 특성 수 S를 만드는 약수의 갯수와 같다.
// 가령, 6은 1, 2, 3, 6의 약수를 가져 총 4번 등장한다.
// 4는 1, 2, 4의 약수를 가져 총 3번 등장한다.
starts.forEach(start=>{
// 나온 갯수를 담은 배열을 초기화 한다.
const counts = Array.from({length: e + 1}, ()=> 0)
for(let i = start; i < e + 1; i++) { // s부터 e까지의 수 중
for(let j = 0; j < e + 1; j++) { // 억억단의 단 수로 나누었을 때
if(i%j === 0) { // 0이 되면 약수이므로 counts배열에 추가한다.
counts[i] += 1
} else if (j > i) break;
}
}
let maxValue = 0
let maxIndex = 1 //가장 많이 나온 수를 찾아 담는다.
counts.forEach((value, index)=> {
if(value > maxValue) {
maxValue = value
maxIndex = index
}
})
answer.push(maxIndex)
})
return answer;
}
성능 개선
function solution(e, starts) {
var answer = [];
// n이 등장하는 갯수는, 특성 수 S를 만드는 약수의 갯수와 같다.
// 가령, 6은 1, 2, 3, 6의 약수를 가져 총 4번 등장한다.
// 4는 1, 2, 4의 약수를 가져 총 3번 등장한다.
const counts = Array.from({length: e + 1}, ()=> 0)
for (let i = 2; i <= e; i++) {
for (let j = 1; j <= Math.min(Math.floor(e / i) + 1, i); j++) {
if(i !== j && (i * j) < e+1) counts[i * j] += 2;
}
}
for (let i = 1; i <= Math.floor(Math.sqrt(e)); i++) {
if((i ** 2) < e+1) counts[i ** 2] += 1;
}
starts.forEach(start=>{
let maxValue = 0
let maxIndex = 1 //가장 많이 나온 수를 찾아 담는다.
for(let index = start; index <= e+1; index++){
const value = counts[index]
// counts.slice(start).forEach((value, index)=> {
if(value > maxValue) {
maxValue = value
maxIndex = index
}
// })
}
answer.push(maxIndex)
})
return answer;
}
파이썬 풀이를 이용해서 실행해보았다.
테스트케이스 8번까지 효율성 테스트를 통과한다.
9, 10번은 노가다로 테스트한다길래 여기까지만 개선하고 패스하는걸로...
09/18 호텔 대실
1차원 배열과 문자열을 이용하는 문제이다.
더 효율적인 방법은 있겠으나, 한 번 이상의 정렬이 필수적이라는 점에서 O(nlogn)의 시간복잡도를 가진다.
function solution(book_time) {
var answer = 0;
const newArray = book_time.map(times=>{
return times.map((string, index)=>{
const [hour, min] = string.split(":").map(e=>~~e)
// 시간 * 60해서 분으로 교체
// index * 10 해서 청소시간 10분 추가
return hour*60 + min + index*10
})
})
newArray.sort((a, b)=>{
const startGap = a[0] - b[0]
if(startGap) return startGap
else return a[1] - b[1]
})
const rooms = []
newArray.forEach((times)=>{
const [start, end] = times
let haveRoom = false
for(let i = 0; i < rooms.length; i++){
const [prevStart, prevEnd] = rooms[i]
if(prevEnd <= start) {
rooms[i] = [start, end]
haveRoom = true
break
}
}
if(!haveRoom) rooms.push(times)
})
return rooms.length;
}
09/19 다음 큰 숫자
진법 계산이 가능하면 쉽게 풀이할 수 있는 문제이다.
문제를 풀 때에 2진법 문자열을 얻는 방법이 생각나지 않아 getBinCount라는 함수를 만들었다.
이후엔 n은 1,000,000 이하의 자연수라는 점에서 착안하여, n에서부터 1씩 증가하며 이진법의 1의 갯수가 일치하는 답을 answer에 담았다.
(수학적으로 접근하면 O(n)보다 더 빠른 답이 나올 수 있을 것이라 생각한다.)
function solution(n) {
var answer = 0;
const getBinCount = (n) => {
let bin = ""
let count = 0
let pow = 0
let temp = n
while(true) {
const powNum = 2**pow
if(n < powNum) break
pow++
}
pow--
while(pow >= 0) {
const gap = temp - 2**pow
if(gap >= 0){
bin = bin+"1"
count += 1
temp = gap
} else {
bin = bin+"0"
}
pow--
}
return count
}
const crrNum = getBinCount(n)
let temp = n+1
while(true) {
const newNum = getBinCount(temp)
if(newNum===crrNum) {
answer = temp
break
} else temp++
}
return answer;
}
참고로 Number.prototype.toString(진법) 특정 진법으로 변환된 문자가 반환된다.
function solution(n) {
var answer = 0;
const getBinCount = (n) => {
return n
.toString(2) // 2진 문자열을
.split("") // 배열로 만들고
.reduce((a,b)=> a+~~b, 0) // 모든 요소의 총합을 반환한다. (시작값 0 필수!)
}
const crrNum = getBinCount(n)
let temp = n+1
while(true) {
const newNum = getBinCount(temp)
if(newNum===crrNum) {
answer = temp
break
} else temp++
}
return answer;
}
09/20 뒤에 있는 큰 수 찾기
뒤에 있는 큰 수 찾기
1일 1알고를 위해 밤 11시 30분에 급하게 풀기 시작한 문제.
급하다고 그리디하게 풀면 시간 초과가 발생한다. 아래는 for문을 두 번 돌리는 풀이이다.(투포인터를 적용해서 풀이를 시도해도 결과적으로는 아래와 같은 구조가 되어 시간 복잡도가 같아진다.)
function solution(numbers) {
var answer = [];
for(let i = 0; i < numbers.length; i++) {
let biggerNumber = -1
const num = numbers[i]
for(let j = i+1; j < numbers.length; j++) {
const nextNumber = numbers[j]
if(nextNumber > num) {
biggerNumber = nextNumber
break
}
}
answer.push(biggerNumber)
}
return answer;
}
혹시나 반대로도 풀어봤는데 역시나 더 성능이 안좋아졌다
function solution(numbers) {
var answer = [...numbers]
for(let i = numbers.length-1; i>=0; i--) {
for(let j = i - 1; j>=0; j--) {
const crr = numbers[i]
const prev = numbers[j]
if(crr > prev) answer[j] = crr
}
}
for(let i = 0; i < numbers.length; i++) {
if(answer[i]===numbers[i]) {
answer[i] = -1
}
}
return answer;
}
그 밖에 DP, Stack 등을 사용해야 문제를 풀이할 수 있다고 한다...
아래는 스택을 이용한 풀이이다. 정답 출처
function solution(numbers) {
const length = numbers.length;
const answer = Array.from({length}, () => -1);
const stack = [];
for (let i = length - 1; i >= 0; i--) {
// 끝에서부터 순회 시작
const crrNum = numbers[i]
// 스택의 마지막 값이 현재값 보다 작다면, Stack에서 값을 제외함
while (stack.length !== 0 && crrNum >= stack.at(-1)) stack.pop();
// 만일 현재값보다 큰 값을 만나면, answer 테이블을 갱신함.
if (stack.length !== 0) answer[i] = stack.at(-1);
// 현재 값을 스택에 저장함.
stack.push(crrNum);
}
return answer;
}
입력값 〉 [9, 1, 5, 3, 6, 2]
기댓값 〉 [-1, 5, 6, 6, -1, -1]
실행 결과 〉 테스트를 통과하였습니다.
출력 〉 ---------------
1회차
현재값 : 2
기존스택 : []
stack에서 제외된 값 : []
실행결과 stack : [2]
실행결과 answer : [-1,-1,-1,-1,-1,-1]
---------------
2회차
현재값 : 6
기존스택 : [2]
stack에서 제외된 값 : [2]
실행결과 stack : [6]
실행결과 answer : [-1,-1,-1,-1,-1,-1]
---------------
3회차
현재값 : 3
기존스택 : [6]
stack에서 제외된 값 : []
실행결과 stack : [6,3]
실행결과 answer : [-1,-1,-1,6,-1,-1]
---------------
4회차
현재값 : 5
기존스택 : [6,3]
stack에서 제외된 값 : [3]
실행결과 stack : [6,5]
실행결과 answer : [-1,-1,6,6,-1,-1]
---------------
5회차
현재값 : 1
기존스택 : [6,5]
stack에서 제외된 값 : []
실행결과 stack : [6,5,1]
실행결과 answer : [-1,5,6,6,-1,-1]
---------------
6회차
현재값 : 9
기존스택 : [6,5,1]
stack에서 제외된 값 : [1,5,6]
실행결과 stack : [9]
실행결과 answer : [-1,5,6,6,-1,-1]
09/21 숫자 변환하기
숫자 변환하기
'최소 횟수'를 찾는 문제이니 BFS로 풀이하면 금방 풀린다.
이때 visited를 통해 점검하는 것이 필수다. (visited를 넣지 않으면 같은 값을 계속 push해서 시간초과가 된다.)
function solution(x, y, n) {
var answer = -1;
// 최소니까 BFS로 찾으면 되지 않음?
// 정석대로 BFS로 찾으니까 내용이 너무 길어짐.
// const que = []
// que.push([x, 0]) //[값, Weight]
// while(que.length && que.length < 10) {
// const [crrValue, crrWeight] = que.shift()
// if(crrValue===y) {
// answer = crrWeight
// break;
// }
// const newWeight = crrWeight+1
// const newValues = [x*2, x*3, x+n]
// newValues.forEach(value=> {
// console.log(que)
// if(value <= y) que.push([value, newWeight])
// })
// }
// y에서부터 값을 찾아가는 것으로 하자.
const que = []
// ---내용추가---
const set = new Set()
// -------------
que.push([y, 0])
while(que.length){
const [crrValue, crrWeight] = que.shift()
if(crrValue === x) {
answer = crrWeight
break
}
const newWeight = crrWeight+1
const newValues = [crrValue-n, crrValue/2, crrValue/3]
newValues.forEach(value => {
if(!set.has(value) && value%1===0 && value >= x) {
que.push([value, newWeight])
set.add(value)
}
})
}
return answer;
}
09/21 시소 짝꿍
function solution(weights) {
var answer = 0;
weights.sort((a,b)=>a-b)
weights.forEach((crr,i)=>{
const crrArray=[crr, crr*(4/3), crr*(3/2), crr*(4/2)]
for(let j = i+1; j < weights.length; j++) {
const target = weights[j]
if(crrArray.includes(target)) answer++
}
})
return answer;
}
O(n^2)으로 풀었더니 에러가 난다.