조합 - 20529 가장 가까운 세 사람의 심리적 거리 & 조합 방식

문제 설명

이번 문제는 세 사람의 MBIT 심리적인 거리를 구하는 문제로

• (A,B 사이 거리) + (B,C 사이 거리) + (A,C 사이 거리) 의 최솟값

을 구해야합니다.

💡 즉, 조합으로 경우의 수를 찾고, 최솟값을 찾아야 합니다.

3중 For문으로 풀기

중첩 For 문은 적은 소규모 조합일 때, 가장 알맞는 조합방식입니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int len = str.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        
        for(int i = 1; i < len + 1; i++) {
            char c = str.charAt(i - 1);
            if(c != '0') {
                dp[i] += dp[i - 1];
            }
            
            if(i >= 2) {
                int num = 
                    Integer.parseInt(str.substring(i - 2, i));
                
                if(10 <= num && num <= 34) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        
        System.out.println(dp[len]);
    }
}

재귀로 풀기

재귀는 조합의 전형적 방식으로, 중첩 For문보다는 느리지만 간결하고 직관적이라는 장점이 있습니다.

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

public class Main {

  static int answer;
  static int[] arr;

  public static void main(String[] args) throws Exception {
    BufferedReader br =
        new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int freq = Integer.parseInt(br.readLine());

    next:
    for (int z = 0; z < freq; z++) {
      answer = Integer.MAX_VALUE;
      arr = new int[3];

      int seq = Integer.parseInt(br.readLine());
      StringTokenizer st =
          new StringTokenizer(br.readLine(), " ");
      Map<String, Integer> map = new HashMap<>();
      List<String> list = new ArrayList<>();

      // map + set 저장
      for (int i = 0; i < seq; i++) {
        String str = st.nextToken();
        if (map.containsKey(str)) {
          map.put(str, map.get(str) + 1);
        } else {
          map.put(str, 1);
        }
      }

      // 리스트 setting + key 3개 이상이면 0 insert
      for (String key : map.keySet()) {
        list.add(key);

        if (map.get(key) >= 3) {
          sb.append(0).append("\n");
          continue next;
        }
      }

      comb(list, map, arr, list.size(), 0);

      sb.append(answer).append("\n");
    }

    System.out.print(sb);
  }

  static void comb(List<String> list, Map<String, Integer> map,
      int[] arr, int seq, int depth) {

    if (depth == 3) {
      String aKey = list.get(arr[0]);
      String bKey = list.get(arr[1]);
      String cKey = list.get(arr[2]);

      if (arr[0] == arr[1] && arr[1] == arr[2]) {
        return;
      }

      if ((aKey.equals(bKey) && map.get(aKey) == 2)
          || (bKey.equals(cKey) && map.get(bKey) == 2)
          || (aKey.equals(cKey) && map.get(aKey) == 2)
          || (!aKey.equals(bKey) && !aKey.equals(cKey) && !cKey.equals(bKey))) {
        answer =
            Math.min(comp(aKey, bKey, cKey), answer);
      }

      return;
    }

    for (int i = 0; i < seq; i++) {
      arr[depth] = i;
      comb(list, map, arr, seq,depth + 1);
    }
  }

  public static int comp(String aKey, String bKey, String cKey) {
    int returnValue = 0;

    for (int i = 0; i < 4; i++) {
      returnValue += aKey.charAt(i) != bKey.charAt(i) ? 1 : 0;
      returnValue += bKey.charAt(i) != cKey.charAt(i) ? 1 : 0;
      returnValue += cKey.charAt(i) != aKey.charAt(i) ? 1 : 0;
    }

    return returnValue;
  }
}

느낀 점

• 재귀와 중복 반복문으로 조합을 각각 구현해보니, 각각의 장단점을 알 수 있었습니다.