[백준][BOJ-3078][자바] 좋은 친구

www.acmicpc.net/problem/3078

3078번: 좋은 친구

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		HashMap<Integer, List<Integer>> hm = new HashMap<>();
		long result =0;
		
		for(int i=0; i<N; i++) {
			int length = br.readLine().length();
			
			if(hm.containsKey(length)) {
				List<Integer> list = hm.get(length);
				for(int j=0; j<list.size(); j++) {
					if(i-list.get(j) <=K) {
						result += list.size();
						break;
					}
					else {
						list.remove(j--);
					}
				}
			}else {
				hm.put(length, new ArrayList<>());
			}
			hm.get(length).add(i);
		}
		
		System.out.println(result);
	}
}

정리

• N이 최대 300,000이고 K도 최대 N까지 가질 수 있기 때문에 N만큼 돌리면서 K의 개수만큼 검사한다면 시간 초과가 난다. 
• 문자열의 길이를 Key로 가지고 성적을 저장(배열)하는 Value를 가진 HashMap을 선언해준다.
• 문자열 길이가 존재 한다면 Value를 꺼내서 현재 i와 차이가 K 이하만큼 나는 것이 있다면 그 뒷부분은 검사할 필요 없이 list.size() 만큼이 한 쌍이다.
• 하지만 K 초과라면 i 이상의 문자열과 비교를 해도 항상 값이 K 초과가 되어 버리기 때문에 list에서 삭제를 시켜주면서 항상 최소한의 K 이하의 값을 가지도록 list를 관리한다.