[백준 3078번] 좋은 친구 - java

문제 설명

1. 전체 사람 수 N, 친구간 거리 K가 주어진다.

2. 사람들 이름이 순서대로 주어진다.

3. 이름의 길이가 같고 거리가 K 사이인 쌍을 모두 구해서 숫자를 구하면 된다.

풀이 과정

1. 슬라이딩 윈도우

2. 백준은 다 좋은데 난이도가 애매할때가 있다. 이거는 골드4라고 하기에는 좀 쉬운 느낌

3. 서로 친구라는거는 어차피 위로보나 아래로보나 기준이 같다.

4. 그래서 그냥 위에서 아래로만 확인하면 쌍을 다 구하는 것과 같다.

5. 위에서부터 아래로 K만큼 슬라이딩 윈도우 하고, 그 숫자는 HashMap으로 하면 된다.

코드

import java.util.*;

public class Main{
    public static void main(String[] args) {
        // 30000 개의 입력. int 범위를 벗어날 수 있다.
        long ans = 0;
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] users = new int[N]; // 친구 이름이 뭔지는 안중요하고 이름의 길이가 중요함

        for(int i=0; i<N; i++) {
            users[i] = sc.next().length(); // 사람들의 이름을 저장한다.
        }

        // 현재 위치 사람의 친구들의 이름 갯수를 저장하는 HashMap
        HashMap<Integer, Integer> lengthCnt = new HashMap<>();

        for(int i=0; i<K+1; i++) {
            // 0번 녀석 본인을 포함하고 그 K번 아래까지 친구들을 이름 갯수 저장
            lengthCnt.put(users[i], lengthCnt.getOrDefault(users[i], 0) + 1);
        }

        for(int i=0; i<N; i++) {
            int nowLength = users[i]; // 현재 녀석 봐서
            lengthCnt.put(nowLength, lengthCnt.get(nowLength) - 1); // 그녀석의 이름은 고려하지 않고
            int near = lengthCnt.get(nowLength); // 나머지 친구들의 이름 갯수 중 현재 친구와 같은 갯수를 구하면
            ans += near; // 가장 친한 친구가 된다.
            if(i+K+1 < N) { // 그리고 아래로 가면서 다음 사람의 K만큼 거리의 친구를 추가하면 된다.
                int nextWindow = users[i+K+1];
                lengthCnt.put(nextWindow, lengthCnt.getOrDefault(nextWindow, 0) + 1);
            }
        }

        System.out.println(ans);
    }
}