3077 - 임진왜란

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

주어진 사건들의 이름에 대응되는 인덱스들만 저장해서 나중에 $O(N^{2})$ 만큼 돌면서 크기가 $i$번째 이후 중에서 $i$번째보다 큰 인덱스만 세려고 했다.

자료구조 map을 써서 각 사건들의 인덱스를 저장한 후, 사건이 입력될 때마다 j=i+1~N 의 반복문에서 index[ 사건[i] ] < index[ 사건[j] ] 를 썼더니 map에서 조회 연산이 $O(NlogN)$ 이라 그런지 시간초과를 먹었다. (당시에는 map에서 조회하는 연산을 생각하지 못해서 30분 정도 삽질한듯.. 생각나는 대로 코딩하는 자의 최후)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int i, j, n;
    char s[16];
    scanf("%d ", &n);
    map<string, int> index;
    for(i=0; i<n; ++i){
        scanf("%s ", s);
        index[s] = i;
    }
    int a[2501];
    for(i=0; i<n; ++i){
        scanf("%s ", s);
        a[i] = index[s];
    }
    int r = 0;
    for(i=0; i<n; ++i){
        for(j=i+1; j<n; ++j) r += a[i] < a[j];
    }
    printf("%d/%d", r, n*(n-1)/2);
    return 0;
}