정수들이 들어가있는 배열 numbers
와 목표 결과값인 target
을 인자로 받는다. 모든 값을 더하거나 빼서 결과값이 target
이 나온다면 카운팅을 하고, 해당 값을 return
하면 되는 문제다.
Numbers | Target | Return |
---|---|---|
[1, 1, 1, 1, 1] | 3 | 5 |
[4, 1, 2, 1] | 4 | 2 |
function solution(numbers, target) {
let answer = 0;
const stack = [{ index: 0, sum: 0 }];
while (stack.length) {
const { index, sum } = stack.pop();
if (index === numbers.length) {
if (sum === target) answer++;
continue;
}
stack.push({ index: index + 1, sum: sum + numbers[index] });
stack.push({ index: index + 1, sum: sum - numbers[index] });
}
return answer;
}
console.log(solution([4, 1, 2, 1], 4));
DFS
방식을 사용했는데, Python
을 사용하다 와서 그런지 다른 풀이를 참고하면서 풀었다. stack
에는 index, sum
값이 들어가있고, 스택이 빌 때까지 탐색을 시작한다. 카운팅이 수행되는 조건은 index
가 numbers
배열의 길이만큼 늘어나고, 합산이 target
과 일치할 때이다. index
는 말 그대로 인덱스의 의미도 가지고 있지만, 무조건 순차적인 탐색이라 카운팅의 의미를 갖기도 한다.
push
구문을 보면 더하는 케이스와 빼는 케이스가 있는데, index
는 다음 index
로 넘어가게 되면서 +1
이 되고, sum
은 기존 값에 numbers
배열의 해당 인덱스 값을 더하거나 빼는 과정을 수행하게 된다. 나머지 문제들에 비해 상대적으로 쉬웠던 문제였던 것 같다.
tickets
배열을 받아오는데, 배열의 형태가 [['KOR', 'JPN'], ['JPN', 'USA'], ...]
와 같은 형식으로 주어져있다. 인덱스의 첫 번째 값과 두 번째 값은 각 출발지와 도착지를 의미하며, 모든 항공권을 이용하여 여행경로를 짜야 한다.
Tickets | Return |
---|---|
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] | ["ICN", "JFK", "HND", "IAD"] |
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] | ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] |
function solution(tickets) {
let routes = [];
DFS = (extra, current, route) => {
if (extra.length === 0) {
routes.push(route);
} else {
extra.forEach(([from, to], index) => {
if (current === from) {
const newExtra = extra.slice();
newExtra.splice(index, 1);
DFS(newExtra, to, route.concat(to));
}
});
}
};
DFS(tickets, "ICN", ["ICN"]);
return routes.sort()[0];
}
BFS
로 풀고 싶었는데, 생각대로 잘 안되었던 것도 있고 문제 자체가 좀 어려워서 외부 풀이를 참고해서 풀었다. 전반적인 DFS
구조를 보면 인자값으로 extra, current, route
가 들어가는 것을 볼 수 있다. 처음에 선언하는 routes
는 최종적인 경로라고 생각하면 되고, 인자로 들어가는 route
는 중간에 경로를 기억할 수 있는 tmp_route
정도로 이해하면 될 것 같다.
DFS
함수가 실행되면 extra
값이 비어있는지 확인한다. 초기값은 티켓 전체가 그대로 들어가므로 바로 else
문으로 들어가는데, extra
에 forEach
루프를 돌려 각 인덱스 내의 출발지와 도착지에 대한 연산을 시작한다. 현위치 current
에는 초기값 "ICN"
이 들어가기 때문에 첫 루프에는 출발지가 ICN
인 경우를 서칭하게 될 것이다. 조건을 충족하면 임시로 쓸 변수 newExtra
에 extra
배열을 얕은 복사해주고 복사하는 이유는 단순 대입 연산자를 이용하여 넣어버리면 기존 배열값이 바뀌기 때문이다.
그렇게 가져온 newExtra
에서 조건을 충족하는 index
를 빼줌으로써 다음 서칭에는 포함되지 않도록 만들어준다. 그리고 재귀적으로 동작하도록 DFS
를 호출하는데, 여기서 newExtra: extra, to: current, route.concat(to)
라는 의미를 담고 있다. 첫 루프에는 route
에 ICN
밖에 안들어있었는데 그 다음 목적지, 예를 들면 "JFK"
가 들어가게 되는 것이다.
그렇게 나온 routes
를 제한사항 5번을 참고하여 정렬해야 하는데, sort()
를 활용하여 정렬을 수행하고 그렇게 정렬된 routes
배열의 첫 번째 인덱스 값을 가져오기 위해 [0]
을 사용했다.
지난 번에 풀었던 백준의 바이러스 와 유사한 문제이다. 인자값으로 n, computers
를 받는데 n
은 컴퓨터의 개수, computers
는 연결 상태가 담긴 배열이다. 뭐, 예를 들어 컴퓨터가 4대라고 한다면 [[0: 1번 컴퓨터와의 연결 여부, 0: 2번 컴퓨터와의 연결 여부, 0: 3번 컴퓨터와의 연결 여부, 0: 4번 컴퓨터와의 연결 여부], [...], [...], [...]
와 같은 형태로 되는 것이다. 각 인덱스는 컴퓨터의 번호를 의미한다고 보면 되고, 그렇게 해서 컴퓨터들은 각각의 연결로 하나의 네트워크를 이루게 될 것이다. 그렇게 구성된 네트워크의 개수를 알아내면 되는 문제다.
n | computers | return |
---|---|---|
3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
function solution(n, computers) {
var answer = 0;
const visited = Array(n).fill(false);
DFS = (index, visited, computers) => {
visited[index] = true;
for (let i = 0; i < computers.length; i++) {
if (computers[index][i] === 1 && !visited[i]) DFS(i, visited, computers);
}
};
for (let i = 0; i < n; i++) {
if (!visited[i]) {
DFS(i, visited, computers);
answer++;
}
}
return answer;
}
console.log(
solution(3, [
[1, 1, 0],
[1, 1, 0],
[0, 0, 1],
])
); // local 확인용 콘솔
DFS
로 풀었는데 먼저 visited
배열은 각 컴퓨터의 방문 상태를 기록하기 위해 선언했다. 개수를 맞추기 위해 Array(n).fill(false)
로 선언했고, [false, false, ... , false]
이런식으로 될 것이다. 이렇게 초기값은 다 false
로 선언이 되었기 때문에 루프를 돌려서 첫 index
부터 DFS
탐색을 시작한다. DFS
함수를 분석해보자.
우선 방문을 기록하기 위해 visited
배열의 해당 인덱스의 값을 true
로 수정해준다. 그리고 반복문을 돌려 그 해당 인덱스와의 연결이 되어있는 경우를 찾는다. 이것이 computers[index][i]
를 의미하고, 방문 여부도 !visited[i]
를 통해 확인해준다. 그렇게 방문하지 않고 연결되어 있는 케이스를 찾아내면 재귀적으로 DFS
를 호출한다. 그렇게 다 돌면 하나의 네트워크를 다 탐색했으므로 answer
의 값을 1 증가시킨 후, 다음 네트워크를 찾게 된다.