백준 3078번: 좋은 친구 [슬라이딩 윈도우][투 포인터] -Java

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

3078번: 좋은 친구

 

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

 

 

O(N*K)는 시간초과가 발생하기에  투포인터 할 때 공부했던 Sliding Window 알고리즘을 이용했다. O(N)

다 풀고나니 Queue를 이용한 방법도 있었다. 방식은 내나 동일하다.

구간의 정보를 재 사용하는 것!

 

0~N까지 각각 이름의 lenght를 cnt배열에 카운팅하고,

K범위내에서 이름의 lenght가 동일한게 있다면 갯수만큼 ans에 더해준다.

 

 

** 챙겨야 할 부분..

N의 최대가 300,000이기에.. 쌍의 개수가 int형 범위를 넘어갈 수 있다.

long 타입으로 받아주어야한다.

 

<Java 코드>

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		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());
		
		long ans = 0;
		
		String[] friend= new String[N+1];
		Arrays.fill(friend, "");
		int[] cnt = new int[21]; //글자수 2~20글자
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			friend[i] = st.nextToken();
		}
		
		//0~K만큼 최초 수동으로 구하기
		for (int i = 0; i <= K; i++) {
			if(cnt[friend[i].length()]>0) //동일한 길이의 숫자가 있는가?
				ans+= cnt[friend[i].length()]; //K범위내에 동일한 숫자 개수 만큼 ans++ ;
			cnt[friend[i].length()]++;
		}
		
        //이후부터는 범위 활용하여 한개씩만 활용하기
		for (int i = K+1; i < N; i++) {
			cnt[friend[i-(K+1)].length()]--; //바로 직전 범위 지우기 (K범위만큼만 봐야하므로)
			if(cnt[friend[i].length()]>0)
				ans+= cnt[friend[i].length()];
			cnt[friend[i].length()]++;
		}
		
		System.out.println(ans);
		
	}

}