[ 백준 ] 좋은 친구

문제

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

• 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
• ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
• 상근: 근데?
• ??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
• 상근: 아? 근데 K는 어떻게 구해?
• ??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
• 상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

 

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

 

출력

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

 

문제 해석

 

n 명의 학생 이름이 성적준으로 정렬되어서 주어진다

어떤 두 학생이 좋은 친구인지 아닌지 판단해서 총 쌍의 수를 구하는 문제이다.

 

좋은 친구의 조건은 두가지이다.

1. 등수 차이가 k 보다 작거나 같아야한다 ( 두 학생의 index 차이가 k 이하여야한다 )

2. 이름의 길이가 같아야한다.

 

성적 순서로 정렬된 학생 리스트에서 인접한 학생들 끼리만 등수 차이를 고려하면된다.

그래서 큐를 사용해서 문제를 해결했다.

 

이미 정렬되어있고 길이별로 좋은 친구를 찾으려고한다.

등수 차이가 k 보다 큰 학생은 큐에서 제거하고 현재 학생과 큐안에 남아있는 학생들과의 쌍의 수를 카운트하면 결과가 나온다.

 

알고리즘 흐름 

이름 길이를 key로 하는 Map<이름 길이 , 큐> 를 생성한다.

각 큐는 해당 이름 길이를 가진 학생들의 등수(인덱스) 를 보관

 

현재 학생의 이름 길이를 기준으로 큐를 하나 꺼낸다.

 

등수 차이가 k 초과인 학생들은 큐에서 제거한다.

 

큐에 남아있는 학생 수는 현재 학생과 좋은 친구가 될 수 있는 사람의 수 이다.

 

이 수를 result 변수에 저장하고 현재 학생의 인덱스를 큐에 추가하면된다.

 

입력 예시 2를 기준으로 풀이하면 이런 식이다.

 

i = 0 CYNTHIA (7글자)

해당 길이를 가진 학생이 존재하지않음으로 큐 생성

큐 상태 [0]

result += 0

 

i = 1 LLOYD (5글자)

해당 길이를 가진 학생이 존재하지않음으로 큐 생성

큐 상태 [1]

result += 0

 

i = 2 STEVIE (6글자)

해당 길이를 가진 학생이 존재하지않음으로 큐 생성

큐 상태 [2]

result += 0

 

i = 3 KEVIN(5글자)

해당 길이를 가진 학생이 존재함으로 기존의 큐 사용 생성 X

기존의 5글자 큐 : [1]

3(i) - 1(queue.peek()) = 2 <= 2 k 임으로 제거하지않고 유지

좋은 친구 한명 발견!

큐 상태 [1, 3]

result += 1

 

i = 4 MALCOLM (7글자)

해당 길이를 가진 학생이 존재함으로 기존의 큐 사용 생성 X

기존의 7글자 큐 : [0]

4(i) - 0(queue.peek()) = 4 > k 임으로 큐에서 제거 (queue.poll())

큐 상태 [4]

result += 0

 

i = 5 DABNEY (6글자)

해당 길이를 가진 학생이 존재함으로 기존의 큐 사용 생성 X

기존의 6글자 큐 : [2]

5(i) - 2 (queue.peek()) <= k  임으로 제거하지않고 유지

좋은 친구 발견!

큐 상태 [2,5]

result += 1

 

최종적으로 모든 쌍을 확인해보면 2쌍이 나오게 된다

LLOYD- KEVIN 

STEVIE-DABNEY

reuslt : 2

 

 

코드

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());

        // N: 학생 수, K: 등수 차이 제한
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 이름 길이별로 큐를 관리하기 위한 Map (key: 이름 길이, value: 해당 길이의 등수들)
        Map<Integer, Queue<Integer>> map = new HashMap<>();

        // 결과: 좋은 친구 쌍의 수
        long result = 0;

        // 순차적으로 학생 이름을 입력받음 (성적순)
        for (int i = 0; i < N; i++) {
            String name = br.readLine();
            int len = name.length(); // 이름 길이

            // 이름 길이에 해당하는 큐가 없으면 생성
            map.putIfAbsent(len, new LinkedList<>());

            Queue<Integer> queue = map.get(len);

            // 현재 학생과의 등수 차이가 K 초과인 학생은 큐에서 제거
            while (!queue.isEmpty() && i - queue.peek() > K) {
                queue.poll();
            }

            // 현재 큐에 남아 있는 학생 수만큼 좋은 친구 쌍이 생김
            result += queue.size();

            // 현재 학생의 인덱스를 큐에 추가
            queue.offer(i);
        }

        // 정답 출력
        System.out.println(result);
    }
}