[JAVA] 백준 추월

문제 설명

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.
소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.
N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

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

2002번: 추월

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이

www.acmicpc.net

내 풀이 과정

가장 먼저 그리디한 방법을 떠올려 보았다.

먼저 들어간 차를 A, 늦게 들어간 차를 B라고 할 때, B가 A보다 먼저 나오면 B를 추월한 차라고 판단하는 방법이다.

차량의 대수는 최대 1000이므로, 1000 * 1000 = 1000000 이므로 시간 복잡도도 만족할 것이었다.

하지만 이중 for문을 안 써도 뭔가 풀릴 것 같다는 직감에 다른 방법을 몰색해보기로 하였다.

~~(일종의 홍대병)~~

첫 번째 시도 - 순위 차이

순위	들어온 순서	나가는 순서	순위 차이(exit - enter)
1	A	D	3
2	B	A	-1
3	C	C	0
4	D	B	-2

위의 표와 같이 (나간 순서) - (들어온 순서)를 했을 때, 음수가 아닌 값이 나오면 추월한 차량이라고 판단하는것이다.

위의 표는 D가 A, B, C를 추월하였으며, C가 B를 추월하였으므로 C와 D가 추월한 차량이 된다.

이때의 순위 차이는 둘 다 음수가 아니므로 추월 차량의 개수는 2가 된다.

첫 번째 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	private final static Scanner input = new Scanner(System.in);
	private static int carNum, answer = 0;
	private static Map<String, Integer> enterCar = new HashMap<>();
	private static String[] exitCar = new String[1010];
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// given
		carNum = input.nextInt();
		input.nextLine();
		for(int i = 0; i < carNum; ++i)
			enterCar.put(input.nextLine(), i);
		for(int i = 0; i < carNum; ++i)
			exitCar[i] = input.nextLine();
		
		// when
		for(int i = 0; i < carNum; ++i) 
			if(enterCar.get(exitCar[i]) - i >= 0 )
				answer++;

		// then
		System.out.println(answer);
	}
}

하지만 틀렸다!

두 번째 시도 - 순위 차이 + 조건문

다시 생각해보니 첫 번째 시도는 추월과 연관없는 차량들도 추월한 차로 인식될 수 있다는 것을 깨달았다.

다음이 그 예시이다.

순위	들어온 순서	나가는 순서	순위 차이(exit - enter)
1	A	B	1
2	B	A	-1
3	C	C	0
4	D	D	0

위의 표에서는 실제 추월한 차는 B이지만, C, D의 순위 차이가 0이므로 추월한 차량의 수가 3으로 나온다.

이처럼 추월과 연관없는 차는 계산에서 제거하는 로직을 추가하였다.

각 for문마다 순위 차이를 더하는 변수를 추가하여, 해당 변수가 0일 때는 추월 차량으로 계산하지 않는 로직이다.

두 번째 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	private final static Scanner input = new Scanner(System.in);
	private static int carNum, answer = 0;
	private static Map<String, Integer> enterCar = new HashMap<>();
	private static String[] exitCar = new String[1010];
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// given
		carNum = input.nextInt();
		input.nextLine();
		for(int i = 0; i < carNum; ++i)
			enterCar.put(input.nextLine(), i);
		for(int i = 0; i < carNum; ++i)
			exitCar[i] = input.nextLine();
		
		// when
		int temp = 0;
		for(int i = 0; i < carNum; ++i) {
			int diff = enterCar.get(exitCar[i]) - i;
			temp += diff;
			if(temp != 0 && diff >= 0)
				answer++;
		}

		// then
		System.out.println(answer);
	}
}

~~앗 또 틀렸다!~~

세 번째 시도 - 추월 당한 차량의 시점

왜 틀렸나 생각해봤는데 좋은 반례가 있었다.

내 앞의 n개의 차량을 추월해도, 내 뒤의 n + 1개 차량이 나를 추월하면 추월 차량으로 집계되지 않는다는 것이 그 예시였다.

순위	들어온 순서	나가는 순서	순위 차이(exit - enter)
1	A	C	2
2	B	D	2
3	C	B	-1
4	D	A	-3

위에서 추월한 차량은 B, C, D이지만, 내 코드에서는 2개의 차량만 잡힌다.

그래서 나는 생각을 바꿔서 추월 당한 차량 시점에 맞추기로 했다.

추월 당한 차량의 입장에서 들어올 때와 나갈 때의 순서 차가 바로 자신을 추월한 차량의 대수이기 때문이다.

세 번째 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	private final static Scanner input = new Scanner(System.in);
	private static int carNum, answer = 0;
	private static Map<String, Integer> enterCar = new HashMap<>();
	private static String[] exitCar = new String[1010];
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// given
		carNum = input.nextInt();
		input.nextLine();
		for(int i = 0; i < carNum; ++i)
			enterCar.put(input.nextLine(), i);
		for(int i = 0; i < carNum; ++i)
			exitCar[i] = input.nextLine();
		
		// when
		int overCar = 0;
		int big = 0;
		for(int i = 0; i < carNum; ++i) {
			int diff = enterCar.get(exitCar[i]) - i;
			overCar += diff;
			if(diff < 0) {
				big = (big > Math.abs(diff) ? big : Math.abs(diff));
				if(overCar == 0) {
					answer += big;
					big = 0;
				}
			}
		}

		// then
		System.out.println(answer);
	}
}

또....또....틀렸다.......

네 번째 시도 - 체크 포인트

반례 찾는 시간만 20분정도 걸린 것 같다.

그러다 좋은 반례를 발견하였다.

순위	들어온 순서	나가는 순서	순위 차이(exit - enter)
1	A	B	1
2	B	E	3
3	C	A	-2
4	D	D	0
5	E	C	-2

위의 표를 보면 추월한 차량은 B, D, E임을 알 수 있다.

하지만 내 로직에서는 A 앞으로 2대의 차량, C 앞으로 2대의 차량이 지나갔으므로 답이 2가 나온다는 것을 알 수 있다.

그래서 문득 기가 막힌 방법을 떠올렸다. ~~(이 방법 아니었으면 블로그에 올리지도 않았다.)~~

들어온 차량의 나간 순서를 확인한다.]
이 값은 check(초기값은 0)값과 비교한다.
만약 check보다 나간 순서 값이 크다면, check값을 차량의 나간 순서 값으로 갱신한다.
만약 check보다 나간 순서 값이 작다면, 추월한 차량으로 판단한다.

위의 로직을 따르면 바로 아래 표와 같이 된다.

차량 번호	나간 순서	check값(초기값 0)	추월한 차량인가?
A	3	3으로 갱신	x
B	1	3	o
C	5	5으로 갱신	x
D	4	5	o
E	2	5	o

네 번째 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	private final static Scanner input = new Scanner(System.in);
	private static int carNum, answer = 0;
	private static String[] enterCar = new String[1010];
	private static Map<String, Integer> exitCar = new HashMap<>();
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// given
		carNum = input.nextInt();
		input.nextLine();
		for(int i = 0; i < carNum; ++i)
			enterCar[i] = input.nextLine();
		for(int i = 0; i < carNum; ++i)
			exitCar.put(input.nextLine(), i);
		
		// when
		int check = 0;
		for(int i = 0; i < carNum; ++i) {
			if(check > exitCar.get(enterCar[i])) answer++;
			else check = exitCar.get(enterCar[i]);
		}

		// then
		System.out.println(answer);
	}
}

~~아 존맛~~

개발로 먹고 살고 싶다