[백준] 추월

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

2002번: 추월

---

Think🤔

실버 1

첫 번째 줄에 차가 몇 대인지 주어진다.

먼저, 소문난 명콤비의 대근이는 차가 들어가는 순서대로

       소문난 명콤비의 2인자 영식이는 차가 나오는 순서대로 적었다.

 

터널을 나왔을 때, 몇개의 차가 추월했는지 계산하는 문제이다.

 

차번호는 영어 대문자 , 숫자로 주어지고 6~8글자 이내이다.

 

규칙을 찾아보자..

 

ZG50 1

PU30 2

RI60  3

ZG20 4

ZG23 5

 

PU30 1

ZG23 2

ZG20 3

ZG50 4

RI60  5

 

들어간 대근이가 적은 차 번호의 값이 더 컸을 때, 추월한 차량을 구할 수 있다.

반복문을 돌리고 맨 마지막 차량 번호에 들어간 인덱스 값을 넣는다.

 

해쉬값으로 번호를 줘도 된다.

그리고 같은 value값을 비교해서 대근이의 key가 높으면 반환시키면 된다.

package back22y03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

public class overTake {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int carCnt = Integer.parseInt(bf.readLine());
		
		HashMap<String, Integer> inputCar = new HashMap();
		HashMap<String, Integer> outputCar = new HashMap();
		
		//대근이와 영식이 값 넣어주기
		for(int i=0; i<carCnt; i++) {
			String carNum = bf.readLine();
			inputCar.put(carNum, i+1);
		}
		for(int i=0; i<carCnt; i++) {
			String carNum = bf.readLine();
			outputCar.put(carNum, i+1);
		}
		
		int answer = 0; // 정답
		
		for(Entry<String, Integer> entry : inputCar.entrySet()) {
			entry.getValue();
			System.out.println(entry.getValue());
		}
		
	}

}

코드를 다 작성하지 못했지만, 2중 for문으로 entry set해서 받으면 받을 수 있다..

 

---

Solution✍

package back22y03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class overTake {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int carCnt = Integer.parseInt(bf.readLine());
		int answer = 0; // 정답
		HashMap<String, Integer> map = new HashMap();
		
		for(int i=0; i<carCnt; i++) {
			String inputCar = bf.readLine();
			map.put(inputCar, i);
		}
		
		int[] outputCar = new int[carCnt];
		
		for(int i=0; i<carCnt; i++) {
			String input = bf.readLine();
			outputCar[i] = map.get(input); //들어갔던 차, 몇번째 들어갔는지 outputCar에 담아준다
		}
		System.out.println(map);
		System.out.println(Arrays.toString(outputCar));
		
		for(int i=0; i<carCnt; i++) {
			for(int j=i+1; j<carCnt; j++) { // 이미 나간 차 비교 할 필요 없음
				if(outputCar[i] > outputCar[j]) { //들어갔던차가 먼저 들어간 차 보다 빨리 나왔으면
					answer++;	// 증가시키고 
					break;		// 끝내고 다음 차 비교한다.
				}
			}
		}
		System.out.println(answer);
	}

}

---

Review🤩

Set으로 밸류값 두개 다 받아서 같은 키값의 value를 비교해서 먼저 들어간 차의 value가 높으면 구할 수 있는 방법

HashMap을 두개 안쓰더라도 get을 이용해서 같은 차가 들어간 순위를 배열을 이용해서 넣어줘서 구할 수 있는 문제..

구글 답안 참조...!!

---