-문제 설명-
현재 기찻길에 3개의 열차가 있고 열차들은 플랫폼에 들렸다가 다시 출구로 빠질 수 있다.
열차가 1번부터 3번까지 번호순서대로 들어온다고 했을 때, 입력 순서대로 나갈 수 있는지 없는지 판단하는 프로그램을 작성하시오.
case1) 입력값:[1,2,3] --> 출력값:true
case1:1번 기차가 플랫폼에 있다가 출구로 빠짐 ->2번 기차가 플랫폼에 있다가 출구로 빠짐->3번 기차가 플랫폼에 있다가 출구로 빠짐
case2) 입력값:[3,2,1] --> 출력값:true
case2: 1번 기차가 플랫폼에서 대기 -> 2번기차가 플랫폼에서 대기 ->3번기차가 플랫폼에 들어온 후 출구로 빠짐 -> 2번기차가 출구로 빠짐 -> 1번기차가 출구로 빠짐
case3) 입력값: [3,1,2] --> 출력값:false
case3:1번 기차가 플랫폼에서 대기 -> 2번기차가 플랫폼에서 대기 ->3번기차가 플랫폼에 들어온 후 출구로 빠짐 -> 2번기차부터 빠질 수 있기 때문에 불가능
기본 템플릿
let input = [
[1,2,3],
[3,2,1],
[3,1,2],
];
for (let i=0; i<input.length; i++){
process.stdout.write(#${i+1});
console.log(answer(input[i]));
}
기본 템플릿을 봤을때 input변수에 3개의 배열이 존재하니깐 현재 기차가 출구로 빠지는 상황이 3가지가 있다.
그리고 우리는 answer함수만 완성해주면 될 것같다.
function answer(train){
let platform = [];
}
우선 이렇게 answer함수를 만들어줄 수 있다. 이 문제의 핵심은 플랫폼에 들어가는 열차가 마치 스택의 개념과 매우 흡사하다는 것이다.
그래서 우리는 스택개념을 이용하여 문제를 풀것이다.
우선 for문을 사용해서 1,2,3의 순서로 들어오는 기차를 플랫폼에 넣어줄 것이다. 그리고 만약 넣는 과정에서 출구로 빠져야 하는 차례의 기차번호와 플랫폼에 들어온 기차번호가 같다면 그 기차는 플랫폼에서 제거해주면 되는 것이다.(제거한다는 것은 곧 출구로 빠져나가는 것을 의미)
function answer(train){
let platform = [];
let num;
for(let i=0; i<train.length; i++){
while(stack.length === 0 || stack[stack.length-1] < train[i]){
stack.push(++num)
}
}
}
while문에서 조건 설명
-
stack.length === 0
우선 플랫폼에 아무 기차가 안들어오면 안되기 때문에 1번 기차를 넣어주기 위해서 -
stack[stack.length-1] < train[i]
플랫폼에 들어온 열차중에서 처음으로 나가야 하는 열차가 있게 해주기 위해
ex) 만약 3번 열차가 나가야 하는데 2번기차 밖에 없으면 플랫폼에 3번 열차도 추가해줘야 한다.
그리고 이제 if문을 추가해서 출구로 나가야하는 순서를 가진 배열을 보면서 첫번째로 나가야하는 열차가 플랫폼 배열 맨 마지막 요소이면 플랫폼에서 삭제 해주면 된다.
function answer(train){
let platform = [];
let num;
for(let i=0; i<train.length; i++){
while(stack.length === 0 || stack[stack.length-1] < train[i]){
stack.push(++num)
}
if (stack[stack.length-1] === train[i]){
stack.pop()
} else {
return false;
}
}
return true
}
