const fs = require('fs');
const input = fs
.readFileSync(__dirname + '/input.txt')
.toString()
.split('\n');
// 테스트 횟수
const T = +input[0];
let index = 1;
for (let t = 1; t <= T; t++) {
// 입력값 n은 건물 개수, k는 간선의 수
const [n, k] = input[index].split(' ').map(Number);
// 각각의 건물마다 건설 시간
const timeArr = input[index + 1].split(' ').map(Number);
// 입력값에서 간선의 인덱스로 이동
index += 2;
// 간선들을 그래프에 담기 위해서 (인덱스와 건물 번호가 일치하도록 n+1)
const graph = Array(n + 1)
.fill()
.map(() => []);
// 그래프에 간선 정보 담기
for (let i = 0; i < k; i++) {
const [start, end] = input[index + i].split(' ').map(Number);
graph[end].push(start);
}
// 총 건설 시간의 초기값은 각각의 건물 시간으로 줌
const minBuild = [0, ...timeArr];
// 간선 지나치기
index += k;
// 완성 시켜야 하는 건물
const target = input[index++];
//총 건설 시간 배열을 활용하여 목표 건물의 총 건설 시간 구함
console.log(countTotal(target));
// 재귀함수를 통해서 경로를 찾음, 이때 모든 건물의 건설 시간을 구하는게 아니라
// 목표 건물의 하위 건물들만 구해줌
function countTotal(number) {
//반복문을 통해서 목표 건물에 선행 건물이 있다면 해당 건물의 총 건설 시간 먼저 구함
while (true) {
// 선행 건물이 없다면 건설시간 반환
if (graph[number].length === 0) {
return minBuild[number];
}
// 선행 대상이 있다면, graph에서 해당 노드를 추출하고 총 건설시간을 구함
const subTarget = graph[number].pop();
// 총 건설 시간은 기존에 있는 값과 비교하여서 더 긴 경우에만 수정
minBuild[number] = Math.max(
minBuild[number],
countTotal(subTarget) + timeArr[number - 1]
);
}
}
}
문제를 풀었는데, 내 방법은 13번에서 효율성에 통과하지 못했다. 하지만 해당 원인에 대해서 처음엔 잘 이해하지 못했고, 다른 사람의 풀이를 보고 고민한 결과를 정리하고자 게시글을 작성하게 되었다.
문제는 위와 같다.
요약하자면 현재 돌 보다 밟을 수 있는 횟수가 작은 돌이 연속으로 k번 이상 나오게 되면 건널 수가 없다.
나는 위와 똑같은 논리를 코드로 구현하고자 하였다.
function solution(stones, k) {
// 돌의 갯수
const arrayLength = stones.length;
// 한번에 건널 수 있는 수와 돌 수가 같다면 최대값이 답.
if (arrayLength == k) {
return Math.max(...stones);
}
// 초기에는 k번쨰 수중 가장 큰 값이 최대값
let answer = stones[0];
for (let i = 1; i < k; i++) {
if (stones[i] > answer) {
answer = stones[i];
}
}
// 이후 반복문을 통해서, 다음번의 돌들이 연속으로 k번 작을 경우 answer를 교체
for (let i = 0; i < arrayLength - k; i++) {
let max = 0;
const current = stones[i];
let flag = false;
for (let j = 1; j <= k; j++) {
if (current < stones[i + j]) {
flag = true;
break;
}
max = Math.max(max, stones[i + j]);
}
if (!flag) {
answer = Math.min(answer, max);
}
}
return answer;
}
로직에 문제가 없다면 정확성에선 통과하지만, 효율성에서 13번에서 걸리고 말았다.
이 당시에는 왜 13번만 통과를 못하지에 대한 해답을 찾지 못하였고, 나와 같은 문제를 겪은 사람이 있을까 질문하기에 들어갔다.
그 결과 대부분을 이분탐색을 통해서 문제를 푼다는 것을 알게 되었고, 이를 참고하여서
function solution(stones, k) {
//이분 탐색 좌우
let left = 1;
let right = 200000000;
while (left <= right) {
const mid = ((left + right) / 2) >> 0;
let count = 0;
// 반복문을 통해서 연속으로 k번 나오면 break, 이후 정답에 가까운 값을 다시 탐색)
for (let i = 0; i < stones.length; i++) {
if (stones[i] - mid <= 0) count++;
else count = 0;
if (count === k) break;
}
// 만약 연속 k번 나오면 right를 교체(현재 값이 최댓값을 넘었다)
if (count === k) right = mid - 1;
// 아니라면 더 큰 값이 있는지 찾기 위해서 left를 교체
else left = mid + 1;
}
return left;
}
위 방법은 내 방법과 다르다.
내 방법은 각각의 숫자를 비교하면서 일일이 최댓값을 교체해주는 방식이면, 이분탐색 방법은 정답을 임의의 값으로 정해놓고 비교한 후 정답을 수정하는 방식이다. (200000000가지 중에서 이분 탐색을 통해서 정답을 찾는 방식)
내 방법과 다르게 대부분의 방식에선 속도가 느린데, 13번만 유독 빠르다.
이에 대한 호기심을 해결하기 위해서 두 방식의 시간 복잡도를 계산해 보려고 하였다.
내 방법의 시간복잡도는 n * k 이다. ( n: 배열의 길이 , k : k의 값)
k가 길어질수록 반복 계산이 많아진다.
정답에 통과한 두 번쨰 방법의 시간 복잡도는 nlogM이다( n: 배열의 길이, M은 left와 right의 간격 200000000)
이분 탐색을 통해 찾기 때문에 만약 정답이 중앙에 가까울수록 속도가 빠를 것이다.
즉 테스트에서 대부분 내 값이 빨랐던 이유는 k 값이 log( 200000000)에 비해서 작았기 떄문이다.
하지만 가장 오래 걸리는 값을 기준으로 했을 때는 후자가 훨씬 좋은 방법이다.
회고
문제를 풀면서, 시간 복잡도에 대해서 깊게 생각하지 않았기 때문에 좀 더 막막하게 느껴졌었던 것 같다.
백준에서 시간 복잡도의 중요성을 느끼지만, 막상 문제 풀 때는 문제 유형에 맞춘 방법을 사용했었다... 안 좋은 습관인 거 같다. 막상 혼자 밑 바닥 부터 생각해야 할 때, 좋은 방법이 잘 떠오르지 않았느데, 이번 기회에 시간 복잡도와 문제를 고민하는 방법에 대해서 다시 생각하게 되었다.
/**
* Expose `PriorityQueue`.
*/
module.exports = PriorityQueue;
/**
* Initializes a new empty `PriorityQueue` with the given `comparator(a, b)`
* function, uses `.DEFAULT_COMPARATOR()` when no function is provided.
*
* The comparator function must return a positive number when `a > b`, 0 when
* `a == b` and a negative number when `a < b`.
*
* @param {Function}
* @return {PriorityQueue}
* @api public
*/
function PriorityQueue(comparator) {
this._comparator = comparator || PriorityQueue.DEFAULT_COMPARATOR;
this._elements = [];
}
/**
* Compares `a` and `b`, when `a > b` it returns a positive number, when
* it returns 0 and when `a < b` it returns a negative number.
*
* @param {String|Number} a
* @param {String|Number} b
* @return {Number}
* @api public
*/
PriorityQueue.DEFAULT_COMPARATOR = function(a, b) {
if (typeof a === 'number' && typeof b === 'number') {
return a - b;
} else {
a = a.toString();
b = b.toString();
if (a == b) return 0;
return (a > b) ? 1 : -1;
}
};
/**
* Returns whether the priority queue is empty or not.
*
* @return {Boolean}
* @api public
*/
PriorityQueue.prototype.isEmpty = function() {
return this.size() === 0;
};
/**
* Peeks at the top element of the priority queue.
*
* @return {Object}
* @throws {Error} when the queue is empty.
* @api public
*/
PriorityQueue.prototype.peek = function() {
if (this.isEmpty()) throw new Error('PriorityQueue is empty');
return this._elements[0];
};
/**
* Dequeues the top element of the priority queue.
*
* @return {Object}
* @throws {Error} when the queue is empty.
* @api public
*/
PriorityQueue.prototype.deq = function() {
var first = this.peek();
var last = this._elements.pop();
var size = this.size();
if (size === 0) return first;
this._elements[0] = last;
var current = 0;
while (current < size) {
var largest = current;
var left = (2 * current) + 1;
var right = (2 * current) + 2;
if (left < size && this._compare(left, largest) >= 0) {
largest = left;
}
if (right < size && this._compare(right, largest) >= 0) {
largest = right;
}
if (largest === current) break;
this._swap(largest, current);
current = largest;
}
return first;
};
/**
* Enqueues the `element` at the priority queue and returns its new size.
*
* @param {Object} element
* @return {Number}
* @api public
*/
PriorityQueue.prototype.enq = function(element) {
var size = this._elements.push(element);
var current = size - 1;
while (current > 0) {
var parent = Math.floor((current - 1) / 2);
if (this._compare(current, parent) <= 0) break;
this._swap(parent, current);
current = parent;
}
return size;
};
/**
* Returns the size of the priority queue.
*
* @return {Number}
* @api public
*/
PriorityQueue.prototype.size = function() {
return this._elements.length;
};
/**
* Iterates over queue elements
*
* @param {Function} fn
*/
PriorityQueue.prototype.forEach = function(fn) {
return this._elements.forEach(fn);
};
/**
* Compares the values at position `a` and `b` in the priority queue using its
* comparator function.
*
* @param {Number} a
* @param {Number} b
* @return {Number}
* @api private
*/
PriorityQueue.prototype._compare = function(a, b) {
return this._comparator(this._elements[a], this._elements[b]);
};
/**
* Swaps the values at position `a` and `b` in the priority queue.
*
* @param {Number} a
* @param {Number} b
* @api private
*/
PriorityQueue.prototype._swap = function(a, b) {
var aux = this._elements[a];
this._elements[a] = this._elements[b];
this._elements[b] = aux;
};
위의 코드를 이해하기에 앞서 힙(heap)이라는 자료구조를 알 필요가 있습니다.
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로서
A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
이때 부모가 자식보다 크면 최대 힙, 작으면 최소 힙이라고 한다. (출처 : 위키백과)
아래와 같은 구조는 최대 힙이다.
이를 통해서 부모노드는 항상 자식보다 큰 값을 가지며, 우리는 추상적 자료구조인 우선순위큐를 구현할 수 있다.
출처 : 위키 백과
최대힙에서 삽입
만약 추가적인 자료가 삽입된다면, 우선 마지막 노드 위치에 추가되고, 부모 노드와 비교하여 최대힙 조건이 만족될 떄까지 이동한다. 그렇기 때문에 배열에 단순히 추가하는 것은 O(1) 이지만 최대 힙에서 시간복잡도는 O(log(N))이다
최대힙에서 삭제
최대힙에서 삭제할 때는, 부모 노드를 제거한다 .
이후 마지막 노드를 부모로 이동시킨 후, 두 값 중에서 더 큰 값을 가진 노드와 스왑을 진행하여, 최대 힙이 만족될 떄까지 정렬한다.
이제 힙에 대한 설명이 끝났으니, 다시 위의 코드에 대한 분석을 해보자. 결국 우리의 목적은 알고리즘(백준?)에 쓸 우선순위 큐를 만드는 것이고, 위의 코드는 라이브러리 형식이기에 모듈로 export 되어있다. 라이브러리 기에 기본적인 우선순위 큐를 설정해두었고, 외부에서 비교로직을 준다면 해당 로직으로 사용한다. 따라서 우리는 위의 코드를 아래와 같이 수정할 수 있다. (불필요한 주석 제거)
1. 외부에서 무조건 comparator를 전달하는 구조를 만들자.
function PriorityQueue(comparator) {
this._comparator = comparator
this._elements = [];
}
2. isEmpty 와 peek , size
size는 elements의 길이를 측정해준다. elements에 저장된 노드를 담긴 때문에 해당 배열의 길이가 우선순위큐의 크기다.
isEmpty는 큐가 비었는지 확인하는 함수이다. 따라서 ;size가 0이면 비었있다'라고 구현했다.
peek의 경우 가장 먼저 제거되는 녀석(부모 노드)를 알려주면 된다. 이는 elements라는 배열의 0번째 인덱스 값이다.
function PriorityQueue(comparator) {
this._comparator = comparator
this._elements = [];
}
PriorityQueue.prototype.isEmpty = function() {
return this.size() === 0;
};
PriorityQueue.prototype.peek = function() {
if (this.isEmpty()) throw new Error('PriorityQueue is empty');
return this._elements[0];
};
PriorityQueue.prototype.size = function() {
return this._elements.length;
};
3. forEach, swap, compare
우선순위를 정해서 삽입 및 추가하려면, 기존 노드들을 비교, 스왑할 필요가 있다고 했다.
forEach: 큐 내의 elements에 대해서 배열의 forEach 메서드 실행 ( fn을 통해 함수를 매개변수로 받어 콜백함수로 사용)
compare :forEach노드에 사용할 비교함수. 각각의 노드를 comparator를 활용해서 비교함
swap : aux에 a 를 잠시 저장하고, b를 a에 할당, b에 aux를 할당함으로서 a와 b를 교체함
PriorityQueue.prototype.forEach = function(fn) {
return this._elements.forEach(fn);
};
PriorityQueue.prototype._compare = function(a, b) {
return this._comparator(this._elements[a], this._elements[b]);
};
PriorityQueue.prototype._swap = function(a, b) {
var aux = this._elements[a];
this._elements[a] = this._elements[b];
this._elements[b] = aux;
};
4. enq와 deq (삽입과 제거)
이제 내부 프로토타입들은 완성 되었으므로, 이를 활용하여 deq와 enq 프토로타입을 만들면 됩니다.
PriorityQueue.prototype.enq = function(element) {
var size = this._elements.push(element);
var current = size - 1;
while (current > 0) {
var parent = Math.floor((current - 1) / 2);
if (this._compare(current, parent) <= 0) break;
this._swap(parent, current);
current = parent;
}
return size;
};
위쪽 위키백과 이미지에 배열 테이블을 보시면 한 하위노드에 대한 부모노드의 취니는 해당 노드의 인덱스/2를 내림 한 값과 같습니다. 따라서 부모 노드를 찾고, 비교했을 때, 현재값이 작거나 같다면 멈추고, 아니면 swap을 계속 진행해줍니다.
이후 현재값을 parent노드 값(기존에 삽입한 값)으로 변경 후 해당 위치에서는 힙구조(최대인지 최소인지)에 맞는 위치인지를 확인합니다. 맞다면 변경된 size를 반환합니다.
PriorityQueue.prototype.deq = function() {
var first = this.peek();
var last = this._elements.pop();
var size = this.size();
if (size === 0) return first;
this._elements[0] = last;
var current = 0;
while (current < size) {
var largest = current;
var left = (2 * current) + 1;
var right = (2 * current) + 2;
if (left < size && this._compare(left, largest) >= 0) {
largest = left;
}
if (right < size && this._compare(right, largest) >= 0) {
largest = right;
}
if (largest === current) break;
this._swap(largest, current);
current = largest;
}
return first;
};
2. elements 배열에 마지막 자식 노드를 할당합니다 ( 부모노드 덮어씌워지기 떄문에 first에 미리 할당하는 것입니다.)
그리고 해당 index는 0이기에 current에 0을 할당합니다.
3. while문 안에서, 인덱스를 통해서 자식 노드의 위치를 찾습니다. 이때 현재 위치가 사이즈보단 작아야함으로 이를 조건에넣습니다.
4. 만약 자식 노드 중 왼쪽과 오른쪽이 size보다 작으면서 비교결과가 크다면 largest의 값을 해당 인덱스로 할당해줍니다.
5. largest가 current랑 같다는건 교체되지 않았다는 것이므로 while문을 멈추고, 그렇지 않다면 swap을 통해 현재값과 largest값을 swap하고, 해당인덱스에 대해서 다시 비교를 합니다.
알고리즘 테스트에 사용할 최종코드는 아래와 같습니다. ( 주석은 제거하고 var => let으로 교체하였습니다)
function PriorityQueue(comparator) {
this._comparator = comparator;
this._elements = [];
}
PriorityQueue.prototype.isEmpty = function () {
return this.size() === 0;
};
PriorityQueue.prototype.peek = function () {
if (this.isEmpty()) throw new Error('PriorityQueue is empty');
return this._elements[0];
};
PriorityQueue.prototype.deq = function () {
let first = this.peek();
let last = this._elements.pop();
let size = this.size();
if (size === 0) return first;
this._elements[0] = last;
let current = 0;
while (current < size) {
let largest = current;
let left = 2 * current + 1;
let right = 2 * current + 2;
if (left < size && this._compare(left, largest) >= 0) {
largest = left;
}
if (right < size && this._compare(right, largest) >= 0) {
largest = right;
}
if (largest === current) break;
this._swap(largest, current);
current = largest;
}
return first;
};
PriorityQueue.prototype.enq = function (element) {
let size = this._elements.push(element);
let current = size - 1;
while (current > 0) {
let parent = Math.floor((current - 1) / 2);
if (this._compare(current, parent) <= 0) break;
this._swap(parent, current);
current = parent;
}
return size;
};
PriorityQueue.prototype.size = function () {
return this._elements.length;
};
PriorityQueue.prototype.forEach = function (fn) {
return this._elements.forEach(fn);
};
PriorityQueue.prototype._compare = function (a, b) {
return this._comparator(this._elements[a], this._elements[b]);
};
PriorityQueue.prototype._swap = function (a, b) {
let aux = this._elements[a];
this._elements[a] = this._elements[b];
this._elements[b] = aux;
};
사용 예시
function PriorityQueue(comparator) {
this._comparator = comparator;
this._elements = [];
}
PriorityQueue.prototype.isEmpty = function () {
return this.size() === 0;
};
PriorityQueue.prototype.peek = function () {
if (this.isEmpty()) throw new Error('PriorityQueue is empty');
return this._elements[0];
};
PriorityQueue.prototype.deq = function () {
let first = this.peek();
let last = this._elements.pop();
let size = this.size();
if (size === 0) return first;
this._elements[0] = last;
let current = 0;
while (current < size) {
let largest = current;
let left = 2 * current + 1;
let right = 2 * current + 2;
if (left < size && this._compare(left, largest) >= 0) {
largest = left;
}
if (right < size && this._compare(right, largest) >= 0) {
largest = right;
}
if (largest === current) break;
this._swap(largest, current);
current = largest;
}
return first;
};
PriorityQueue.prototype.enq = function (element) {
let size = this._elements.push(element);
let current = size - 1;
while (current > 0) {
let parent = Math.floor((current - 1) / 2);
if (this._compare(current, parent) <= 0) break;
this._swap(parent, current);
current = parent;
}
return size;
};
PriorityQueue.prototype.size = function () {
return this._elements.length;
};
PriorityQueue.prototype.forEach = function (fn) {
return this._elements.forEach(fn);
};
PriorityQueue.prototype._compare = function (a, b) {
return this._comparator(this._elements[a], this._elements[b]);
};
PriorityQueue.prototype._swap = function (a, b) {
let aux = this._elements[a];
this._elements[a] = this._elements[b];
this._elements[b] = aux;
};
let pq = new PriorityQueue((a, b) => b[0] - a[0]);
const fs = require('fs');
const input = fs
.readFileSync(__dirname + '/input.txt')
.toString()
.split('\n');
let visited = [];
const testCase = +input[0];
let favorite = [];
let selected = [];
let count = 0;
for (let t = 0; t < testCase; t++) {
const memberCnt = +input[1 + 2 * t];
favorite = input[2 + 2 * t].split(' ').map((e) => e - 1);
count = 0;
visited = new Array(memberCnt).fill(false);
for (let i = 0; i < memberCnt; i++) {
if (!visited[i]) {
selected = [i];
visited[i] = true;
dfs(favorite[i]);
}
}
console.log(count);
}
function dfs(like) {
if (!visited[like]) {
visited[like] = true;
const favOfLike = favorite[like];
if (favOfLike === like) {
count++;
} else if (visited[favOfLike]) {
const targetIndex = selected.findIndex((e) => e === favOfLike);
if (targetIndex !== -1) {
count += selected.length - targetIndex;
}
} else {
selected.push(like);
dfs(favOfLike);
}
}
}
생각했던 로직
1. 학생들은 1번 부터 n까지 번호가 주어지기 때문에, 각각의 case에서 Map을 돌릴 때, 1을 뺀 값을 통해 새로운 배열을 만듭니다. ( favortie 배열)
2. 이후 중복 작업을 제거하기 위해서 visited 배열을 만들었고, 현재 dfs에서 선택된 녀석들을 담을 selected 배열을 만들었습니다.
3. 새로운 dfs가 실행될 떄마다 selected를 초기화 시켜줬고, 각각의 케이스마다 visited와 favorite 배열을 초기화 시켰습니다.
위 코드로 해당 케이스 테스트 시 1 1 2 0 이 나옵니다..
1차 보완
일단 dfs함수가 잘못 된 부분이 많았네요..그리고 for 문 안에서 이미 좋아했떤 애를 좋아하는 경우에 대한 경우가 없었네요.. 위의 케이스에 대해선 통과 했는데 여전히 틀린 코드 뭐가 문젤까요..
let visited = [];
const testCase = +input[0];
let favorite = [];
let selected = [];
let count = 0;
for (let t = 0; t < testCase; t++) {
const memberCnt = +input[1 + 2 * t];
// 케이스마다 좋아하는 배열 초기화
favorite = input[2 + 2 * t].split(' ').map((e) => e - 1);
// 조 못이룬 사람 수
count = 0;
// 확인 한 경우
visited = new Array(memberCnt).fill(false);
for (let i = 0; i < memberCnt; i++) {
//아직 확인 안 한 사람중에
if (!visited[i]) {
// 현재 순회중인 대상
selected = [i];
visited[i] = true;
const like = favorite[i];
if (like === i) {
// 혼자 하는 놈
} else if (visited[like]) {
// 이미 탐색이 끝난 애(조를 이루거나 조가 이루어 질 수 없는 애랑 하고 싶어하면 실패)
count++;
} else {
// 나머진 탐색
dfs(like);
}
}
}
console.log(count);
}
function dfs(like) {
visited[like] = true;
const favOfLike = favorite[like];
if (favOfLike === like) {
// 혼자 하고 싶어하면 순회중인 나머진 조 못 이룸
count += selected.length;
} else if (visited[favOfLike]) {
// 이미 방문했던 애를 좋아한다면
const targetIndex = selected.findIndex((e) => e === favOfLike);
if (targetIndex === -1) {
// 순회 중이지 않다면
count += selected.length;
} else {
// 만약 대상이 현재 순회중인 애 라면
count += targetIndex;
}
} else {
// 순회 대상에 추가하고 새로운 애를 통해 순회
selected.push(like);
dfs(favOfLike);
}
}
2차보완
let visited = [];
const testCase = +input[0];
let favorite = [];
let selected = [];
let count = 0;
for (let t = 0; t < testCase; t++) {
const memberCnt = +input[1 + 2 * t];
favorite = input[2 + 2 * t].split(' ').map((e) => e - 1);
count = 0;
visited = new Array(memberCnt).fill(false);
for (let i = 0; i < memberCnt; i++) {
if (!visited[i]) {
visited[i] = true;
const like = favorite[i];
if (like === i) {
} else if (visited[like]) {
count++;
} else {
selected = [i];
dfs(like);
}
}
}
console.log(count);
}
function dfs(like) {
visited[like] = true;
const favOfLike = favorite[like];
if (favOfLike === like) {
count += selected.length;
} else if (visited[favOfLike]) {
const targetIndex = selected.findIndex((e) => e === favOfLike);
if (targetIndex === -1) {
//수정
count += selected.length + 1;
} else {
count += targetIndex;
}
} else {
selected.push(like);
dfs(favOfLike);
}
}
순환중이지 않다면의 조건을 잘못 걸었다.. selected.length+1 왜냐면 순회대상은 아직 selected배열에 안 넣었으니깐..
성능도 향상이 많이 됐다. 앞에 처음 맞춘 코드는 강사님 코드입니다.
성능차이가 나는건, 강사님의 경우 방문과 완료 두 가지 배열을 사용하고, 성공적으로 팀을 이룬 ( 사이클이 생성된 경우) 경우에 result배열에 넣는 방식을 사용하였습니다. 즉 3개의 배열에 값을 수정하면서 최종결과가 도출됐기 떄문에, 시간도 1.5배 정도 걸린 것이라 저는 생각했습니다..
DFS랑 그래프에 유독 약했는데, 혼자 풀었던 게 성능이 좋아서 기분이 좋네요,,
const fs = require('fs');
const input = fs
.readFileSync(__dirname + '/input.txt')
.toString()
.split('\n');
let testCases = +input[0];
let line = 1;
while (testCases--) {
let n = +input[line];
let graph = [0, ...input[line + 1].split(' ').map(Number)];
let visited = new Array(n + 1).fill(false);
let finished = new Array(n + 1).fill(false);
let result = [];
for (let x = 1; x <= n; x++) {
if (!visited[x]) dfs(x, graph, visited, finished, result);
}
line += 2;
console.log(n - result.length);
}
function dfs(x, graph, visited, finished, result) {
visited[x] = true;
let y = graph[x];
if (!visited[y]) {
dfs(y, graph, visited, finished, result);
} else if (!finished[y]) {
while (y !== x) {
result.push(y);
y = graph[y];
}
result.push(x);
}
finished[x] = true;
}
const fs = require('fs');
const input = fs
.readFileSync(__dirname + '/input.txt')
.toString()
.split('\n');
const n = +input[0];
const arr = [];
for (let i = 1; i <= n; i++) {
arr.push(input[i].split(''));
}
const height = [];
for (let i = n + 1; i <= n + n; i++) {
height.push(input[i].split(' ').map(Number));
}
let dx = [-1, -1, -1, 0, 0, 1, 1, 1];
let dy = [-1, 0, 1, -1, 1, -1, 0, 1];
let uniqueHeight = new Set();
let target = 0;
let result = 1e9;
let startX;
let startY;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
uniqueHeight.add(height[i][j]);
if (arr[i][j] === 'P') {
startX = i;
startY = j;
}
if (arr[i][j] === 'K') target += 1;
}
}
uniqueHeight = [...uniqueHeight].sort((a, b) => a - b);
let left = 0;
let right = 0;
let middle = 0;
let cnt = 0;
for (let i = 0; i < uniqueHeight.length; i++) {
if (uniqueHeight[i] === height[startX][startY]) {
right = i;
middle = i;
break;
}
}
let visited = [];
while (true) {
while (true) {
visited = [];
cnt = 0;
for (let i = 0; i < n; i++) visited.push(new Array(n).fill(false));
dfs(startX, startY);
if (right < uniqueHeight.length - 1 && cnt < target) right += 1;
else break;
}
if (cnt === target) {
result = Math.min(result, uniqueHeight[right] - uniqueHeight[left]);
}
left += 1;
if (left > middle ) break;
}
console.log(result);
function dfs(x, y) {
visited[x][y] = true;
if (arr[x][y] === 'K') cnt += 1;
for (let i = 0; i < 8; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny > n) continue;
if (!visited[nx][ny]) {
if (
height[nx][ny] >= uniqueHeight[left] &&
height[nx][ny] <= uniqueHeight[right]
) {
dfs(nx, ny);
}
}
}
}
문제는 배달을 하면서 각 지역마다 높이가 있는데, 배달을 하기 위해서 필요한 높이차의 최소값을 구하는 것 입니다.
3
P..
.KK
...
3 2 4
7 4 2
2 3 1
입력 예시는 위와 같은데, P는 시작점, K는 반드시 들려야하는 지점입니다.
이때 한상덕 씨는 대각선 및 좌우로 이동할 수 있으니 3에서 시작해서 4와 2를 방문하면 되니 답은 4-2 인 2가 나옵니다.
이를 알고리즘으로 구현할 때, 로직은 아래 순서 입니다.
1. 우선 입력값을 통해서, 각각의 유니크한 높이를 구한다. 이후 시작점을 찾고 시작점의 높이를 구합니다.
2. 투포인터 개념으로 접근할 건데, 유니크한 높이를 구한 배열에서 좌측포인터는 0, 우측포인터는 시작점의 높이 인댁스를 구합니다.
3. 이후 dfs를 통하여서, 각각의 지점에 포인터의 높이 범위 내의 있는 경우 방문을 진행합니다. 그리고 만약 방문 지점이 타겟 숙소인 경우 count를 올려줍니다.
4. 이때 count가 목표숙소 수보다 작다면, 높이 범위가 맞지 않아서 방문 못하는 것이기 때문에 우측포인터의 index를 증가시켜줍니다.
5. 이후 방문이 완료되면(count와 타겟수가 같다면) 우측 index값은 고정시킵니다.
6. 이후 좌측 포인터를 이동시켜서 좌측 포인터의 최소값을 찾습니다.
즉 위 문제는 투 포인터와 dfs 로직이 섞여 있습니다.
하나하나 해석하면
STEP1
const fs = require('fs');
const input = fs
.readFileSync(__dirname + '/input.txt')
.toString()
.split('\n');
const n = +input[0];
const arr = [];
for (let i = 1; i <= n; i++) {
arr.push(input[i].split(''));
}
const height = [];
for (let i = n + 1; i <= n + n; i++) {
height.push(input[i].split(' ').map(Number));
}
let dx = [-1, -1, -1, 0, 0, 1, 1, 1];
let dy = [-1, 0, 1, -1, 1, -1, 0, 1];
1. 우선 입력값을 받고, 총 개수를 특정하고, 각각의 높이값과 위치에 대한 정보를 추출해서 배열에 담습니다.
2. dfs시에 배열 내에서 상하좌우대각선 이동을 하기에 dx,dy를 통해서 총 8방위를 담아줍니다.
STEP2
let uniqueHeight = new Set();
let target = 0;
let result = 1e9;
let startX;
let startY;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
uniqueHeight.add(height[i][j]);
if (arr[i][j] === 'P') {
startX = i;
startY = j;
}
if (arr[i][j] === 'K') target += 1;
}
}
uniqueHeight = [...uniqueHeight].sort((a, b) => a - b);
1. 이후 높이값을 통해서 유니크한 높이값을 찾아줍니다. ( 포인터의 이동시에 중복된 높이는 필요없기 때문!)
2. 결과값은 우선 가능한 가장 큰 값을 할당 (1e9가 문제 제약 조건이었습니다)
3. 이후 반복문을 통해서 각각의 높으로 Set에 담고, K가 나오면 target 개수 증가, P가 나오면 시작점으로 기록
4. 마지막으로 완성된 Set을 배열로 바꾸고 오름차순으로 정렬 (오름차순이야지 포인터가 의미 있습니다)
STEP3
let left = 0;
let right = 0;
let middle = 0;
for (let i = 0; i < uniqueHeight.length; i++) {
if (uniqueHeight[i] === height[startX][startY]) {
right = i;
middle = i;
break;
}
}
let cnt = 0;
let visited = [];
while (true) {
while (true) {
visited = [];
cnt = 0;
for (let i = 0; i < n; i++) visited.push(new Array(n).fill(false));
dfs(startX, startY);
if (right < uniqueHeight.length - 1 && cnt < target) right += 1;
else break;
}
if (cnt === target) {
result = Math.min(result, uniqueHeight[right] - uniqueHeight[left]);
}
left += 1;
if (left > middle ) break;
}
console.log(result);
1. 방문 배열을 만들어줍니다. 방문 배열을 통해서 dfs로 각각의 좌측포인터와 우측포인터에 대한 탐색을 시작합니다.
2. 우측 포인터의 최소값은 시작점의 값으로 설정하고 중간지점을 설정합니다 ( 탈출 조건 용도로 중간지점 설정)
3. 이후 방문 배열(visited)과 횟수(cnt)를 선언합니다.
4. 반복문에서 dfs을 통해서 집에 도착할 경우 cnt를 증가시키고 작은 경우 right의 값을 증가, 최종적으로 cnt가 목표수와 같아지면 결과값(이전값과 비교해서 더 작으면)을 할당합니다.
5. 이후 left 값을 증가시킵니다 . 이때 초기 설정했던 middle까지만 확인하고 탈출 시킵니다.
const fs = require('fs');
const [min,max] = fs.readFileSync("./dev/stdin").toString().trim().split(' ').map(Number);
// 총 개수 구하기
let count = max - min + 1;
const primeFilter = new Array(max + 1).fill(1); //RangeError 생긴 부분
// 소수 구하기
const primeNumber = [];
for (let i = 2; i <= Math.sqrt(max); i++) {
if (primeFilter[i]) {
primeNumber.push(i);
for (let j = i ** 2; j <= max; j += i) {
if (primeFilter[j]) {
primeFilter[j] = 0;
}
}
}
}
// nono가 아닌 애들 구하기
let notNoNo = new Set();
for (let i = 0; i < primeNumber.length; i++) {
const primeDouble = primeNumber[i] * primeNumber[i];
const startPoint = Math.ceil(min / primeDouble);
for (let j = startPoint; j <= max / primeDouble; j++) {
notNoNo.add(j * primeDouble);
}
}
console.log(count - notNoNo.size);
