[java] 3078 좋은 친구

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

슬라이딩 윈도우 기법과 해시맵을 사용한다.
해시맵 = (이름길이수, 몇명)
해당 예시로 함께 설명 - 백준 예시 1)

---

1. int[] 배열에 1번부터 N번까지 친구들 이름의 '길이'로 생성

---

2. 1등친구 ~ K번째 친구까지 자릿수를 키로 hashmap 에 값을 삽입

예시 ) 1등일 때 (hashmap 이하 hm 이라 표현)
hm = (7,1) == 이름길이 7인 사람, 1명

2등일 때
hm == (5,1) , (7,1) == 이름길이 5인사람 1명, 이름 길이 7인 사람 1명

3등일 때
hm == (5,1) , (6,1) , (7,1) == 이름길이 5인사람 1명, 6인 사람 1명, 7인 사람 1명

4등일 때 ( K가 3이므로 , 1등의 좋은 친구는 4등까지의 경우의 수임)
hm == (5,2) , (6,1) , (7,1) == 이름길이 5인사람 2명, 6인 사람 1명, 7인 사람 1명

이 과정을 코드로 표현

		for (int i = 0; i <= K; i++) {
			if (hm.containsKey(list[i])) { //이미 있으면 값 +1
				hm.put(list[i], hm.get(list[i]) + 1);
			} else { //없으면 1로 생성
				hm.put(list[i], 1);
			}
		}

3. 1등 친구~K번째 친구와 똑같은 이름길이가 몇 명인 지 확인

예시로 이해) 아래 4명을 비교하는 것으로, 우리는 이미 구해놓은 HM 에서 7의 값 - 1이 1등친구와 똑같은 이름길이를 가진 친구수이다. 그러므로 1등친구의 좋은 친구는 없음.

▼ 1번 친구의 경우

▼ 코드

if (hm.get(list[1]) > 1) {
                friends += hm.get(list[l]) - 1;
            }

4. 그럼 다음 2등 친구 ~ K+1번째 친구 해쉬맵에 값을 넣어가며 구하면 하는데,
   이 문제는 범위가 크므로 슬라이딩 윈도우 기법을 사용한다.

예시로 이해)
1번 친구 : 1,2,3,4 비교
2번 친구 : 2,3,4,5 비교 이므로
1번 친구에서 -> 현재 1번 값을 빼주고, 5번값을 더해주면 된다.

▼ 2번 친구의 경우

빼주고 코드

• 현재 1번값을 빼야하니 idx=0
  그다음 뺄 값은 2이므로 idx += 1

	private static void remove(int idx) {
		hm.put(list[idx], hm.get(list[idx]) - 1);
	}

더해주고 코드

• 현재 5번값을 구해야하니, idx = K+1
  그다음 뺄 값은 3이므로 idx += 1

	private static void add(int idx) {
		if (hm.containsKey(list[idx])) {
			hm.put(list[idx], hm.get(list[idx]) + 1);
		} else {
			hm.put(list[idx], 1);
		}
	}

5. 이를 반복한 후 3번에서 구한 friends 가 최종 정답이 된다.

3. 전체 코드

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

public class Main {

	static int N, K;
	static long friends = 0;
	static int[] list;
	static char[] temp;
	static HashMap<Integer, Integer> hm = new HashMap<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		list = new int[N];

		for (int i = 0; i < N; i++) {
			temp = br.readLine().toCharArray();
			list[i] = temp.length;
		}

		for (int i = 0; i <= K; i++) {
			if (hm.containsKey(list[i])) {
				hm.put(list[i], hm.get(list[i]) + 1);
			} else {
				hm.put(list[i], 1);
			}
		}

		int l = 0, r = K + 1;

		while (l < N) {
			if (hm.get(list[l]) > 1) {
                friends += hm.get(list[l]) - 1;
            }
			if (r < N) {
				add(r++);
			}
			remove(l++);
		}

		System.out.println(friends);
	}

	private static void add(int idx) {
		if (hm.containsKey(list[idx])) {
			hm.put(list[idx], hm.get(list[idx]) + 1);
		} else {
			hm.put(list[idx], 1);
		}
	}

	private static void remove(int idx) {
		hm.put(list[idx], hm.get(list[idx]) - 1);
	}

}

코드 참고 : blog.naver.com/kerochuu
내 방식대로 코드를 변경하며 작성했는데,
블로그 작성하면서 내 코드를 갖다 쓰다보니 어렵고
위 블로그 분의 코드가 설명하기 가장 쉬웠다 ... 역시 오늘도 이렇게 배운다!!👍👍👍