[백준] 3078번 : 좋은 친구 - 자바(JAVA)

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

3078번: 좋은 친구

 

문제 해석

모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니다.

이때 좋은 친구는 이름의 길이가 같아야 합니다.

N명의 학생들의 이름이 성적순으로 주어졌을 때 좋은 친구가 몇 쌍이나 있는지 구하세요

 

좋은 친구 = 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같음

 

문제 풀이 전 설계

우선 N은 최대 30만입니다.

 

좋은 친구의 문서 쌍을 구해야 합니다.

투 포인터를 통해 K범위 안에 속하면서 이름의 길이가 같은 친구들을 모두 구해냅니다.

 

그렇게 되면 O(N)만에 각자의 학생들은 자신을 기준으로 오른쪽으로 K만큼 좋은 친구의 개수를 N개 가지게 됩니다.

 

근데 이때 주의해야 할 점은 N번만큼 좋은 친구를 검사하기 위해서는 오른쪽의 K개의 친구가 자신과 같은 길이를 가지는지 매번 검사해야 합니다.

 

그것을 막기 위해서는 Map을 선언하여 (Key, Value)를  (이름의 길이 Integer, 개수 Integer)로 관리하고자 합니다.

 

 

예시

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

K=3

 

CYNTHIA : LLOYD, STEVIE, KEVIN 검사 여기서 자기와 같은 길이를 세어줍니다. (없음)

Map에 해당값들을 넣어줍니다. (Key = 이름의 길이, Value = 개수)

LLOYD , KEVIN= 5자

STEVIE = 6자

 

결과 Map (5,2), (6,1)

 

이후 LLOYD를 검사합니다.

그러면서 자기자신(5자)은 맵에서 제외하고 MALCOLM(7자)에 대한 정보는 MAP에 넣어줍니다.

그러면 결과 Map (5,1), (6,1), (7,1)이 됩니다.

여기서 LLOYD는 5자이기 때문에 좋은 친구가 1개 생깁니다.

 

이후에 STEVIE를 검사합니다.

자기 자신(6자)은 맵에서 제외하고 DABNEY(6자)에 대한 정보는 MAP에 넣어줍니다.

그러면 결과 Map (5,1) , (6,1), (7,1)이 됩니다.

여기서 STEVIE는 6자이기 때문에 좋은 친구가 1개 생깁니다.

 

즉, 좋은 친구 쌍은 2개

 

주의할 점은 이때 결과가 overflow가 발생할 수 있어 int대신에 long타입을 사용해야 합니다.

 

코드

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_3078_좋은친구 {
    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());

        String[] friends = new String[N];
        for (int i = 0; i < N; i++) {
            friends[i] = br.readLine();
        }
        //현재 학생을 기준으로 K범위안에 존재하는 Key = 이름의 길이, Value = 학생들의 수
        Map<Integer, Integer> currentFiendsState = new HashMap<>();

        //초기 세팅을 0~K까지 Map에 넣어둠
        for (int i = 0; i < K; i++) {
            int length = friends[i].length();
            Integer curStudentCount = currentFiendsState.getOrDefault(length, 0);
            currentFiendsState.put(length, curStudentCount + 1);
        }

        int right = K;
        long result = 0;
        boolean finishFlag = false;

        for (int i = 0; i < N; i++) {
            //자기자신은 현재상태에서 제외
            int curLength = friends[i].length();
            int curCount = currentFiendsState.getOrDefault(curLength, 0);
            curCount = curCount == 0 ? 1 : curCount;
            currentFiendsState.put(curLength, curCount - 1);


            //K번째 친구를 넣어줌
            if (!finishFlag) {
                int kLength = friends[right++].length();
                Integer kStudentCount = currentFiendsState.getOrDefault(kLength, 0);
                currentFiendsState.put(kLength, kStudentCount + 1);
            }


            //이러면 현재 맵에는 자기자신~ K번째 수에 대한 이름에 길이에 해당하는 학생들의 수를 관리하고 있음
            result += currentFiendsState.get(curLength);

            if (right == N) {
                finishFlag = true;
            }

        }
        System.out.println(result);

    }
}