[BOJ] 2002번 : 추월

백준 2002번 : 추월

🔗 문제 링크

https://www.acmicpc.net/problem/2002

2002번: 추월

 

---

💬 문제

 해시(hash) 에 대한 이해가 있다면 풀 수 있는 문제이지만, 만만하지 않은 문제였다.

해시에 대해 익숙하지 않다면, 아래 글을 참고해보길 바란다.

 

https://valueengine.tistory.com/55

[자료구조] 해시 (Hash)

또한, 이 문제를 풀기 위해 Map 객체 사용법에 대해 참고해보길 바란다.

https://ko.javascript.info/map-set#ref-79

맵과 셋

 

💬 문제 설명

1. 총 N개의 차량이 터널을 지난다.
   
   
2. 터널에 진입하는 순서대로 차량 번호를 적고, 나오는 순서대로 차량 번호를 적어 번호를 비교한다.
   
   - 비교를 하여 추월한 자동차의 수를 구해주면 된다
   
   - 같은 차량 번호는 존재하지 않는다 (전부 다르다)

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 자동차 수 N이 주어지고, 그 다음 줄부터 터널에 진입한 자동차 번호(2번째부터 N+1번째까지)와 터널에서 나온 자동차 번호(N+2번째부터 2N+1번째까지)가 차례대로 주어진다.

전체적으로 줄바꿈을 기준으로 잘라준 뒤, 각각을 N과 터널에 진입한 자동차 번호(tunnelIn)와 나온 자동차 번호(tunnelOut)로 할당해준다.

 

예제를 쉽게 변환하면 아래와 같다.

1번째 예제는 tunnelIn = ['a', 'b', 'c', 'd']과 tunnelOut = ['d', 'a', 'b', 'c']
2번째 예제는 tunnelIn = ['a', 'b', 'c', 'd', 'e']과 tunnelOut = ['b', 'e', 'd', 'a', 'c']
3번째 예제는 tunnelIn = ['a', 'b', 'c', 'd', 'e']과 tunnelOut = ['e', 'c', 'a', 'b', 'd']

 

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] JS로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

🔑 풀이

• 자동차 수 N과 터널에 진입한 차 tunnelIn, 터널에 나온 차 tunnelOut으로 분리해준다.
  
  
• Map 객체를 통해 tunnelIn과 tunnelOut을 각각 해시 테이블로 만들어준다.
  
  - tunelIn은 enterCar, tunnelOut은 exitCar
  
  - Map 객체에는 자동차 번호(car)와 배열 인덱스번호(i)를 key와 value로 매핑해준다
  
  
• 진입한 자동차와 비교하기 위해 exitCar에서 나온 자동차 이름(exitCarName)과 인덱스번호(exitIndex)를 추출해준다.
  
  - 첫 번째로 들어간 차(enterCar)의 인덱스번호와 나온 차의 인덱스번호를 비교해서 나온 차가 더 크면 추월한 것이다
  
  - 그리고 비교했던 차는 들어간 차(enterCar) 목록에서 삭제해준다
  

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n");
const N = parseInt(input[0]);
const tunnelIn = input.slice(1, N+1);
const tunnelOut = input.slice(N+1, N*2+1);

console.log(solution(tunnelIn, tunnelOut));

// 추월한 자동차 수 카운트
function solution(tunnelIn, tunnelOut) {
    // 해시 테이블 생성
    const enterCar = new Map();
    tunnelIn.map((car, i) => {
        enterCar.set(car, i);
    });
    
    const exitCar = new Map();
    tunnelOut.map((car, i) => {
        exitCar.set(car, enterCar.get(car));
    });

    let cnt = 0;
    for (const [exitCarName, exitIndex] of exitCar) {
        const [firstCar] = enterCar.values();
        
        if (exitIndex > firstCar) {
            cnt++;
        }
        enterCar.delete(exitCarName);
    }
    return cnt;
}

 

시간은 다음과 같이 걸렸다.

 

 

반응형

 

---

👣 예제를 참고한 풀이

예제 입력

N = 5
tunnelIn = ['a', 'b', 'c', 'd', 'e']
tunnelOut = ['b', 'e', 'a', 'd', 'c']

 

2번째 예제를 조금 변형해 위와 같은 예제가 있다고 해보자.

위 예제를 해시 테이블로 바꿔주면 아래와 같다.

tunnelIn = Map(5) { 'a' => 0, 'b' => 1, 'c' => 2, 'd' => 3, 'e' => 4 }
tunnelOut = Map(5) { 'b' => 1, 'e' => 4, 'a' => 0, 'd' => 3, 'c' => 2 }

 

for문에서 서로 어떤 값을 비교하는지 파악하기 위해 console.log를 찍어보았다.

for (const [exitCarName, exitIndex] of exitCar) {
    const [firstCar] = enterCar.values();
    console.log(`exitCarName=${exitCarName}, exitIndex=${exitIndex}, firstCar=${firstCar}`);
    
    if (exitIndex > firstCar) {
        cnt++;
    }
    enterCar.delete(exitCarName);
    console.log(cnt);
}

// 비교군
exitCarName=b, exitIndex=1, firstCar=0
1
exitCarName=e, exitIndex=4, firstCar=0
2
exitCarName=a, exitIndex=0, firstCar=0
2
exitCarName=d, exitIndex=3, firstCar=2
3
exitCarName=c, exitIndex=2, firstCar=2
3

 

터널을 나온 차 b와 e는 a보다 추월했기에 cnt를 늘려준다. 그렇지만 나온차 a와 첫번째로 들어간 차 a는 동일한 차이기에 패스해준다. 그리고 비교를 했던 나온 차(exitCarName)는 들어간 차에서 빼준다. 그 다음 나온차 d와 들어간 차 c를 비교했을 때 d가 추월했으므로 cnt를 늘려준다. 마지막으로 나온 차 c와 들어간 차 c를 비교했을 땐 같으므로 패스해준다.

 

이렇게 비교할 때 비교했던 차를 enterCar에서 빼주지 않으면 어떻게 될까? 

그럼 나온차 b와 들어간 차 a, 나온 차 e와 들어간 차 a, 나온 차 a와 들어간 차 a를 비교하는 것까지는 동일하다. 그 다음은 나온 차 d와 들어간 차 a를 비교하는데 이때까지도 cnt는 동일한 결과가 나온다.

그러나 문제는 다음부터다. 나온 차 c는 들어간 차 a와 비교하게 되며 cnt도 증가된다. exitCarName에서 a, d, c 순으로 나왔으므로 c는 a를 추월하지 않았으므로 cnt가 올라가면 안 되지만, c는 들어간 차 a와 비교하게 되므로 cnt가 증가하게 되는 것이다. 따라서 이미 비교한 차는 들어간 차(enterCar)에서 삭제해줘야 정상적인 값이 도출된다.