토스 보증 문제
1 import java.util.*;
2
3 class Solution {
4
5 /**
6 * 대출 승인 여부를 판별하는 메인 함수
7 * @param relations 보증 관계 배열 [[보증받는자, 보증인], ...]
8 * @param initial_approvals 초기 승인자 배열
9 * @param applicants 대출 신청자 배열
10 * @return 각 신청자의 승인 여부를 담은 boolean 배열
11 */
12 public boolean[] solution(int[][] relations, int[] initial_approvals, int[] applicants) {
13 // 1. 자료구조 초기화
14 Map<Integer, Integer> guarantorMap = new HashMap<>();
15 for (int[] rel : relations) {
16 int guaranteed = rel[0];
17 int guarantor = rel[1];
18 guarantorMap.put(guaranteed, guarantor);
19 }
20
21 Set<Integer> approvalSet = new HashSet<>();
22 for (int approved : initial_approvals) {
23 approvalSet.add(approved);
24 }
25
26 // 3. 최적화를 위한 메모이제이션 캐시
27 Map<Integer, Boolean> memo = new HashMap<>();
28
29 // 2. 각 신청자에 대해 승인 여부 확인
30 boolean[] results = new boolean[applicants.length];
31 for (int i = 0; i < applicants.length; i++) {
32 results[i] = isApproved(applicants[i], guarantorMap, approvalSet, memo);
33 }
34
35 return results;
36 }
37
38 /**
39 * 특정 신청자가 대출 승인을 받을 수 있는지 재귀적으로 확인하는 헬퍼 함수
40 * @param applicant 현재 확인하려는 고객
41 * @param guarantorMap 보증 관계 맵
42 * @param approvalSet 초기 승인자 집합
43 * @param memo 중복 계산을 피하기 위한 캐시
44 * @return 승인 여부
45 */
46 private boolean isApproved(int applicant, Map<Integer, Integer> guarantorMap, Set<Integer> approvalSet,
Map<Integer, Boolean> memo) {
47 // 이미 계산된 결과가 있으면 즉시 반환 (메모이제이션)
48 if (memo.containsKey(applicant)) {
49 return memo.get(applicant);
50 }
51
52 // 현재 고객부터 시작하여 보증인 사슬을 따라 올라감
53 int current = applicant;
54 Set<Integer> visited = new HashSet<>(); // 순환 방지를 위한 방문 기록 (문제 조건상 불필요하나 안전장치)
55
56 while (true) {
57 // 기저 사례 1: 현재 고객이 초기 승인자이면, 승인
58 if (approvalSet.contains(current)) {
59 memo.put(applicant, true); // 원본 신청자의 결과를 캐시에 저장
60 return true;
61 }
62
63 // 이미 확인했던 중간 고객의 결과가 캐시에 있다면 사용
64 if (memo.containsKey(current)) {
65 boolean result = memo.get(current);
66 memo.put(applicant, result); // 원본 신청자의 결과를 캐시에 저장
67 return result;
68 }
69
70 // 방문 기록 추가 (무한 루프 방지)
71 if (visited.contains(current)) {
72 memo.put(applicant, false);
73 return false;
74 }
75 visited.add(current);
76
77 // 다음 보증인 탐색
78 Integer guarantor = guarantorMap.get(current);
79
80 // 기저 사례 2: 보증인이 더 이상 없으면, 거절
81 if (guarantor == null) {
82 memo.put(applicant, false); // 원본 신청자의 결과를 캐시에 저장
83 return false;
84 }
85
86 // 보증인을 따라 한 단계 위로 올라감
87 current = guarantor;
88 }
89 }
90
91 public static void main(String[] args) {
92 Solution sol = new Solution();
93
94 // 예시 1
95 int[][] relations1 = {{2, 1}, {3, 1}, {4, 2}};
96 int[] initial_approvals1 = {1};
97 int[] applicants1 = {3, 4, 5, 1};
98 boolean[] results1 = sol.solution(relations1, initial_approvals1, applicants1);
99 // 예상 결과: [true, true, false, true]Last updated