[BOJ] 2002 추월

추월

풀이

• 처음에 문제가 이해가 안가서 뭔소리야...2차선이야? 하면서 헤맸었다

• 곰곰이 생각해보니 그냥 들어간 순서랑 나온순서가 같은지 확인하면 되고, 확인한 애들은 하나씩 지워주면서 비교하면 됐다.

• 처음 N개를 큐에 넣고, 그 후 N개를 하나씩 입력받을 때, 입력받은 값이 큐의 헤드에 있는 값과 같으면 순서가 맞는 것이므로 queue.poll() 해 주고, 큐의 헤드에 있는 값과 다르면 answer +1 한 다음 큐에서 그 값을 찾아서 지워줬다.

• 근데 이 방식은 아마 N의 갯수가 늘어나면 시간 초과가 날 것 같다.(다른 경우, 큐에서 탐색하는 과정이 있어서)

• 그래서 해시맵을 쓰는 방법이 있다는 것을 알았음 ! 얘로 하니까 132ms로 좀 빠른 것을 알 수 있었다~!

  😃 큐 쓴 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
          int answer = 0;
          Queue<String> queue = new LinkedList<>();
          for(int i=0;i<N;i++){
              String car = br.readLine();
              queue.add(car);
          }
          for(int i=0;i<N;i++){
              String search = br.readLine();
              if(queue.peek().equals(search)){
                  queue.poll();
              }
              else{
                  answer++;
                  queue.remove(search);
              }
          }
          System.out.println(answer);
      }
  }

  😇 해시맵 쓴 풀이

  import java.util.*;
  import java.io.*;
  public class BOJ2002 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
          int answer = 0;
          HashMap<String, Integer> map = new HashMap<>();
          int[] data = new int[N];
          for(int i=0;i<N;i++){
              String car = br.readLine();
              map.put(car,i);
          }
          for(int i=0;i<N;i++){
              String search = br.readLine();
              data[i] = map.get(search);
          }
          for(int i=0;i<N-1;i++){
              for(int j=i+1;j<N;j++){
                  if(data[i]>data[j]){
                      answer+=1;
                      break;
                  }
              }
          }
          System.out.println(answer);
      }
  }