[백준 Baekjoon] 3077번 임진왜란 - JAVA

백준 Baekjoon 3077번 임진왜란 - JAVA

---

문제 풀이

올바른 순서가 주어졌을 때, 작성한 답안을 2개씩 비교하여 순서가 올바르면 1점씩 증가한다. N이 5일 때
{0, 1}, {0, 2}, {0, 3}, {0, 4},
{1, 2}, {1, 3}, {1, 4},
{2, 3}, {2, 4}
{3, 4}
이렇게 두개씩 짝을 지어 올바른 순서의 순서와 같은지 비교하면 된다.

해전을 HashMap을 사용하여 문자열의 순서를 저장하여 쉽게 찾을 수 있도록 하면 된다.

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            map.put(st.nextToken(), i);
        }

        String[] input = br.readLine().split(" ");

        int cnt = 0;

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (map.get(input[i]) < map.get(input[j])) {
                    cnt++;
                }
            }
        }

        System.out.println(cnt + "/" + N * (N - 1) / 2);
    }
}