백준_2002(투포인터, 큐)

 

입구에 들어간 순서와 출구에서 나온 순서가 뒤바뀐 차량들을 찾아내면 된다.

두가지 방법으로 풀 수 있는데 첫번째는 큐를 이용한 방법이고 두번째는 투포인터 알고리즘이다.

 

큐

package TT4_APR;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Boj_2002_queue {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N  = Integer.parseInt(br.readLine());
        Queue<String> queue = new LinkedList<>();
        for(int i=0;i<N;i++) queue.offer(br.readLine());

        int result=0;
        for(int i=0;i<N;i++){
            String input = br.readLine();
            if(input.equals(queue.peek())){
                queue.poll();
                result++;
            }
            else queue.remove(input);
        }
        System.out.println(N-result);
    }
}

입구로 들어간 차량은 큐에 넣는다.

출구로 나온 차량은 입력 그대로 큐랑 비교해서 순서를 비교한다.

 

투포인터

package TT4_APR;

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

public class Boj_2002 {
    static int N;
    static ArrayList<String> first = new ArrayList<>();
    static ArrayList<String> second = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        //TODO 투포인터
        for (int i = 0; i < N; i++) {
            first.add(br.readLine());
        }
        for (int i = 0; i < N; i++) {
            second.add(br.readLine());
        }
        twoPointers(first, second);
        System.out.println(N-result);
    }

    static int result = 0;

    private static void twoPointers(ArrayList<String> first, ArrayList<String> second) {
        int f = 0, s = 0;
        Map<String, Boolean> map = new HashMap<>();
        while (f < first.size() && s < second.size()) {
            while (map.getOrDefault(first.get(f), false)) {
                f++;
            }
            if (first.get(f).equals(second.get(s))) { //같으면 둘다 한칸 뒤로
                s++; f++;
                result++;
            } else { //같지 않으면 s만 뒤로 한
                map.put(second.get(s), true); s++;
            }
        }
    }
}

입구와 출구 모두 ArrayList에 저장하고 투포인터 알고리즘을 이용하여 비교한다.

 

 

입력이 크지 않아서 메모리나 시간상으로 큰 차이가 없지만 입력이 커지면 저런 방식의 투포인터는 효율적이지 않을듯 싶다.