BAEKJOON / 백준 - JAVA 1058번 친구

2024.07.23기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 자신의 친구의 수와 (친구와 친구의 수)를 더 해 가장 2-친구가 많은 사람을 찾는 문제입니다.

 

저의 접근은 친구들을 저장할 때, 중복을 제거하기 위해 Set으로 접근을 먼저 했습니다.

 

1. 자신의 번호와 친구, 친구의 친구를 저장하는 커스텀 class를 생성했습니다.

// 친구들을 저장하는 클래스
public static class Friend {
    int number;
    Set<Integer> one, two;

    public Friend(int n, List<Integer> o) {
        number = n;

        one = new LinkedHashSet<>(); // 친구
        two = new LinkedHashSet<>(); // 2-친구

        for (int i = 0; i < o.size(); i++) {
            one.add(o.get(i));
        }
    }
}

 

2. 우선적으로 자신의 친구 목록을 먼저 저장했습니다.

(저장을 하면서, two리스트도 초기화를 해줍니다.)

for (int i = 0; i < n; i++) {
    arr = br.readLine().toCharArray();

    friend = new LinkedList<>();
    for (int j = 0; j < arr.length; j++) {
        if (arr[j] == 'Y') { // 친구이면 friend에 저장
            friend.add(j);
        }
    }

    // 저장된 friend 리스트로 Friend 클래스 생성 후 저장
    list.add(new Friend(i, friend));
}

 

3. 저장된 리스트를 통해 친구의 친구(two list)를 저장해주는 함수를 생성했습니다.

// 2-친구를 구하는 함수.
private static int twoFriend(int index) {
    for (int n1 : list.get(index).one) {
        for (int n2 : list.get(n1).one) {
            if (n2 != index) {
                // 자신의 친구의 친구인 2-친구를 본인을 제외하고 저장
                list.get(index).two.add(n2);
            }
        }
    }

    // 저장된 친구 목록을 중복 없이 저장하기 위해 set에 저장.
    Set<Integer> sum = new LinkedHashSet<>();
    for (int o : list.get(index).one) {
        sum.add(o);
    }

    for (int t : list.get(index).two) {
        sum.add(t);
    }

    // set의 사이즈가 총 2-친구의 수가 된다.
    return sum.size();
}

 

4. two를 채우는 것과 동시에 새로운 sum이라는 set을 만들어 자신의 친구와 친구의 친구를 저장해 중복을 제거를 시켜주었습니다.

// 저장된 친구 목록을 중복 없이 저장하기 위해 set에 저장.
Set<Integer> sum = new LinkedHashSet<>();
for (int o : list.get(index).one) {
    sum.add(o);
}

for (int t : list.get(index).two) {
    sum.add(t);
}

// set의 사이즈가 총 2-친구의 수가 된다.
return sum.size();

이렇게 참조한 인원의  2-친구의 수를 구하여 Main클래스에서 최대값을 정리해 출력을 해주었습니다.

 

 

코드

package Main;

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

public class Main {
	
	// 친구들을 저장하는 클래스
	public static class Friend {
		int number;
		Set<Integer> one, two;
		
		public Friend(int n, List<Integer> o) {
			number = n;
			
			one = new LinkedHashSet<>(); // 친구
			two = new LinkedHashSet<>(); // 2-친구
			
			for (int i = 0; i < o.size(); i++) {
				one.add(o.get(i));
			}
		}
	}
	
	static int n;
	static List<Friend> list;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine()); // 사람의 수
		
		char[] arr;
		List<Integer> friend;
		list = new LinkedList<>();
		
		for (int i = 0; i < n; i++) {
			arr = br.readLine().toCharArray();
			
			friend = new LinkedList<>();
			for (int j = 0; j < arr.length; j++) {
				if (arr[j] == 'Y') { // 친구이면 friend에 저장
					friend.add(j);
				}
			}
			
			// 저장된 friend 리스트로 Friend 클래스 생성 후 저장
			list.add(new Friend(i, friend));
		}
		
		int count = 0;
		for (int i = 0; i < n; i++) {
			count = Math.max(count, twoFriend(i));
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 2-친구를 구하는 함수.
	private static int twoFriend(int index) {
		for (int n1 : list.get(index).one) {
			for (int n2 : list.get(n1).one) {
				if (n2 != index) {
					// 자신의 친구의 친구인 2-친구를 본인을 제외하고 저장
					list.get(index).two.add(n2);
				}
			}
		}
		
		// 저장된 친구 목록을 중복 없이 저장하기 위해 set에 저장.
		Set<Integer> sum = new LinkedHashSet<>();
		for (int o : list.get(index).one) {
			sum.add(o);
		}
		
		for (int t : list.get(index).two) {
			sum.add(t);
		}
		
		// set의 사이즈가 총 2-친구의 수가 된다.
		return sum.size();
	}
}