Baekjoon 3078
in Study / Computer science on Baekjoon 3078
Queue, Sliding Window
Watch Out
- We need to use “long” type for the result
Description
상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.
상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
상근: 근데?
??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
상근: 아? 근데 K는 어떻게 구해?
??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와. 상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!
상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.
Input
첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다.
이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.
Output
첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.
Example I & O
Input
4 2
IVA
IVO
ANA
TOM
Output
5
Input
6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY
Output
2
My solution
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
import java.io.*;
import java.util.StringTokenizer;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] NK = br.readLine().split(" ");
int n = Integer.parseInt(NK[0]);
int k = Integer.parseInt(NK[1]);
int[] slide_arr = new int[n];
for (int i = 0; i < n; i++) {
String name = br.readLine();
slide_arr[i] = name.length();
}
long[] length_arr = new long[21];
Queue<Long> q = new LinkedList<Long>();
int q_max_size = k + 1;
long[] duplicated = new long[q_max_size];
int temp_index = 0;
for (int i = 0; i < q_max_size; i++) {
if (i >= slide_arr.length)
break;
q.add((long) slide_arr[i]);
if (length_arr[slide_arr[i]] == 1) {
duplicated[temp_index] = slide_arr[i];
temp_index += 1;
}
length_arr[slide_arr[i]] += 1;
}
long res = 0;
for (int i = 0; i < duplicated.length; i++) {
res += (length_arr[(int) duplicated[i]] * (length_arr[(int) duplicated[i]] - 1)) / 2;
}
for (int i = q_max_size; i < slide_arr.length; i++) {
long removed = q.poll();
long newone = slide_arr[i];
length_arr[(int) removed] -= 1;
res += length_arr[(int) newone];
length_arr[(int) newone] += 1;
q.add(newone);
}
bw.write(res + "");
bw.flush();
bw.close();
}
}
- Sketch
- Use sliding window implemented by queue
Strings: CYNTHIA LLOYD STEVIE KEVIN MALCOLM DABNEY
slide_arr: [7, 5, 6, 5, 7, 6] (string length)
k = 4: window's size == 4
* length_arr
length_arr[i] means the number of elements
having i as value in slide_arr at the current window's location
* At the first window's location, we need to calculate the number of possible cases
= 1 + 2 + ... (i - 1) = i(i-1)/2
* Since calculating the first window's location,
we just move the window with removing the first element of window (reflecting on length_arr[i]: length_arr[i] -= 1)
and adding the new element (reflecting on length_arr[i]: length_arr[i] += 1)
At that point, the number of the possible cases is accumulated by the new element
(res += length_arr[i] except the new element)