문제 출처
나의 풀이 (실패)
경우의 수를 나눠 완전탐색을 해야 할 것 같은데, 아직 부족하다.
function solution(n, weak, dist) {
const wl = weak.length
const g = {}
for(let i=0; i<wl; i++){
for(let j=0; j<wl; j++){
if(i == j) continue
const s = weak[i],
e = weak[j],
f = (s < e) ? Math.abs(s - e) : Math.abs(e - s),
r = (s < e) ? Math.abs(s + (n - e)) : Math.abs(e + (n - s))
if(f > r) g[`${s}to${e}`] = r
else g[`${s}to${e}`] = f
}
}
console.log(g)
let ch = new Array(dist.length).fill(0)
// ...
}
console.log(solution(12, [1, 5, 6, 10], [1, 2, 3, 4])) // 2 다른 풀이 1 (76/100, 시간초과)
js에서 이렇게 비트마스크를 사용해 완전 탐색하면 시간초과가 발생한다.
(visited & (1 << i))가 falsy일 때 진입해서
visited | (1 << i)의 값들을 수집한다.
비트마스크는 너무 어렵다.
function solution(n, weak, dist) {
let wl = weak.length // 점검해야 할 외벽의 개수
let dl = dist.length
// (1 << num) === (2 ** num)
// 각 외벽을 (2^i)로 표현
let n_bit = 1 << wl
dist.sort((a,b) => b - a) // 내림차순 정렬
// dist 요소 하나하나를 depth로 본다.
// 정확히는 dist의 index를 depth로 설정
let depth = 0
let queue = []
// 예를 들어 내림차순한 dist = [4, 3, 2, 1] 이면
// dist[0]부터 dfs 탐색 시작
// dist[0]==4 이면, 즉 "각 친구가 1시간 동안 이동할 수 있는 거리"가 "4"일 때의 모든 경우를 탐색하면 된다.
queue.push(0)
while(queue.length > 0 && depth < dl){
let curLen = queue.length
while(curLen--){ // 현재 depth의 모든 경우를 검사한다.
// console.log(queue, queue[0])
let visited = queue.shift()
for(let i=0; i<wl; i++){ // 점검 해야 할 외벽 개수
// AND 비트 연산자(&)는 두 개의 피연산자의 각 자리마다 대응하는 비트가 모두 1일 경우에만 1을 반환
console.log(visited, visited.toString(2), (1 << i), (1 << i).toString(2), (visited & (1 << i)))
/** 예를 들어 visited == 3, (1<<i) == 1, 2, 4, 8 이면
* visited == 0011, (1<<0) == 0001 => visited & (1<<0) == 0001 == 1
* visited == 0011, (1<<1) == 0010 => visited & (1<<1) == 0010 == 2
* visited == 0011, (1<<2) == 0100 => visited & (1<<2) == 0000 == 0
* visited == 0011, (1<<3) == 1000 => visited & (1<<3) == 0000 == 0
*
* 예를 들어 (1<<3)에서 1000이면 점검해야 할 외벽 개수 wl 중에서 4번째에 해당하는 외벽을 점검 완료했다는 의미.
*
* 특정 노드 visited에 대해, wl 개의 외벽 중에서
* 첫번째 외벽을 점검완료했을 때,
* 두번째 외벽을 점검완료했을 때,
* 세번째 외벽을 점검완료했을 때,
* 네번째 외벽을 점검완료했을 때,
*
* ... 이렇게 경우의 수를 뻗어나가는 것이다.
*
* 이렇게 경우의 수를 나눠 현재 노드 visited와 1<<i를 & 연산했을 때의 값이 Truthy 이면 검사되었다고, falsy 이면 검사되지 않은 경우라고 임의로 구분
*/
if(!(visited & (1 << i))){ // (visited & (1 << i))의 값이 0이면 == 0000이면 ==> 현재 위치가 검사되지 않은 외벽이면
// 비트 논리 연산자 OR :| => 비트단위로 OR 연산을 한다. 둘중 하나라도 1이면 결과가 1이다. 둘다 0일때만 결과가 0이다.
// (visited & (1 << i))의 값이 0인 애들에 한해서 (visited | (1 << i)) 를 변수 t에 할당
/**
* 예를 들어 visited == 3 일때
* visited == 0011, (1<<2) == 0100 => visited & (1<<2) == 0000 == 0 => visited | (1<<2) == 0111 == 7
* visited == 0011, (1<<3) == 1000 => visited & (1<<3) == 0000 == 0 => visited | (1<<3) == 1011 == 11
*/
let t = visited | (1 << i) // 현재 검사되지 않은 그 외벽 위치를 t에 할당
let next = (i + 1) % wl
console.log(i, t, (i + 1) % wl)
// i=2, t=7, next=3
// i=3, t=11, next=0
// i가 끝지점이 아닌 경우는 무조건 i < next 이다.
let val = i < next ? weak[next] - weak[i] : n - weak[i] + weak[next]
console.log(i, t, next, val)
// i=2, t=7, next=3, val=4
// i=3, t=11, next=0, val=3
// val <= dist[depth] 거리가 남으면 친구들을 더 데려갈 수 있으니까
//t에 대해서 더 탐색할 수 있는지 판단한다. !(t & (1 << next))
// 더 탐색할 수 있으면 위 과정을 반복해주고
while(val <= dist[depth] && !(t & (1 << next))){
t |= (1 << next)
next = (next + 1) % wl
val = i < next ? weak[next] - weak[i] : n - weak[i] + weak[next]
}
// n_bit - 1에 도달했으면 정답을 반환한다.
if(t == n_bit - 1) return depth + 1 // 모든 위치가 검사되었다면 종료
if(visited != t) queue.push(t) // 추가로 검사할 위치가 있으면 추가
}
}
}
++depth
}
return -1
}다른 풀이 2 (96/100, 1개 시간초과)
마찬가지로 비트마스크 풀이(+dfs)지만, js에서는 시간초과가 발생한다.
++아래 풀이를 공부해보면 비트마스크에 대해 조금 이해할 수 있다.
방문 처리 : visited |= (1 << nextPos)
전부 방문되었는지 확인 : (visited == (1 << Weak.length) - 1)
특정 정점이 방문되었는지 아닌지 : visitedt & (1 << i)
예를 들어 4개의 경우의 수를 고려한다면
2^4 == 16 == 10000
2^4 - 1 == 1<<4 -1 == 11111
4개 중에서 예를 들어 0번째에 전기를 켜면 2^0 == 1 == 00001 이므로
OR 연산자(|)를 사용해서 방문 처리를 해주면 10001이된다.
그리고 AND 연산자(&)를 사용해서 방문 여부를 확인할 수 있게 된다.
비트마스킹 정리
정리하자면,n개의 원소로 이루어진 집합에 대해
1. 부분 집합의 개수 :1 << n
2. 모든 집합을 사용했는지 여부 확인하려면 :visited == ((1 << n) - 1)
3. 특정 원소가 있는지 확인하려면 :i & (1 << j)
(i 비트 안에 j 비트 자리가 1인지 확인하고 싶을 때, 방문했다면 1일 것이고 아니라면 0일 것이다. 위 문제에서 visited가 i에 해당한다.)
4. 원소를 추가하고 싶다면 :i | (1 << j)
(i 비트 안에 j 비트 자리를 1로 만든다. 위 문제에서 방문 처리 로직에 사용되고, visited가 i에 해당한다.)
5. 원소를 삭제하고 싶다면 :i & ~(1 << j)
(i 비트 안에 j 비트 자리를 0으로 만든다. 방문한 뒤 재귀를 끝낸 뒤에 다시 방문 처리를 미처리로 변경해줄 때 사용할 수 있다. 근데 js에서는 에러가 발생한다. 자료형 크기 떄문인듯. 32비트 이상 표현할 수 없어서..?)
=> 각각의 값을 toString(2)로 여러번 적용하지 말고 10진수로 비트 연산을 모두 끝낸 다음에 toString(2) 메서드를 한번만 사용하면 에러 없이 사용할 수 있다.let t = ((1 << 4) - 1) _ let f0 = 1 << 0 let f1 = 1 << 1 let f2 = 1 << 2 let f3 = 1 << 3 _ console.log((t & ~f0).toString(2)) // 1110 console.log((t & ~f1).toString(2)) // 1101 console.log((t & ~f2).toString(2)) // 1011 console.log((t & ~f3).toString(2)) // 0111
// n : 1 이상 200 이하 (공간의 길이)
// weak : 1 이상 15 이하
// dist : 1 이상 8 이하 (== 친구는 최대 8명)
// 문제에서는 시계/반시계 모두 가능하다고 나와 있지만,
// 반시계는 고려할 필요가 없다. 단지 거리만 계산하면 된다.
let N
let Weak
let Dist
let MinCnt
function solve(cnt, pos, visited){
// 사용한 친구의 수 : cnt
// 이 친구의 시작위치 : pos
// 방문 여부 : visited
// 친구 수는 결국 dist 배열의 원소 개수이다.
// 그걸 넘어갔다는 건 모든 친구를 사용했다는 의미이므로 안 된다.
if(cnt > Dist.length) return
// 그리고 사실 cnt가 MinCnt 보다 크다면 더 이상 진행할 이유가 없다.
if(cnt >= MinCnt) return
// 이 친구가 1시간 동안 이동할 수 있는 거리에 있는 모든 취약점을 방문했다고 표시해야 한다.
// 시작지점부터 모든 지점을, 방문 가능한지 확인하기 위해 Weak 크기만큼 반복
for(let i=0; i<Weak.length; ++i){
// 다음에 방문해야 하는 위치 (방문할 위치)
// 시작 위치는 항상 처음이 아닐 수 있다.
// 중간지점부터 시작하면, 예를 들어 [1, 5, 6, 10] 에서 5에서 시작했다면
// 5에서 6으로 갈 수 있는지 5에서 10으로 갈 수 있는지 5에서 1로 갈 수 있는지... 체크해줘야 한다.
// 0을 넘어가는 경우의 index를 계산해줘야 하므로 %로 나머지 연산자를 활용해야 한다.
let nextPos = (pos + i) % Weak.length
// 이제는 이동 할 거리를 구하면 된다.
// 웬만하면 Weak[nextPos]가 Weak[pos] 보다 크지만, 인덱스가 넘어가는 경우에는 거리를 구하기 위해 n에서 빼준 값과 더해주면 된다.
let diff = Weak[nextPos] - Weak[pos]
if(nextPos < pos) diff += N
// diff = nextPos < pos ? Weak[nextPos] - Weak[pos] : N + Weak[nextPos] - Weak[pos]
// 방문을 못하는 경우
if(diff > Dist[Dist.length - cnt])
break // 더 진행할 이유가 없으므로 종료
// 방문할 수 있는 경우
visited |= 1 << nextPos // 방문했다고 표시 (1을 왼쪽으로 nextPos 만큼 이동해주고 or 연산을 해주면, nextPos에 해당하는 비트만 1로 켜지게 된다.)
}
// 여기까지 방문 가능한 경우를 전부 표시해줬는데
// (1 << Weak.length - 1) : 모든 비트가 취약점의 개수만큼 켜진 값
// 예를 들어 Weak.length == 4이면
// (1 << Weak.length).toString(2) == 10000
// ((1 << Weak.length) - 1).toString(2) == 01111
// 즉 4개 경우가 전부 1인 경우, 전부 방문했다는 의미이므로
if(visited == (1 << Weak.length) - 1){
// visited가 이 값과 같다는 건, 모든 비트가 1로 켜졌다는 의미이고
// 방문을 전부 했다는 의미이므로
// MinCnt = Math.min(MinCnt, cnt)
// 위에서 가지치기를 했으므로 여기서 min을 계산할 필요도 없다.
MinCnt = cnt
return
}
// 아직 다 방문하지 않았다고 하면 재귀호출로 방문을 시도한다.
for(let i=0; i<Weak.length; ++i){
// 이미 방문한 위치에서는 시작할 필요가 없다.
// 그래서 방문 여부 확인
// 1을 i 만큼 shift 하면서 그 해당 위치의 비트가 켜져있는지 확인.
// 해당 위치에 비트가 켜져 있다면, 그 취약점은 이미 방문한 것이므로 건너 뛴다.
if(visited & (1 << i)) continue
// 방문하지 않은 곳이라면 이 위치에서 시작. (친구를 한 명 늘려서, 방문 여부는 visited에 담겨 있을 것이므로)
solve(cnt + 1, i, visited)
}
}
function solution(n, weak, dist){
// dis를 오름차순으로 정렬한다.
dist.sort((a,b) => a - b)
// 매개변수를 전역변수로 갖고 있자
N = n
Weak = weak
Dist = dist
MinCnt = Infinity // 사실 dist의 최대 길이가 8이므로 8보다만 크면 된다.
// 최초 부를 때는 시작 위치를 다르게 해줘야 한다.
// 각각의 취약 위치에서 시작한다. Weak[0], ..., Weak[Weak.length-1]
for(let i=0; i<Weak.length; ++i){
// 친구 1명을 써서, i 위치에서, 아직 방문한 곳이 없으므로 0으로 시작
solve(1, i, 0)
}
// 모든 친구를 사용했는데 전부 방문을 못했다면
if(MinCnt == Infinity) return -1
return MinCnt
}다른 풀이 3 (통과)
순열을 사용한 완전탐색 풀이
인원 수가 8명으로 제한되어 있기에 모든 순열을 구해서 시간초과가 발생하지 않는다.
js에서는 순열을 직접 구현해줘야 한다.
function solution(n, weak, dist){
const len = weak.length
// 순차 접근 배열의 크기는 ((len * 2) - 1)
// 예를 들어 마지막 배열 Weak[len-1] 에서 len만큼 구하려면 weak[len-1]을 포함해 len이 되어야 하므로
// 기존 len에 (len - 1) 값이 더 필요하므로 ((len * 2) - 1)
const linear_weak = new Array(len*2 - 1).fill(0)
for(let i=0; i<(len*2)-1; i++){
linear_weak[i] = i < len ? weak[i] : weak[i-len] + n
}
// 예를 들어 weak=[1,5,6,10] 일 때 linear_weak=[1,5,6,10,13,17,18]
// 우리가 원하는 건 친구 간 거리이며, 시작 지점에 따라 index가 0으로 초기화될 수 있는데 (원형리스트 개념을) => 그 값들을 선형적으로 표현한 것.
dist.sort((a,b) => b - a)
for(let i=1; i<=dist.length; i++){
const permutation = getPermutation(dist, i)
// 선택 가능한 친구 수가 늘어날 수 있으므로 배열 형태
for(const permu of permutation){
for(let j=0; j<len; j++){
let line = linear_weak.slice(j, len + j)
for(const p of permu){
const coverage = line[0] + p // 경로 시작점과 현재 인원의 작업 거리를 더한 값
line = line.filter(e => e > coverage) // 값이 크다는 건 도달할 수 없다는 의미이므로
if(!line.length) return i // 전부 도달할 수 있으면 그떄가 최소 인원이므로 반환
}
}
}
}
return -1
}
// 순열
const getPermutation = (arr, n) => {
if(n === 1) return arr.map(el => [el])
const result = []
arr.forEach((fixed, idx, origin) => {
const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)] // 현재 아이템(fixed)만 사용하고 나머지 값들을 다시 선택할 수 있으므로
const perms = getPermutation(rest, n - 1)
const attached = perms.map(perm => [fixed, ...perm])
result.push(...attached)
})
return result
}
console.log(solution(12, [1, 5, 6, 10], [1, 2, 3, 4])) // 2 다른 풀이 4 (통과)
엄청 빠른 풀이..
순열이 필요하긴 한데,
사실 이미 오름차순이 되어 있는 배열에 대해서 ++ 형태로의 조합만 구하면 되기 때문에 순열로 랜덤하게 뽑을 필요없이 인덱스를 1씩 증가시켜 순열 경우의 수를 구하면 된다.
function solution (n, weak, dist) {
dist.sort((a, b) => b - a);
for (let i = 0; i < dist.length; i++) {
for (let j = 0; j < weak.length; j++) {
let tempWeak = weak.map((_, c) => weak[(j + c) % weak.length] + (j + c >= weak.length ? n : 0));
let tempDist = dist.slice(0, i + 1);
/**
console.log(tempWeak, tempDist)
* [ 1, 5, 6, 10 ] [ 4 ]
* [ 5, 6, 10, 13 ] [ 4 ]
* [ 6, 10, 13, 17 ] [ 4 ]
* [ 10, 13, 17, 18 ] [ 4 ]
* [ 1, 5, 6, 10 ] [ 4, 3 ]
* [ 5, 6, 10, 13 ] [ 4, 3 ]
*/
for (let k = 0; k <= i; k++) {
const range = tempWeak[0] + tempDist[0];
let rangeIn = 0;
for (let m = 0; m < tempWeak.length; m++) {
if (tempWeak[m] <= range) {
rangeIn++;
} else {
break;
}
}
for (let n = tempDist.length - 1; n >= 0; n--) {
// 가능한 거리면
if (tempWeak[rangeIn - 1] - tempWeak[0] <= tempDist[n] && n !== 0) {
tempDist.splice(n, 1);
break;
} else if (n === 0) {
tempDist.shift();
}
}
tempWeak.splice(0, rangeIn);
// 배열에 남아 있지 않다는 건 전부 가능한 거리라는 의미이므로
if (tempWeak.length === 0) {
return i + 1;
}
}
}
}
return -1;
}참고
[프로그래머스] 외벽 점검
카카오 코딩 테스트 - 외벽점검 (C++ 풀이)
비트마스크 (BitMask) 알고리즘
https://medium.com/@wooleejaan