[코딩 테스트] 좋은 친구

문제 출처

 

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

 

문제 풀이 생각과 과정

• 한명씩 조사하면서, K 범위에있는 친구를 조사하는건 절대 안될 거라는 생각이 들었다.
• K가 N만큼 커지게 된다면 N^2 만큼 조사하게 되고,  (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 같은 범위에서는 무조건 시간초과가 나게 될 것이다.
• 어떻게 할까 고민하다가 결국에 생각해내지 못하고 힌트를 참고하였다....

 

 

예시를 보면서 설명하는게 편할 것 같아서 문제에서 보여준 2번째 예시를 사용해보도록 하겠다.

예제 입력 2

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

 

다음과 같은 예시에 먼저 배열을 두개를 생성해준다.

1. 첫 번째 배열은, 각 사람마다의 이름의 크기를 저장한다
2. 두 번째 배열은, 이름의 길이를 인덱스로한 배열이다
   
   • 최대 20자라고 하였으니 int[20+1]의 배열을 선언해주면 되겠다.

 

• K만큼 조사하면서 확인한다.

 

 

첫 번째 학생(1등 학생, 이름길이:7)의 count 수를 보고서 answer에 추가하면된다. 여기서 중요한 점은 자신을 제외하여야 하기 때문에

answer += nameLengthCount[ 7 ] - 1 이라는 점이다.

 

그래서 처음 학생과 좋은 친구 쌍은 없다.

 

다음 과정을 하기위해서 1등 친구(이름 길이 7)의 count를 빼주고, 4등 친구(이름 길이 5)의 count를 추가해준다.

 

 

 

이렇게 되면

answer + = nameLengthCount[5]  - 1

즉, answer+ = 2 - 1 

이 되게 된다. 두 번째 친구와의 좋은 친구 쌍이 하나 있다는 말이다.

 

이런식으로 쭉 진행하면 된다.

 

 

 

 

소스코드

 

import java.io.*;


public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        String[] input =br.readLine().split(" ");
        int N =Integer.parseInt(input[0]);
        int K =Integer.parseInt(input[1]);

        long answer=0;

        //이름 길이를 저장할 배열 생성(최대 20자니까 20+1으로 생성)
        int[] nameLengthCount = new int[21];

        int[] nameLength = new int[N];
        for(int i =0;i<N;i++){
            nameLength[i]=br.readLine().length();
        }

        for(int i=0;i<K;i++){
            nameLengthCount[nameLength[i]]++;
        }

        for(int i=0;i<N-1;i++){
            if((i+K)<=N-1) nameLengthCount[nameLength[i+K]]++;
            answer+=nameLengthCount[nameLength[i]]-1;
            nameLengthCount[nameLength[i]]--;
        }

        System.out.println(answer);

    }
}