거의 매일 알고리즘 문제를 풀긴하지만 leetcode에서 처음으로 hard문제를 푼 기념으로 블로깅을 해봅니다.
또한 개인적으로 문제를 푸는 방법이 이상하다 생각하여 정리해보려 합니다.
815. Bus Routes
- Bus Routes
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Example 2:
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
Constraints:
1 <= routes.length <= 500.
1 <= routes[i].length <= 105
All the values of routes[i] are unique.
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
독해 시간
영어가 많아서 당황스럽긴 하지만 쉽게 설명하면 버스가 정류장을 돌고 나는 source에서 target까지 갈 때 버스를 최소한의 갈아타는 횟수를 구하는 문제
단, 갈아타지 못하면 -1 리턴
한국어 시간
자 이제 코드를 작성하기 전에 한국말로 내가 뭘 해야하는 지 적어봅니다.
대충 이렇게 적어봅니다.
코딩 시간
1트
const numBusesToDestination = function(routes,source,target){
let lines = {}
routes.forEach((route,idx)=>{
route.forEach((stop)=>{
lines[stop] = lines[stop] ? [...lines[stop], idx] : [idx]
})
})
let queue= [[source,0]]
let checked = {}
while(queue.length){
let [cur,cnt] = queue.shift()
if(checked[cur])continue
if(cur === target)return cnt
checked[cur] = true
lines[cur].forEach((idx)=>{
routes[idx].forEach((stop)=>{
queue.push([stop,cnt+1])
})
routes[idx] = []
})
}
return -1
}
매우 아름다운 코드에 대한 리트코드의 답변은 시간초과
2트
const numBusesToDestination = function(routes,source,target){
let lines = {}
routes.forEach((route,idx)=>{
route.forEach((stop)=>{
lines[stop] = lines[stop] ? [...lines[stop], idx] : [idx]
})
})
let queue= [[source,0]]
let pointer = 0
let checked = {}
while(queue[pointer]){
let [cur,cnt] = queue[pointer]
pointer++
if(checked[cur])continue
if(cur === target)return cnt
checked[cur] = true
lines[cur].forEach((idx)=>{
routes[idx].forEach((stop)=>{
queue.push([stop,cnt+1])
})
routes[idx] = []
})
}
return -1
}숨은 그림 찾기
shift()부분을 pointer로 바꿔줌
통과
1트 코드는 왜 통과가 안된 것인가요 ?
야매아닌 야매 방법인데 pointer를 둬서 자바스크립트가 하는 일을 줄여주는 것이다.
shift 메소드의 경우 최악일때는 O(n)의 복잡도를 가지기 때문에 pointer index보다 일을 많이한다. 그렇기에 shift를 쓰면 시간복잡도가 초과하는 것
사실 정식으로 이 문제를 풀려면
// 각각의 노드, 노드의 data와 다음 노드를 가리키고 있다.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// 큐 클래스
class Queue {
constructor() {
this.head = null; // 제일 앞 노드
this.rear = null; // 제일 뒤 노드
this.length = 0; // 노드의 길이
}
enqueue(data) { // 노드 추가.
const node = new Node(data); // data를 가진 node를 만들어준다.
if (!this.head) { // 헤드가 없을 경우 head를 해당 노드로
this.head = node;
} else {
this.rear.next = node; // 아닐 경우 마지막의 다음 노드로
}
this.rear = node; // 마지막을 해당 노드로 한다.
this.length++;
}
dequeue() { // 노드 삭제.
if (!this.head) { // 헤드가 없으면 한 개도 없는 것이므로 false를 반환.
return false;
}
const data = this.head.data; // head를 head의 다음 것으로 바꿔주고 뺀 data를 return
this.head = this.head.next;
this.length--;
return data;
}
// head를 반환하는 함수
front() { // head가 있을 경우 head의 data를 반환.
return this.head && this.head.data;
}
//큐의 모든 원소를 반환하는 함수
getQueue() {
if (!this.head) return false;
let node = this.head;
const array = [];
while (node) { // node가 없을 때까지 array에 추가한 후 반환해준다.
array.push(node.data);
node = node.next;
}
return array;
}
}Queue 참고 블로그 - 감사합니다.
JS는 자체적으로 Queue가 없기 때문에 이렇게 엄청 긴 코드는 작성해주고 이 큐를 가져다가 사용해야한다. 하지만 나는 시간이 없기 때문에 index로 빠르게 접근해서 해결해주었다.
