[BOJ] 백준 3078번 좋은 친구 (Java)

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

소요 시간: 16분
메모리: 39280KB
시간: 236ms

---

🔥 문제

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오.

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

 

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N)

다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

 

출력

첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.

---

🍀 풀이

등수 순서대로 K명의 학생들의 이름을 카운트해서 배열에 저장하는 방식으로, 슬라이딩 윈도우를 활용해서 문제를 풀었다.

 

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

 

위와 같은 입력이 주어졌다면, 등수 순서대로 아래와 같은 학생 이름 길이의 배열을 만들 수 있다.

 

1등 학생과 등수 차이가 K이하인 학생들의 이름 길이를 `name_len_count`배열에 카운트한다.

그리고 `name_len_count[7]`이 1등 학생을 포함하여 1등 학생과 이름 길이가 같은 학생의 수가 된다.

1등 학생과 좋은 친구 관계인 학생 수는 `name_len_count[7]-1`인 0명이 된다.

 

2등 학생과 좋은 관계인 학생 수를 찾기 위해 1등 학생의 이름 길이를 `name_len_count`배열에서 1 뺀다.

2등 학생과 등수 차이가 K이하인, 2등 이후 등수인 학생들의 이름 길이를 `name_len_count`배열에 카운트해야 한다.

2등 이전 등수는 이미 해당 등수에서 2등과 관계를 체크했으므로 2등 이후 등수인 학생들만 확인을 하면 된다.

이미 2등부터 4등(2+K-1등)까지 학생 이름 길이는 카운트가 되어 있으니, 범위의 끝 등수 학생인 5등 학생의 이름 길이만 `name_len_count`배열에 카운트하면 된다.

2등 학생과 좋은 친구 관계인 학생 수는 `name_len_count[5]-1`인 1명이 된다.

3등 학생과 좋은 관계인 학생 수를 찾기 위해 2등 학생의 이름 길이를 `name_len_count`배열에서 1 빼고, 범위의 끝 등수 학생인 6등 학생의 이름 길이를 카운트한다.

3등 학생과 좋은 친구 관계인 학생 수는 `name_len_count[6]-1`인 1명이 된다.

4등 학생과 좋은 관계인 학생 수를 찾기 위해 3등 학생의 이름 길이를 `name_len_count`배열에서 1 뺀다.

전체 학생 수는 6명으로 범위의 끝 등수 학생인 7등 학생이 없으므로 카운트하지 않는다.

3등 학생과 좋은 친구 관계인 학생 수는 `name_len_count[5]-1`인 0명이 된다.

이러한 방식으로 6등 학생까지 좋은 친구 관계를 확인하면 좋은 친구는 총 2쌍이 나온다.

 

1. 등수 순으로 학생의 이름 길이를 입력받는다. 이때 1등부터 K+1등 학생의 이름 길이를 `name_len_count` 배열에 카운트한다.
2. 좋은 친구가 몇쌍인지 저장하는 `pair`에 1등 학생과 좋은 친구 관계인 학생 수를 저장한다.
3. 이후 2등 학생부터 순차적으로 접근하며 좋은 친구 관계인 학생 수를 저장한다.
        1. i + K등 학생이 있는 경우 해당 학생의 이름 길이를 `name_len_count` 배열에 카운트한다.
        2. `pair`에 i등 학생과 이후 등수 중 좋은 친구 관계인 학생 수를 저장한다.
4. `pair`를 출력한다.

---

💻 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int N = Integer.parseInt(input.substring(0, input.indexOf(' ')));
        int K = Integer.parseInt(input.substring(input.indexOf(' ') + 1));

        int[] name_len = new int[N];
        int[] name_len_count = new int[21];

        for (int i = 0; i < N; i++) {
            name_len[i] = br.readLine().length();
            if (i <= K) {
                name_len_count[name_len[i]]++;
            }
        }
        long pair = --name_len_count[name_len[0]];

        for (int i = 1; i < N; i++) {
            if (i + K < N) name_len_count[name_len[i + K]]++;
            pair += --name_len_count[name_len[i]];
        }

        System.out.print(pair);
    }
}

---

💫 리뷰

풀이가 바로 생각나서 빠르게 풀 수 있었다.😀

좋은 학생 관계 수는 int형 범위를 벗어날 수 있어서 long형으로 선언해야 한다.

코테에서도 이런거 잘 계산해서 풀자!