[백준BOJ] 3078번 좋은 친구.java

 

백준 저지에서 좋은 친구를 자바를 통해 풀어 보았다. 

 

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

3078번: 좋은 친구

 

3078번 좋은 친구.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

3078번 좋은 친구

문제

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

설명

문제 해결만 생각한다면 이중포문으로 답을 도출할 수 있다. 단 N의 크기가 최대 300000이기 때문에 시간 초과에 걸린다. 한 번의 포문으로 문제를 해결해야한다.

 

좋은 친구가 되기위해선 이름의 길이가 같아야하기 때문에 이름 길이순과 등수순으로 정렬했다. 이름 길이순으로 우선 정렬하여 이름 길이가 다른 친구들에 대해서는 비교하지 않도록 말이다.

 

A와 B가 좋은 친구고 B와 C가 좋은 친구라면 B와 C는 무조건 좋은 친구이다. 이 특징을 통해 반복문을 한 번만 쓰고 문제를 해결한다. 

 

1. 큐를 생성한다.
2. 큐가 비어있다면 친구를 삽입한다.
3. 큐의 peek(A)과 다음 친구(B)가 좋은 친구라면 B를 큐에 삽입한다.
4. 다음 친구(C)도 큐의 peek(A)와 좋은 친구라면 큐에 삽입한다.
5. 이 때 B와 C 또한 좋은 친구이다. 이를 일반화하여 큐의 길이-1만큼 좋은 친구 쌍이 존재한다는 것을 알 수 있다.
6. 만약 좋은 친구사이가 아니라면 poll을 한다. 이때 새로운 큐의 peek과 현재 친구를 비교하기 위해 반복문의 index를 1 빼준다.
7. 2~6을 반복한다. 

코드

//3078번 좋은 친구.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 좋은_친구_3078 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		friend[] friends = new friend[N];
		
		for(int i=0;i<N;i++) {
			friends[i] = new friend(i, br.readLine().length());
		}
		
		long answer = 0;
		
		Arrays.sort(friends);
		
		Queue<friend> q = new LinkedList<friend>();
		
		//System.out.println(Arrays.toString(friends));
		for(int i=0;i<N;i++) {
			if(q.isEmpty()) {
				q.add(friends[i]);
			}else if(q.peek().name==friends[i].name && friends[i].rank-q.peek().rank <= K) {
				answer += q.size();
				q.add(friends[i]);
			}
			else {
				q.poll();
				i--;
			}
			
		}
		System.out.println(answer);
	}
    
    static class friend implements Comparable<friend>{
    	int rank;
    	int name;
    	
    	friend(int rank, int name) {
			this.rank = rank;
			this.name = name;
		}

		@Override
		public int compareTo(friend o) {
			if(Integer.compare(this.name, o.name)==0) {
				return Integer.compare(this.rank, o.rank);
			}
			return Integer.compare(this.name, o.name);
		}

		@Override
		public String toString() {
			return "friend [rank=" + rank + ", name=" + name + "]";
		}
    	
		
    }
}