https://www.acmicpc.net/problem/2002
[문제 설명]
터널에 내부에서 추월한 차량의 대수를 출력하는 문제입니다.
문제를 더욱 쉽게 직관적으로 이해하기 위해 그림으로 설명 드리겠습니다.
[a, b, c, d]의 자동차들이 순서대로 터널에 진입을 하게 됩니다.
그 후
아래의 그림과 같이 차량들이 터널을 빠져 나오게 되며, [d, a, c, b] 차량 순으로 차가 빠져 나오게 됩니다.
d, c 차량이 추월을 한 경우이므로 추월한 차량은 총 2대가 됩니다.
[문제 해결]
자 그럼 문제를 어떻게 해결해야 할까요?
저 같은 경우는 터널을 입장하는 차량에 순번을 매겨준 후 기존 앞 차량보다 먼저 나왔으면 추월한 차량으로 판단했습니다.
자 이게 무슨 소리냐?
터널을 입장할때의 차량 순번들은 [a - 1, b - 2, c - 3, d - 4] 인데
가장 먼저 나온 d 차량의 순번 4가 그 뒤에 나오는 a 차량 순번 1보다 높으므로 추월한 것으로 간주 하는 것입니다.
그림으로 설명해 드리겠습니다.
d의 차량은 비교가 끝났으니 지워주고 바로 뒤에 나오는 a의 차량을 기준으로 비교를 해줍니다.
비교를 해 보았더니 a차량은 어느 뒤 차량보다 숫자가 낮으므로 추월한 차량이 아닙니다.
a 차량이 추월한지 안한지 판별이 났으니 지워주고 c차량 기준으로 뒤 차들이랑 비교를 해줍니다.
c 차량의 순번이 뒤 차량 b의 순번보다 높으니 c는 추월한 차량으로 간주 됩니다.
이렇게 되면 추월한 차량은 d, c 총 2대가 됩니다.
자 그럼 코딩을 어떻게 해야할까요?
- 위 그림 같이 차량의 이름 - 순번으로 데이터를 저장하기 위해 해쉬 맵으로 저장합니다.
- 저장된 해쉬 맵의 제일 앞 요소를 기준으로 뒷 요소들과 비교해줍니다.
- 앞 요소가 뒷 요소보다 숫자가 높다면 추월한 것으로 판단하고 pass Count를 해줍니다.
- 앞 요소의 비교가 끝나면 앞 요소를 제거 해준다.
- 마지막 요소까지 1-4번 과정을 반복
- 여기서 주의 하실점은 일반 HashMap으로 저장하게 된다면 요소들이 순서를 지키지 않으므로 LinkedHashMap을 사용 하셔야 합니다.
[정답 코드 - Java]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedHashMap;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int carNum = Integer.parseInt(br.readLine());
LinkedHashMap <String, Integer> inCar = new LinkedHashMap<>();
for(int i=1; i<=carNum; i++) inCar.put(br.readLine(), i);
int pass = 0;
for(int i=1; i<=carNum; i++){
String outCar = br.readLine();
Iterator<String> it = inCar.keySet().iterator();
while(it.hasNext()){
if(inCar.get(outCar) > inCar.get(it.next())){
pass++; break;
}
}
inCar.remove(outCar);
}
System.out.println(pass);
}
}
'PS > 백준' 카테고리의 다른 글
백준 데스 나이트 (16948) - Java (0) | 2022.07.25 |
---|---|
[백준] Java vs C++ 3613 (Java) (2) | 2022.07.12 |
[백준] Cupid (16460) - Java (0) | 2022.07.07 |
[백준] 노드 사이 거리 (1240) - Java, bfs (0) | 2022.07.05 |
[백준 17264] I AM IRONMAN (0) | 2022.06.28 |