BOJ_좋은친구_3078

1. 과정

- 처음엔 이중 for문으로 하려고 했다. 하지만 아래 방식처럼 하면 N과 K가 최악의 경우 각각 30만이기 때문에 시간초과가 난다.

for(int i=0; i<N-K; ++i){
    for(int j=i+1; j<i+K; ++j){
    	// 코드구현
    }
}

- 그래서 라인스위핑을 사용했다.

- 먼저 최소 길이가 2, 최대 길이가 20이므로 Queue타입의 배열을 만든다. 예를들어 q[4]라면 문자열 길이가 4인 학생의 등수를 q에다 저장하는것이다.

- 그리고 중요한것은 문자열 길이기 때문에 길이로만 저장한다.

- q가 비어있다면 그냥 넣고, 아니라면 가장 앞의 등수를 확인하고, 현재 학생의 등수의 차가 K이하라면 q사이즈만큼 쌍이 만들어지므로 answer에 더한다.

- 만약 q의 가장 앞에 있는 등수와의 차가 K보다 크다면 K이하가 나올때 까지 빼낸다.

- 하지만 q에 있던 모든 학생과의 등수 차가 K보다 크다면 q에 현재 학생의 등수만 넣어준다.

 

 

2. 구현

언어 : JAVA

메모리 : 51,476 kb

시간 : 296 ms

import java.io.*;
import java.util.*;

public class BOJ_좋은친구_3078 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		long answer = 0;
		int N = Integer.parseInt(s[0]);
		int K = Integer.parseInt(s[1]);
		// 최소 길이가 2, 최대 길이가 20이므로 Queue타입의 배열을 만든다.
		Queue<Integer>[] q = new LinkedList[21];
		for (int i = 2; i < 21; ++i)
			q[i] = new LinkedList<>();

		for (int i = 1; i <= N; ++i) {
			int len = br.readLine().length();
			// q가 비어있다면 그냥 넣음
			if (q[len].isEmpty()) {
				q[len].add(i);
			}
			else {
				while (!q[len].isEmpty()) {
					// 아니라면 가장 앞의 등수를 확인하고, 현재 학생의 등수의 차가 K이하라면 q사이즈만큼 쌍이 만들어지므로 answer에 더한다.
					// 그리고 q에 넣고 빠져나온다
					if (i - q[len].peek() <= K) {
						answer += q[len].size();
						q[len].add(i);
						break;
					}
					// 만약 q의 가장 앞에 있는 등수와의 차가 K보다 크다면 빼낸다.
					q[len].poll();
				}
				// q가 비었다면 q에 있었던 모든 학생의 차가 K보다 컸기 때문에 그냥 현재 학생의 등수만 넣어준다.
				if(q[len].isEmpty())
					q[len].add(i);
			}
		}
		System.out.println(answer);
	}

}