BOJ 3078. 좋은 친구

최근 이래저래 일이 많아서 오랜만에 알고리즘을 풀었다..
꾸준히 풀어야하는데ㅠ_ㅠ
그리고 원래는 java로 ps 푸는데 요즘은 swift와 병행할까 생각중이다.

처음에는 Queue에 다 때려박고 순회 돌면서 계산하도록 풀었다.
근데 당연히 시간초괔ㅋㅋㅋ(범위 좀 미리 보는 습관을 들이자...)

내가 solve한 방법은 다음과 같다.

1. 입력되는 문자열의 내용은 상관없으므로 처음부터 문자열의 길이를 저장한다.
2. 문자열의 길이를 저장하는 lengthArr 배열과 lengthQ 큐와 map 해시맵을 사용한다.
   (lengthArr는 탐색 target이 될 배열, lengthQ는 target의 n의 범위를 벗어난 길이를 저장한 큐, map은 target의 n의 범위에 있는 문자열의 길이의 갯수를 저장한다.... 이름 좀 명시적으로 짓도록 노력해야지...)
3. 문자열을 입력받을때 lengthArr에는 무조건 다 넣고, n의 범위에 있는 것들은 map에 넣고 이후의 것들은 다 lengthQ에 넣는다.
4. lengthArr을 순회하며 친구의 쌍을 찾는다. lengthArr[index]가 우리가 찾아야하는 배열의 길이 target이라고 볼 수 있다.
5. index가 0일때와 아닐때를 구분해야하는데 0이라면 map에서 target이 있는지만 확인한다.
6. index가 0이 아니라면 우선 n의 범위를 이동해야한다. 그렇기에 map의 값들을 조정해준다.
   (정답이 long여야한다.... 다시 한 번 범위 체크 좀 잘하자...)

import java.io.*;
import java.util.*;

public class BOJ3078 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int[] lengthArr = new int[k];
        Queue<Integer> lengthQ = new LinkedList<>();

        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < k; i++) {
            lengthArr[i] = br.readLine().length();

            if (i == 0) {
                continue;
            }

            if(i <= n) {
                if(map.containsKey(lengthArr[i])) {
                    map.put(lengthArr[i], map.get(lengthArr[i]) + 1);
                }
                else {
                    map.put(lengthArr[i], 1);
                }
                continue;
            }

            lengthQ.offer(lengthArr[i]);
        }

        long answer = 0;
        for(int index = 0; index < k; index++) {
            if(index == 0) {
                if(map.containsKey(lengthArr[index])) {
                    answer += map.get(lengthArr[index]);
                }
                continue;
            }

            if(map.containsKey(lengthArr[index])) {
                if(map.get(lengthArr[index]) == 1) {
                    map.remove(lengthArr[index]);
                }
                else {
                    map.put(lengthArr[index], map.get(lengthArr[index]) - 1);
                }
            }
            if(!lengthQ.isEmpty()) {
                int next = lengthQ.poll();
                if(map.containsKey(next)) {
                    map.put(next, map.get(next) + 1);
                }
                else {
                    map.put(next, 1);
                }
            }

            if(map.containsKey(lengthArr[index])) {
                answer += map.get(lengthArr[index]);
            }
        }

        bw.write(answer + "");
        bw.flush();
        bw.close();
    }
}