티스토리 뷰
추석 트래픽 -- 2018 KAKAO BLIND RECRUITMENT
function solution(lines) {
const result = [],
arr = [];
lines.forEach((val) => {
const spl = val.split(" "),
time = spl[1].split(":"),
hour = time[0] * 1,
min = time[1] * 1,
sec = time[2] * 1,
end = hour * 3600 + min * 60 + sec,
duration = spl[2].substr(0, spl[2].length - 1) * 1,
start = end - duration + 0.001;
arr.push([start, end]);
});
const logArr = [...new Set(arr.flat())];
logArr.sort((a, b) => a - b);
for (let i = 0; i < logArr.length; i++) {
const startLog = logArr[i],
endLog = logArr[i] + 1;
let count = 0;
for (let j = 0; j < arr.length; j++) {
const start = arr[j][0],
end = arr[j][1];
if (
(startLog <= start && start < endLog) ||
(startLog <= end && end < endLog) ||
(start < startLog && end >= endLog)
) {
count++;
}
}
result.push(count);
}
return Math.max(...result);
}
너무 어렵게 풀었다.....
2016-09-15 00:00:00.000 이거를 바로 date객체에 넣을 수 있는지 몰랐어서 다른 방법으로 풀었다.
각각의 처리시작 시간과 끝 시간에만 처리량이 바뀐다는 것을 먼저 알아야 한다.
시간복잡도를 줄이는 방법은 로그 배열 하나를 더 만드는 것이다. 시간 0.001 더해주고 부등호에 =을 붙이는 여부도 신경써서 코딩해야 한다.
조금 자세히 설명하면 먼저 arr에 시작시간과 끝시간으로 2차원 배열을 만든다. 그리고 이를 이용해 logArr을 만든다. 왜냐하면 로그배열과 비교해서 처리량을 계산하면 시간 복잡도가 줄어들기 때문이다. if문은 코드를 보면 이해할 수 있다.
programmers.co.kr/learn/courses/30/lessons/17676
2xn 타일링
function solution(n) {
const answer=[1,2];
for(let i=2;i<n;i++){
answer[i]=(answer[i-1]+answer[i-2]) % 1000000007;
}
return answer[n-1];
}피보나치 수열인지 파악하는게 어렵다... 코드는 그냥 피보나치 수열 푸는대로 풀면 끝
programmers.co.kr/learn/courses/30/lessons/12900
N으로 표현 -- 동적계획법(Dynamic Programming)
function solution(N, number) {
const set = Array(9)
.fill()
.map(() => new Set());
for (let i = 1; i <= 8; i++) {
set[i].add(+String(N).repeat(i));
for (let j = 1; j < i; j++) {
for (let a of set[j]) {
for (let b of set[i - j]) {
set[i].add(a + b);
set[i].add(a - b);
set[i].add(a * b);
set[i].add(a / b);
}
}
}
if (set[i].has(number)) return i;
}
return -1;
}구글링해서 힌트를 얻었다.. 난 멍청해
먼저 set을 만들어놓고 첫번째 for문(i)이 돌아갈 때 먼저 N, NN, NNN~~을 집어 넣는다. 그리고 N이 i번 사용되는 집합은 set[j]와 set[i-j]의 연산 결과의 집합이다. 따라서 이를 더해주고 has로 number가 있는지 확인하고 있다면 return i, for문이 끝나도 없다면 최솟값이 8보다 크므로 -1을 return
옛날에는 코드 쓰는법이였다면 이젠 진짜 알고리즘 문제같다...
programmers.co.kr/learn/courses/30/lessons/42895
풍선 터트리기
런타임 에러
function solution(a) {
if(a.length<=3) return a.length;
let answer=0;
for(let i=0;i<a.length;i++){
remain(a,i) && answer++
}
return answer;
}
function remain(arr,idx){
if(idx===0 || idx===arr.length-1) return true;
const left=arr.slice(0,idx), right=arr.slice(idx+1),
left_min=Math.min(...left),
right_min=Math.min(...right),
current=arr[idx];
if(current<left_min || current<right_min ) return true;
return false;
}시간복잡도 O(3n)
function solution(a) {
const left = [],
right = [];
let answer = 2;
(left[0] = a[0]), (right[a.length - 1] = a[a.length - 1]);
for (let i = 1; i < a.length; i++) {
left.push(Math.min(left[i - 1], a[i]));
}
for (let i = a.length - 2; i >= 0; i--) {
right[i] = Math.min(right[i + 1], a[i]);
}
for (let i = 1; i < a.length - 1; i++) {
if (a[i] < left[i - 1] || a[i] < right[i + 1]) answer++;
}
return answer;
}O(n)으로도 풀 수 있다고 하는데 패스...
최대 최소를 저렇게 구해서 시간복잡도를 줄였다. 아니 코드를 보고 알앗다. 왜 저걸 생각을 못할까...
수학문제 처음에 4번푸는 느낌...
네트워크 -- 깊이/너비 우선 탐색(DFS/BFS)
function solution(n, computers) {
const result=[];
for(let i=0;i<n;i++){
if(!result.flat().includes(i)){
result.push(dfs(i,[i]));
}
}
return result.length;
function dfs(idx,arr){
for(let i=0;i<n;i++){
if(idx===i) continue;
if(computers[idx][i]===1 && !arr.includes(i)){
arr.push(i);
dfs(i,arr);
}
}
return arr;
}
}dfs만 쓰면 간단히 해결
programmers.co.kr/learn/courses/30/lessons/43162
자물쇠와 열쇠
const keyRotate = (key, key_len) => {
const result = Array(key_len)
.fill(null)
.map(() => Array(key_len).fill(null));
for (let i = 0; i < key.length; i++) {
for (let j = 0; j < key.length; j++) {
result[i][j] = key[key_len - 1 - j][i];
}
}
return result;
};
const keyExpand = (key, key_len, lock_len) => {
const result = [];
for (let i = 0; i < lock_len - 1; i++) {
result.push(Array(lock_len * 3 - 2).fill(0));
}
for (let i = 0; i < key_len; i++) {
result.push(
Array(lock_len - 1)
.fill(0)
.concat(key[i])
.concat(Array(lock_len - 1).fill(0))
);
}
for (let i = 0; i < lock_len - 1; i++) {
result.push(Array(lock_len * 3 - 2).fill(0));
}
return result;
};
const keyCorrect = (real_key, lock, lock_len) => {
for (let i = 0; i < lock_len; i++) {
for (let j = 0; j < lock_len; j++) {
if (real_key[i][j] + lock[i][j] !== 1) return false;
}
}
return true;
};
function solution(key, lock) {
const key_len = key.length;
const lock_len = lock.length;
for (let r = 0; r < 4; r++) {
key = keyRotate(key, key_len);
// console.log("key", key);
const key_expand = keyExpand(key, key_len, lock_len);
// console.log("key_expand", key_expand);
const key_expand_len = key_expand.length;
for (let i = 0; i <= key_expand_len - lock_len; i++) {
for (let j = 0; j <= key_expand_len - lock_len; j++) {
const real_key = [];
for (let k = i; k < i + lock_len; k++) {
real_key.push(key_expand[k].slice(j, j + lock_len));
}
// console.log("reak_key",real_key);
if (keyCorrect(real_key, lock, lock_len)) return true;
}
}
}
return false;
}
하루 동안 이 문제를 못풀었다. 이게 말이되나...풀릴듯말듯 계속 안풀려서 처음부터 차근차근 다시 풀었다.
1. 먼저 회전 함수를 만들어야 한다. 이건 그냥 생각을 잘해야한다. 설명할 수 없음
key를 4번 회전 시켜서 결국 4번째 회전한 key는 처음 key가 된다. 3번 돌려도 되지만 코드가 더 길어져서 그냥 이렇게 풀었다.
2. key를 확장 시켜야 한다. 원래 key를 가운데에 넣고 나머지 부분을 0으로 채우는 것이다. 0은 홈부분이므로 이렇게 해도 상관이 없다. 여기서도 실수를 했었는데 늘리는게 lock의 길이만큼 늘려야 한다.
key가 m*m, lock이 n*n이라고 할 때 확장된 행렬은 (2*m+n-2)*(2*m+n-2)이다.
여기서 주의할게 key와 lock의 크기가 다를때이다. 바로 이해가 가지 않는다면 그림을 그려보면 쉽다.
key가 lock보다 작을때 같을때 클때 3번을 비교해보면 이해가 될 것이다.
아래 그림에서는 key의 길이가 1이고 lock의 길이가 3일때이다. 이 그림으로 예시를 들면
i,j가 0,0일때는 원래 key가 확장key의 2,2 자리에 오게 되고
i,j가 1,0일때는 원래 key가 확장 key의 1,2 자리에 오게 된다.
이런식으로 최소한의 경우로 모든 경우의 수를 구하는 것이다. 나는 lock의 길이가 아니라 key의 그림만큼 확장시켜서 처음에 틀렸었다. 그런데 key가 작은경우를 그려보고 틀렸다는 것을 깨달았다.
3. 이제 key와 lock을 비교하면 된다. 여기서는 어려운게 없는데 문제를 제대로 읽지 않거나 대충 풀면 틀리기 쉽다. 특히나 실제 시험에서 실수를 하면 찾기 어려울 것으로 보인다.
열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
위 설명을 보면 돌기와 돌기가 만나면 안되고 돌기와 홈부분이 만나는 경우에만 성립한다. 따라서 비트연산으로 계산을 하면 틀린다. 그냥 두개를 더해서 1이 나오는지 확인하면 된다. 그리고 만약 1이아니라면 그 자리에서 return false를 하면 된다.
카카오문제가 점점더 어려워지는것같다.... 이건 초반문젠데 3번?인가? 뒤에 문제보다 훨씬 오래걸려서 풀렸다.
programmers.co.kr/learn/courses/30/lessons/60059
가장 먼 노드 -- 그래프
실패.... 테케에서 하나가 시간초과 떴다. bfs사용
function solution(n, edge) {
const visited = [0, 0];
const queue = [1];
while (queue.length) {
const vertex = queue.shift();
for (let i = 0; i < edge.length; i++) {
if (edge[i].includes(vertex)) {
const adj_vertex = edge[i].filter((val) => val !== vertex)[0];
if (!visited[adj_vertex]) {
queue.push(adj_vertex);
visited[adj_vertex] = visited[vertex] + 1;
}
edge.splice(i, 1);
i--;
}
}
}
const max = Math.max(...visited);
return visited.filter((val) => val === max).length;
}
includes를 안쓰고 조금 더 지저분하게 코드를 썼더니 통과.... 이게 맞나.. 수정
function solution(n, edge) {
const visited = [0, 0];
const queue = [1];
while (queue.length) {
const vertex = queue.shift();
for (let i = 0; i < edge.length; i++) {
if (edge[i][0] === vertex && !visited[edge[i][1]]) {
queue.push(edge[i][1]);
visited[edge[i][1]] = visited[vertex] + 1;
edge.splice(i, 1);
i--;
} else if (edge[i][1] === vertex && !visited[edge[i][0]]) {
queue.push(edge[i][0]);
visited[edge[i][0]] = visited[vertex] + 1;
edge.splice(i, 1);
i--;
}
}
}
const max = Math.max(...visited);
return visited.filter((val) => val === max).length;
}
programmers.co.kr/learn/courses/30/lessons/49189#
섬 연결하기 -- 탐욕법(Greedy)
function solution(n, costs) {
costs.sort((a, b) => a[2] - b[2]);
const parent = new Array(n).fill().map((v, i) => i);
const arr = [];
for (let i = 0; i < costs.length; i++) {
if (!findParent(parent, costs[i][0], costs[i][1])) {
unionParent(parent, costs[i][0], costs[i][1]);
arr.push(costs[i]);
}
if (arr.length === n - 1) return arr.reduce((acc, cur) => acc + cur[2], 0);
}
}
function getParent(parent, element) {
if (parent[element] === element) return element;
return (parent[element] = getParent(parent, parent[element]));
}
function unionParent(parent, a, b) {
a = getParent(parent, a);
b = getParent(parent, b);
a<b ? parent[b]=a : parent[a]=b;
}
function findParent(parent, a, b) {
a = getParent(parent, a);
b = getParent(parent, b);
return a === b;
}크루스칼 알고리즘, union find 알고리즘으로 풀었다.... 힘들었다
크루스칼 알고리즘 : 가중치를 기준으로 간선을 정렬한 후에 MST가 될때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식
가중치가 낮은 간선들을 하나씩 추가해보자. 그러다보면 사이클이 형성된다. 사이클을 만드는 간선은 그래프에 추가하지 않는다.
간선의 수+1=정점의 수
크루스칼 알고리즘 핵심
1. 가중치를 기준으로 간선을 오름차순으로 정렬한다.
2. 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.
3. 사이클을 형성하는 간선은 추가하지 않는다.
4. 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.
(mst는 최소신장트리)
이때 사이클을 형성하는지 확인할려면 union find 알고리즘이 필요하다.
부모를 합쳐서 부모가 같은지 확인을 하면 된다.
programmers.co.kr/learn/courses/30/lessons/42861
정수 삼각형 -- 동적계획법(Dynamic Programming)
dfs 사용했다가 시간 초과
function solution(triangle) {
let result = [];
plus([[triangle[0][0], 0]]);
return Math.max(...result);
function plus(arr) {
console.log(arr);
if (arr.length === triangle.length) {
result.push(arr.map((i) => i[0]).reduce((acc, cur) => acc + cur, 0));
return;
}
plus([
...arr,
[triangle[arr.length][arr[arr.length - 1][1]], arr[arr.length - 1][1]],
]);
plus([
...arr,
[
triangle[arr.length][arr[arr.length - 1][1] + 1],
arr[arr.length - 1][1] + 1,
],
]);
}
}수정
function solution(triangle) {
let result = [[triangle[0][0]]];
for (let i = 1; i < triangle.length; i++) {
let arr = [];
for (let j = 0; j < triangle[i].length; j++) {
let previous;
if (j === 0) previous = result[i - 1][j];
else if (j === triangle[i].length - 1) previous = result[i - 1][j - 1];
else previous = Math.max(result[i - 1][j - 1], result[i - 1][j]);
arr.push(previous + triangle[i][j]);
}
result.push(arr);
}
return Math.max(...result[result.length - 1]);
}처음에 각 행들중 최대값을 찾는다고 전체 최대값을 찾는게 아니니 dfs를 사용했다. 처음 배열을 찾은 후 처음부터 찾는게 아니라 저장된 배열부터 찾는거라 문제가 없다고 생각했다. 그런데 생각해보니
이렇게 첫번째 열과 마지막 열을 제외하면 둘 중 max값을 선택해서 더 효율적인 코드를 짤 수 있었다.
코드자체는 어렵지 않다.
programmers.co.kr/learn/courses/30/lessons/43105
단어 변환 -- 깊이/너비 우선 탐색(DFS/BFS)
function solution(begin, target, words) {
if (!words.includes(target)) return 0;
let arr = [];
dfs(begin, words, 0);
function dfs(begin, words, count) {
// console.log(begin, words, count);
if (begin === target) {
arr.push(count);
return;
}
for (let i = 0; i < words.length; i++) {
let num = 0;
for (let j = 0; j < begin.length; j++) {
if (words[i][j] === begin[j]) num++;
}
if (num === begin.length - 1) {
dfs(words[i], words.slice(0, i).concat(words.slice(i + 1)), count + 1);
}
}
}
return arr.length > 0 ? Math.min(...arr) : 0;
}dfs로 풀었다. 좀 더 깔끔하게 풀 수 있을것같은데 나중에 생각해보겠다. 딱히 설명할게 없다.
programmers.co.kr/learn/courses/30/lessons/43163
단속 카메라 -- 탐욕법
function solution(routes) {
let answer=0;
routes.sort((a,b)=>a[1]-b[1]);
let camera=-30001;
for (let route of routes){
if(camera<route[0]){
camera=route[1];
answer++;
}
}
return answer;
}생각하는게 조금 어려웠다. 그림을 그려서 생각해보면 맨 처음 설치해야 할 카메라는 routes 중에서 끝나는 부분임을 알 수 있다. 그러므로 끝나는부분으로 routers를 정렬하고 시작지점이 카메라보다 작거나 같으면 이미 카메라에 찍혔으므로 넘어가고 아닌부분만 처리해주면 된다.
programmers.co.kr/learn/courses/30/lessons/42884
디스크 컨트롤러 -- 힙
function solution(jobs) {
let arr = [];
let time = 0;
jobs.sort((a, b) => a[0] - b[0]);
while (jobs.length) {
if (time < jobs[0][0]) {
time = jobs[0][0];
// console.log("if time", time);
}
let min = [];
for (let i = 0; i < jobs.length; i++) {
if (jobs[i][0] > time) break;
const ms = jobs[i][1] + time - jobs[i][0];
if (min.length === 0) min = [i, ms, jobs[i][1]];
if (jobs[i][1] < min[2]) min = [i, ms, jobs[i][1]];
}
// console.log("min", min);
time += jobs[min[0]][1];
arr.push(min[1]);
jobs.splice(min[0], 1);
// console.log(`time:${time}, arr:${arr}, jobs:${jobs}`);
}
// console.log(arr);
return Math.floor(arr.reduce((acc, cur) => acc + cur, 0) / arr.length);
}힙이 뭔지는 아는데 그냥 막 풀었다...
중간에 뭔가 꼬여서 잘 안풀렸는데 차분히 다시 보니 풀렸다. 먼저 jobs를 요청 순서대로 정렬한다.
처리를 다 했는데 시간이 안되서 할 처리가 없는 경우가 첫번째 if문이다.
ex) 처음 요청시간이 3이면 시간을 3으로 하고 가장 빠른 요청시간(sort 했으니 0번째 index)이 12인데 현재 시간이 10이라면 시간을 12로 바꾼다.
그리고 현재시간에 처리가 들어온 jobs중에서 길이가 짧은 경우를 찾는다. i는 jobs의 index, ms는 요청부터 종료까지 시간, jobs[i][1]은 요청시간이다.
나머지는 보면 이해
programmers.co.kr/learn/courses/30/lessons/42627
이중우선순위큐 -- 힙
function solution(operations) {
let queue=[];
operations.forEach(operation=>{
if(operation[0]==="I"){
queue.push(+operation.substr(2));
queue.sort((a,b)=>a-b);
}else if(operation==="D 1"){
queue.pop();
}else{
queue.shift();
}
})
return queue.length ? [Math.max(...queue),Math.min(...queue)] : [0,0]
}힙을 만들지 않았다.. 그냥 이렇게 풀어도 되는걸까?? sort함수도 시간복잡도가 n이니 시간복잡도가 n^2이 되서 이러면 안된다. 안된다고!! 나중에 수정 아니 sort시간복잡도가 n이아니야.. 먼지몰라 머지
팀소트방식이용.. 그냥 이거 쓰면돼
programmers.co.kr/learn/courses/30/lessons/42628
여행경로 -- 깊이/너비 우선 탐색(DFS/BFS)
function solution(tickets) {
let result = [];
const len = tickets.length;
for (let i = 0; i < tickets.length; i++) {
if (tickets[i][0] === "ICN") {
dfs(
tickets[i],
["ICN"],
tickets.slice(0, i).concat(tickets.slice(i + 1))
);
}
}
function dfs(now_ticket, arr, tickets) {
if (arr.length === len) {
result.push([...arr, now_ticket[1]]);
// result.push(arr.concat(now_ticket[1]));
} else {
for (let i = 0; i < tickets.length; i++) {
if (tickets[i][0] === now_ticket[1]) {
dfs(
tickets[i],
[...arr, tickets[i][0]],
// arr.concat(tickets[i][0]),
tickets.slice(0, i).concat(tickets.slice(i + 1))
);
}
}
}
}
result.sort();
return result[0];
}
처음에 filter로 했다가 중복되는 경우가 있어서 실패했다. 개빡... 그냥 dfs사용하면 된다.
programmers.co.kr/learn/courses/30/lessons/43164
입국심사 -- 이분탐색
function solution(n, times) {
let left=1, right=n*Math.max(...times);
while(left<=right){
let mid=Math.floor((left + right) / 2);
const count=times.reduce((acc,cur)=>acc+Math.floor(mid/cur),0);
if(count>=n) right=mid-1;
else left=mid+1;
}
return left;
}이분탐색이기 때문에 먼저 최소시간, 최대시간을 정한다. 최소시간은 1으로 하고 최대시간은 가장 시간이 오래걸리는 심사관이 심사를 n번 한 경우로 한다.
가장 간단한 번호 찾기(소주뒤에 번호찾기)와 비교해서 다른 것은 count=n인 경우가 여러개 라는 것이다.
(count를 계산하는 방법도 생각하기 쉽지 않다)
solution(6,[7,10])인 경우를 보면
mid가 28,29일 때 모두 6이다. 그리고 30이 되면 reduce의 index가 1일때 Math.floor(mid/cur)가 1이 증가한다.
결국 7*n과 10*n일 때 count값이 변한다.
이를 해결하기 위해서 직관적으로 생각나는 것은 7*n, 10*n꼴이 되게 left나 right를 변경하는 것이다. 그래도 되지만 오히려 더 복잡할 수 있어서 이 방법을 선택하지 않았다. times에 길이가 길면 시간이 더 길어질 수 있다.
내가 선택한 방법은 count와 n이 같은 경우에도 오른쪽을 버리는 방법이다. 이렇게 되면 left와 right 값이 같아지고 count는 n보다 1작게 되서 left=mid+1을 실행한다. 그리고 그렇게 되면 left가 값이 더 커서 while문이 종료되고 left에서 원하는 값을 얻게 된다.
아래 그림을 보면 a부터 b까지 count=n인 경우일때 a부터 b사이의 어떤 값이 mid값으로 나오게 되면 그때부터 오른쪽 부분을 계속 지워간다. 그리고 left와 right가 a-1이 되고 위에서 말한 과정을 거쳐서 left는 a 즉 원하는 최소시간이 된다.
참고를 위해 위에서 말한 다른 방법 코드
function solution(n, times) {
let left=1, right=n*Math.max(...times);
while(left<=right){
let mid=Math.floor((left + right) / 2);
const count=times.reduce((acc,cur)=>acc+Math.floor(mid/cur),0);
if(count>n) right=mid-1;
else if(count<n) left=mid+1;
else{
let min=false;
while(!min){
times.forEach(v=>{
if(mid%v===0) min=true;
})
mid--;
}
return mid+1;
}
}
}programmers.co.kr/learn/courses/30/lessons/43238
베스트앨범 -- 해시
function solution(genres, plays) {
const arr = [];
for (let i = 0; i < genres.length; i++) {
let genre_index = -1;
for (let j = 0; j < arr.length; j++) {
if (arr[j][0] === genres[i]) {
genre_index = j;
break;
}
}
if (genre_index === -1) {
arr.push([genres[i], [plays[i], i]]);
} else {
arr.splice(genre_index, 1, [...arr[genre_index], [plays[i], i]]);
}
}
arr.forEach((v, i) => {
v=v.slice(1);
v.sort((a, b) => {
if (a[0] === b[0]) return a[1] - b[1];
return b[0] - a[0];
});
arr.splice(i, 1, [...v, v.reduce((acc, cur) => acc + cur[0], 0)]);
});
arr.sort((a, b) => b[b.length - 1] - a[a.length - 1]);
const result = [];
arr.forEach((v, i) => {
v.pop();
v.slice(0, 2).forEach((val) => {
result.push(val[1]);
});
});
return result;
}코드가 좀 지저분한듯...
먼저 첫번째 for문에서 장르별로 배열을 나눴다.(이부분이 좀 지저분한 듯)
[ [ 'classic', [ 500, 0 ], [ 150, 2 ], [ 800, 3 ] ],
[ 'pop', [ 600, 1 ], [ 2500, 4 ] ]
]
forEach로 장르를 삭제하고 내부정렬을 한다. (play가 같은 경우 예외처리도) 그리고 reduce로 총합을 구한다.
방금 구한 총합으로 sort하고 result에 넣어주면 끝
programmers.co.kr/learn/courses/30/lessons/42579
순위 -- 그래프
처음 코드 오류
function solution(n, results) {
let graph = Array(n)
.fill()
.map((i) => [[], []]);
results.forEach((v) => {
graph[v[0] - 1][0].push(v[1]);
graph[v[1] - 1][1].push(v[0]);
});
for (let i = 0; i < n; i++) {
graph[i][0] = [
...new Set(
graph[i][0].reduce((acc, cur) => {
return acc.concat(graph[cur - 1][0].flat());
}, graph[i][0])
),
];
graph[i][1] = [
...new Set(
graph[i][1].reduce((acc, cur) => {
return acc.concat(graph[cur - 1][1].flat());
}, graph[i][1])
),
];
}
return graph.reduce((acc, cur) => {
if (cur[0].length + cur[1].length === n - 1) return acc + 1;
return acc;
}, 0);
}
graph라는 2차원 배열을 만들고 0번째 요소에는 이긴선수, 1번째 요소에는 진선수를 넣는다. 이때 graph의 i번째 index가 i+1선수이다.
그리고 선수 a가 이긴 선수들(b)이 이긴 선수들(c)은 a가 이긴 선수가 되므로 위에 같이 코드를 짜고 중복제거를 위해 set을 사용한다. a>b b>c => a>b,c
진선수도 마찬가지로 a가 진 선수들(b)이 진 선수들(c)은 진 선수가 된다.
a<b b<c => a,b<c
왜 틀렸나 하고 보니까
solution(8, [[1, 2],[2, 3],[3, 4],[4, 5],[5, 6],[6, 7],[7, 8],]) 을 했을 때
[
[ [ 2, 3 ], [] ],
[ [ 3, 4 ], [ 1 ] ],
[ [ 4, 5 ], [ 2, 1 ] ],
[ [ 5, 6 ], [ 3, 2, 1 ] ],
[ [ 6, 7 ], [ 4, 3, 2, 1 ] ],
[ [ 7, 8 ], [ 5, 4, 3, 2, 1 ] ],
[ [ 8 ], [ 6, 5, 4, 3, 2, 1 ] ],
[ [], [
7, 6, 5, 4,
3, 2, 1
] ]
]
3
값이 이렇게 나온다. 왜냐하면 위 코드에 따르면 1이 이긴선수는 2, 2가 이긴선수는 3이기 때문이다. 그래서 코드를 수정했다.
function solution(n, results) {
let graph = Array(n)
.fill()
.map(() => [[], []]);
results.forEach((v) => {
graph[v[0] - 1][0].push(v[1]);
graph[v[1] - 1][1].push(v[0]);
});
// console.log(graph);
for (let i = 0; i < n; i++) {
graph.forEach((v) => {
v[0] = [
...new Set(
v[0].reduce((acc, cur) => {
acc.push(...graph[cur - 1][0]);
return acc;
}, v[0])
),
];
v[1] = [
...new Set(
v[1].reduce((acc, cur) => {
acc.push(...graph[cur - 1][1]);
return acc;
}, v[1])
),
];
});
}
// console.log(graph);
return graph.reduce((acc, cur) => {
if (cur[0].length + cur[1].length === n - 1) return acc + 1;
return acc;
}, 0);
}
즉 O(n)을 O(n^2)으로 바꾼것이다. 그 외에 concat보다 push spread를 하는게 훨씬 빨라서 코드를 수정했다.
programmers.co.kr/learn/courses/30/lessons/49191
가장 큰 팰린드롬
효율성 실패
function solution(s){
const len=s.length;
if(len<=1) return len;
const result=[1];
for(let start=0;start<len-1;start++){
for(let end=start+2;end<=len;end++){
const temp=s.substring(start,end);
const temp_len=temp.length;
const back_idx=temp_len%2===0 ? temp_len/2 : temp_len/2+1;
const front=temp.substr(0,temp_len/2);
const back=temp.substr(back_idx).split('').reverse().join('');
if(front===back) result.push(temp_len);
}
}
return Math.max(...result);
}
솔직히 효율성 생각안하고 일단 풀자 해서 풀었는데 역시나~~~~
다시 푼 코드
function solution(s){
const s_len=s.length;
if(s_len<=1) return s_len;
for(let len=s_len;len>=2;len--){
for(let left=0;left<=s_len-len;left++){
let right=left+len-1;
const mid=(left+right)/2;
let yes=true;
for(let i=left;i<mid;i++){
if(s[i]!==s[right--]){
yes=false;
break;
}
}
if(yes) return len;
}
}
return 1;
}
일단 잘못푼 코드에서 잘못 생각한 것을 말하겠다. for문을 left와 right로 지정해서 돌렸는데 이러면 이미 값을 찾아도 끝까지 돈다. 이를 해결하기 위해서 길이를 지정하고 하나씩 줄여나가며 맞는 경우 바로 return을 해준다.
그리고 전체 비교를 하지않고 앞, 뒤 index비교를 하면 훨씬 빠르다.
이제 아래 코드로 설명을 하겠다.
먼저 s길이가 1보다 작거나 같은 경우 값은 정해져있기 때문에 미리 return해준다.
첫번째 for문은 아까 말했듯이 길이를 줄여나가며 비교하는 것이다. 1을 제외한 이유는 마지막에 길이가 2인경우도 존재하지 않은 경우에 return 1을해주기 때문이다.
두번째 fro문은 left의 index를 넣었다. 마지막 index는 s의 길이 - 구하는 길이 이다.
ex) s의 길이가 7이고 for문의 첫번째 경우 len=7 이므로 left index가 0인경우 7-7=0이 된다.
right는 당연하므로 생략. mid도 정확히 지정해주면 좋지만 따로 처리를 하지 않아도 오류가 나지 않음
궁금하면 직접 손이나 로그를 찍어보면 된다.
그리고 3번째 for문에서 앞 뒤로 비교를 하고 틀린경우 for문을 break하고 yes를 false로 만든다. 즉 for문이 끝까지 돌아간 경우만 return
programmers.co.kr/learn/courses/30/lessons/12904
기둥과 보 설치 -- 2020 KAKAO BLIND RECRUITMENT
function solution(n, build_frame) {
let answer = [];
build_frame.forEach((v) => {
if (v[3] === 1) {
// 추가
if (validation(answer, v)) answer.push([v[0], v[1], v[2]]);
} else {
// 삭제
const temp = answer.filter(
(ans) => ans.toString() !== [v[0], v[1], v[2]].toString()
);
for (let i = 0; i < temp.length; i++) {
if (!validation(temp, temp[i])) break;
if (i === temp.length - 1) answer = temp;
}
}
// console.log(answer, v);
});
answer.sort((a, b) => {
if (a[0] === b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
return answer;
}
function validation(arr, build) {
if (build[2] === 0) {
// 기둥
// 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
if (
build[1] === 0 || // 바닥 위에 있거나
arr.findIndex(
(v) => v.toString() === [build[0] - 1, build[1], 1].toString()
) !== -1 || // 보의 한쪽 끝 부분 위에 있거나(왼쪽)
arr.findIndex(
(v) => v.toString() === [build[0], build[1], 1].toString()
) !== -1 || // 보의 한쪽 끝 부분 위에 있거나(오른쪽)
arr.findIndex(
(v) => v.toString() === [build[0], build[1] - 1, 0].toString()
) !== -1 // 다른 기둥 위에 있어야 합니다.
)
return true;
} else {
// 보
// 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
if (
arr.findIndex(
(v) => v.toString() === [build[0], build[1] - 1, 0].toString()
) !== -1 || // 한쪽 끝 부분이 기둥 위에 있거나(왼쪽)
arr.findIndex(
(v) => v.toString() === [build[0] + 1, build[1] - 1, 0].toString()
) !== -1 || // 한쪽 끝 부분이 기둥 위에 있거나(오른쪽)
(arr.findIndex(
(v) => v.toString() === [build[0] - 1, build[1], 1].toString()
) !== -1 &&
arr.findIndex(
(v) => v.toString() === [build[0] + 1, build[1], 1].toString()
) !== -1) // 양쪽 끝 부분이 다른 보와 동시에 연결되어
)
return true;
}
return false;
}
실패... 왜지
다시도전
//기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
//보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
const GI = 0,
BO = 1,
DELETE = 0,
INSTALL = 1;
function isValid(x, y, type, frame, n) {
if (type === GI) {
const one = y === 0; // 바닥 위에 있거나
const two = (x - 1 >= 0 && frame[y][x - 1].bo) || frame[y][x].bo; // 보의 한쪽 끝 부분 위에 있거나
const three = y - 1 >= 0 && frame[y - 1][x].gi; // 다른 기둥 위에 있어야
return one || two || three;
} else {
const one =
(y - 1 >= 0 && frame[y - 1][x].gi) || // 한쪽 끝 부분이 기둥 위에 있거나
(x + 1 <= n && frame[y - 1][x + 1].gi);
const two =
x - 1 >= 0 && x + 1 <= n && frame[y][x - 1].bo && frame[y][x + 1].bo; // 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야
return one || two;
}
}
function install(x, y, type, frame) {
const real_type = type === 0 ? "gi" : "bo";
frame[y][x][real_type] = true;
}
function deleteToggle(x, y, real_type, frame) {
frame[y][x][real_type] = !frame[y][x][real_type];
}
function deleteOrNot(x, y, type, frame, n) {
let real_type, gi_check_arr, bo_check_arr;
if (type === 0) {
real_type = "gi";
gi_check_arr = [{ x, y: y + 1 }];
bo_check_arr = [
{ x: x - 1, y: y + 1 },
{ x, y: y + 1 },
];
} else {
real_type = "bo";
gi_check_arr = [
{ x, y },
{ x: x + 1, y },
];
bo_check_arr = [
{ x: x - 1, y },
{ x: x + 1, y },
];
}
deleteToggle(x, y, real_type, frame);
const gi_check = gi_check_arr
.filter((v) => v.x >= 0 && v.y <= n && frame[v.y][v.x][real_type])
.every((v) => isValid(v.x, v.y, type, frame, n));
const bo_check = bo_check_arr
.filter((v) => v.x >= 0 && v.y <= n && frame[v.y][v.x][real_type])
.every((v) => isValid(v.x, v.y, type, frame, n));
console.log(gi_check, bo_check);
if (!(gi_check && bo_check)) {
deleteToggle(x, y, real_type, frame);
}
}
function getSolution(frame, n) {
const answer = [];
for (let x = 0; x <= n; x++) {
for (let y = 0; y <= n; y++) {
if (frame[y][x].gi) {
answer.push([x, y, GI]);
}
if (frame[y][x].bo) {
answer.push([x, y, BO]);
}
}
}
return answer;
}
function solution(n, build_frame) {
const frame = Array(n + 1)
.fill()
.map(() =>
Array(n + 1)
.fill()
.map(() => ({ gi: false, bo: false }))
);
for (const [x, y, type, action] of build_frame) {
if (action === INSTALL) {
if (isValid(x, y, type, frame, n)) install(x, y, type, frame);
} else {
deleteOrNot(x, y, type, frame, n);
}
// console.log(x, y, type, action, frame);
}
// console.log(frame);
return getSolution(frame, n);
}
console.log(
solution(5, [
[0, 0, 0, 1],
[2, 0, 0, 1],
[4, 0, 0, 1],
[0, 1, 1, 1],
[1, 1, 1, 1],
[2, 1, 1, 1],
[3, 1, 1, 1],
[2, 0, 0, 0],
[1, 1, 1, 0],
[2, 2, 0, 1],
])
);
또 실패 자살마렵네
성공
// build_frame의 원소는 [x, y, a, b]형태입니다.
// x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
// a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
// b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치를 나타냅니다.
//기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
//보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
const GI = 0,
BO = 1,
DELETE = 0,
INSTALL = 1;
function isValidGi(x, y, frame) {
const onFloor = y === 0;
const onBo = (x - 1 >= 0 && frame[y][x - 1].bo) || frame[y][x].bo;
const onGi = y - 1 >= 0 && frame[y - 1][x].gi;
return onFloor || onBo || onGi;
}
function isValidBo(x, y, frame, n) {
const onGi =
(y - 1 >= 0 && frame[y - 1][x].gi) ||
(x + 1 <= n && frame[y - 1][x + 1].gi);
const bothBo =
x - 1 >= 0 && x + 1 <= n && frame[y][x - 1].bo && frame[y][x + 1].bo;
return onGi || bothBo;
}
function install(x, y, frame, type) {
frame[y][x][type] = true;
}
function removeGi(x, y, frame, n) {
const gi = [{ x, y: y + 1 }];
const bo = [
{ x, y: y + 1 },
{ x: x - 1, y: y + 1 },
];
toggle(x, y, frame, "gi");
const noEffectGi = gi
.filter((v) => v.x >= 0 && v.y <= n && frame[v.y][v.x].gi)
.every((v) => isValidGi(v.x, v.y, frame));
const noEffectBo = bo
.filter((v) => v.x >= 0 && v.y <= n && frame[v.y][v.x].bo)
.every((v) => isValidBo(v.x, v.y, frame, n));
if (noEffectGi && noEffectBo) {
return;
}
toggle(x, y, frame, "gi");
}
function removeBo(x, y, frame, n) {
const gi = [
{ x, y },
{ x: x + 1, y },
];
const bo = [
{ x: x - 1, y },
{ x: x + 1, y },
];
toggle(x, y, frame, "bo");
const noEffectGi = gi
.filter((v) => v.x >= 0 && v.y <= n && frame[v.y][v.x].gi)
.every((v) => isValidGi(v.x, v.y, frame));
const noEffectBo = bo
.filter((v) => v.x >= 0 && v.y <= n && frame[v.y][v.x].bo)
.every((v) => isValidBo(v.x, v.y, frame, n));
if (noEffectGi && noEffectBo) {
return;
}
toggle(x, y, frame, "bo");
}
function toggle(x, y, frame, type) {
frame[y][x][type] = !frame[y][x][type];
}
function getSolution(frame, n) {
const answer = [];
for (let x = 0; x <= n; x++) {
for (let y = 0; y <= n; y++) {
if (frame[y][x].gi) {
answer.push([x, y, GI]);
}
if (frame[y][x].bo) {
answer.push([x, y, BO]);
}
}
}
return answer;
}
function solution(n, build_frame) {
const frame = Array(n + 1)
.fill()
.map(() =>
Array(n + 1)
.fill()
.map(() => ({ gi: false, bo: false }))
);
for (const [x, y, type, action] of build_frame) {
if (type === GI && action === INSTALL) {
isValidGi(x, y, frame) && install(x, y, frame, "gi");
} else if (type === BO && action === INSTALL) {
isValidBo(x, y, frame, n) && install(x, y, frame, "bo");
} else if (type === GI && action === DELETE) {
removeGi(x, y, frame, n);
} else {
removeBo(x, y, frame, n);
}
}
return getSolution(frame, n);
}
너무 식이 복잡해서 계속 실수했던 것같다. 그냥 진짜 처음하는 것 처럼 차근차근 보고 오류 로그 하나씩 찍어보니 답이 정말 다행히 나왔다. 각 좌표별로 기둥과 보를 둘다 처음에 false로 만들고 삭제할때는 삭제했을때 관련있는 부분만 filtering한다음 검증한다. 이때 먼저 안해 머리아퍼
programmers.co.kr/learn/courses/30/lessons/60061
외벽 점검 -- 2020 KAKAO BLIND RECRUITMENT
const getPermutations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((i) => [i]); // 1개씩 선택한다면 모든 배열의 원소를 return한다.
arr.forEach((fixed, index, array) => {
const rest = [...array.slice(0, index), ...array.slice(index + 1)]; // fixed를 제외한 나머지 배열(순열)
const permutations = getPermutations(rest, selectNumber - 1); // rest에 대한 순열을 구한다.
const attached = permutations.map((permutation) => [fixed, ...permutation]); // fixed와 rest에 대한 조합을 붙인다.
results.push(...attached); // result 배열에 push
});
return results;
};
function solution(n, weak, dist) {
const weak_arr = [];
for (let i = 0; i < weak.length; i++) {
const temp = weak.slice(i);
let num = 0;
while (temp.length !== weak.length) {
temp.push(weak[num++] + n);
}
weak_arr.push(temp);
}
dist.sort((a, b) => b - a);
for (let i = 1; i <= dist.length; i++) {
const arr = dist.slice(0, i);
const permu_arr = getPermutations(arr, i);
for (let j = 0; j < permu_arr.length; j++) {
for (let k = 0; k < weak.length; k++) {
let weak_arr_copy = weak_arr[k].slice();
for (let l = 0; l < i; l++) {
const a = weak_arr_copy[0] + permu_arr[j][l];
weak_arr_copy = weak_arr_copy.filter((v) => v > a);
}
if (weak_arr_copy.length === 0) return i;
}
}
}
return -1;
}순열을 생각못해서 처음에 틀렸다.
먼저 시간복잡도를 줄이고 코드도 더 간단하게 하는 방법이 첫번째 for문이다. 시계방향, 반시계방향을 하는 것을 일자로 피는 작업이다. 첫번째 예시인 12, [1, 5, 6, 10], [1, 2, 3, 4] 이것을 살펴보자.
10에서 1로 가는 것과 1에서 10으로 가는 것은 같다.
weak배열에서 하나를 선택하고 그보다 작은 값은 뒤로 보낸다고 생각하자. 뒤로 보내는 건 n만큼 더하면 된다. 여기서 5를 선택하고 5를 기준으로 일자로 핀다고 생각을 해보자. 그러면 1은 1+12로 13이 된다. 10을 선택한다면 1은 13, 5는 17, 6은 18이 되는 것이다. 이러면 코드도 직관적으로 잘 보이고 복잡도도 줄어든다.
그리고 dist를 내림차순으로 정렬한다. 왜냐하면 dist의 길이를 하나씩 늘리면서 해당한다면 바로 return해주기 위해서다. dist가 길면 무조건 점검하는 지점이 많으므로 내림차순으로 정렬한다.
그래서 두번째에서 첫번째 for문은 dist로 돌리고
dist를 i만큼 앞에서부터 자르고 그에 따른 순열을 만든다. 처음에 이 부분을 생각을 못했다. 생각해보면 당연한 것이다. 뒤의 코드를 먼저 보고 나중에 설명하겠다.
두번째 for문은 permu_arr로 돌리고 j
세번째 for문은 weak의 길이만큼 돌린다. k 이때 아까 만든 weak배열 중 k인덱스를 복사한다. weak_arr_copy
const a = weak_arr_copy[0] + permu_arr[j][l];
weak_arr_copy = weak_arr_copy.filter((v) => v > a);
이 부분은 예를들어서 첫번째 예시에서 첫번째 경우를 보면 a는 1+4=5, weak_arr_copy=[6,10]이 된다.
이렇게 해서 길이가 0이 되면 i를 return하면 된다.
그리고 for문이 끝날때까지 return을 안하면 -1을 return한다.
programmers.co.kr/learn/courses/30/lessons/60062
블록 이동하기 -- 2020 KAKAO BLIND RECRUITMENT
'코딩테스트' 카테고리의 다른 글
| 자바스크립트 프로그래머스 문제모음 (0) | 2021.06.22 |
|---|---|
| 프로그래머스 3단계 답지2 (0) | 2021.02.11 |
| 프로그래머스 2단계 답지2 (0) | 2021.01.01 |
| 프로그래머스 2단계 답지1 (0) | 2020.12.29 |
| 프로그래머스 1단계 답지2 (0) | 2020.12.27 |