BOJ) 좋은 친구 (3078 번)

좋은 친구

3078번: 좋은 친구

 

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

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

또한, 이름의 길이는 2 ~ 20 사이이다.

 

풀이

 

먼저, 이름의 길이에 따라 학생을 저장할 배열 bestFriends와 Sliding Window를 도와줄 Queue를 초기화했다. 위의 배열에는 이름의 길이가 2 ~ 20까지인 학생들이 몇명인지 count한 정보를 가지고 있다.

Queue는 학생들의 순위를 파악하기 위한 보조 역할로, K등수 이상 차이가 나면 Queue에서 제거한다.

즉, Queue는 좋은 친구 후보를 담아두는 역할을 한다.

 

로직

 

배열을 돌면서, queue에 학생의 이름의 길이를 넣어준다.

queue의 가장 앞선 학생이, 현재 학생과 k등 넘게 차이가 나면 queue에서 제거해준다.

queue에서 제거하게 되면, 문제의 조건에 따라 좋은 친구가 아니기 때문에, 해당 학생의 이름 길이에 해당하는 배열의 count를 하나 제거해준다.

queue에 남은 학생들은 좋은 친구가 될 수 있는 조건을 가진다.

따라서, 배열에 이 학생들의 이름 길이에 맞게 count가 저장되어있다.

현재 포인터가 위치하는 학생의 이름 길이에 2명 이상 들어있는지 확인하여 답에 더해준다.

이때, -1을 해주는 이유는 2명 ~> 1쌍, 3명 ~> 2쌍 ... n명 ~> n-1쌍이 되기 때문

 

 

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BestFriends_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()), k = Integer.parseInt(st.nextToken());
        int[] students = new int[n];
        for(int i=0; i<n; i++) {
            students[i] = br.readLine().length();
        }

        br.close();
        solution(n,k,students);
    }

    private static void solution(int n, int k, int[] students) {
        final int MAX = 20, DUPLICATE_COUNT =1;
        int[] bestFriends = new int[MAX+1];
        Queue<int[]> queue = new LinkedList<>();
        long answer =0;

        for(int i=0; i<n; i++) {
            queue.offer(new int[] {i, students[i]});
            bestFriends[students[i]]++;
            if(!isInRange(i, queue.peek()[0], k)) {
                bestFriends[queue.poll()[1]]--;
            }
            answer += bestFriends[students[i]] - DUPLICATE_COUNT;
        }
        System.out.println(answer);
    }

    private static boolean isInRange(int now, int target, int k) {
        return now -k <= target && now + k >= target;
    }
}