[JAVA] 백준 2002번: 추월

<문제>

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

2002번: 추월

< 풀이 1: Hashmap 사용 ❌>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//추월
public class P2002 {
	static String input[];
	static String output[];
	static int n;
	static int count=0;
	
	static void find(String num,String arr[]) {
		int index=0;
		boolean passed=true;
		
		for(int i=0;i<output.length;i++) {
			if(output[i].equals(num)) {
				index=i;
				break;
			}
		}
		if(index==0) {
			count++;
		}
		else {
			for(int i=0;i<arr.length;i++) {
				for(int j=0;j<index;j++) {
					if(arr[i].equals(output[j])) {
						passed=false;
						break;
					}
					else
						passed=true;
				}
				if(passed) {
					count++;
					break;
				}
			}
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine()); //차 대수 입력받음
		input=new String[n]; //들어가는 순서
		output=new String[n]; //나오는 순서 

		for(int i=0;i<n;i++) {
			input[i]=br.readLine();
		}
		for(int i=0;i<n;i++) {
			output[i]=br.readLine();
		}
		for(int i=1;i<input.length;i++) {
			String arr[]=new String[i];
			for(int j=0;j<=i-1;j++) {
				arr[j]=input[j];
			}
			find(input[i],arr); //find 함수에 현재 값과 현재 값보다 앞에 있는 값들을 저장한 배열(arr)을 매개변수로 전달
		}
		System.out.println(count);
	}

}

 

✏️ 풀이 방법

 

 String input = { a,b,c,d } , String output= { d, a, c, b } 일 때 

input 배열에서 c 값의 경우 앞에 있는 값이 { a, b } 이다.

그렇다면 output 배열에서 c 보다 앞에 a, b 가 있는지 확인하여 

값이 하나라도 없는 경우에는 count를 증가하는 식으로 코드를 구성했다.

하지만, 문제를 풀면서도 이렇게까지 복잡하게 안해도 될 것 같은데? 하는 

생각이 들어 다른 풀이들을 찾아봤다. 

 

< 풀이 2: Hashmap 사용>

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Map<String, Integer> map = new HashMap<>();
        int count = 0;

        for (int i = 0; i < N; i++) {
            map.put(br.readLine(), i); // (a,0),(b,1),(c,2) 의 형식으로 저장됨
        }
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            arr[i] = map.get(input); // 입력 받은 값으로 value를 찾아 arr 배열에 저장 
        }

        for(int i = 0; i< N-1; i++){
            for(int j = i+1; j< N; j++){
                if(arr[i] > arr[j]){ // 현재 값이 뒤에 있는 배열 값보다 크면 
                    count++;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}

 

현재 값이 뒤에 있는 배열 값보다 크다 => 추월했다 라는 뜻

추월한 차의 개수를 증가시켜주고, 클 때마다 증가시키는 것이 아니므로 바로 break 를 해준다. 

이렇게 해시맵을 이용해서 풀면 훨씬 간단하고, 시간도 많이 줄어든다 !

 

✍🏻 느낀점

 

해시맵을 진작에 알았더라면 훨씬 깔끔하고 쉽게 풀었을텐데..!

이제라도 해시맵에 대해 배웠으니,

앞으로 비슷한 문제가 나올 때 잘 활용해야겠다. 

 

참고 블로그

---

https://today-retrospect.tistory.com/204