백준 25758번 유전자 조합 Java

https://school.programmers.co.kr/learn/courses/30/lessons/59411?language=mysql

문제

---

생각하기

---

• 자료구조, 부르트포스, 해시 문제이다.

동작

이 문제의 핵심은 중복을 관리하는 것 같다.

같은 유전자를 중복으로 저장하지 않는 것,

그렇다고 모든 유전자를 Set에 저장해서 하나만 남기는 것은 아니다.

AA가 2개 있을 경우, A의 표현형이 나와야 한다.
근데 같은 유전자가 굳이 2개를 초과할 필요가 없기 때문에 HashMap에 2개까지만 저장하도록 했다.

이렇게 해서 중복을 잘 관리하면 정답을 구할 수 있음

결과

코드

---

import java.io.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

    // input
    private static BufferedReader br;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        HashSet<String> set = new HashSet<>();
        HashMap<String, Integer> map = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            String str = st.nextToken();

            if (map.get(str) != null && map.get(str) >= 2) continue;
            map.put(str, map.getOrDefault(str, 0) + 1);
            set.add(str);
        }
        TreeSet<Character> geneSet = new TreeSet<>();
        for (String key : map.keySet()) {
            int value = map.get(key);

            if (value == 2) {
                char ch = makeGene(key, key);
                geneSet.add(ch);
            }
        }


        for (String a : set) {
            for (String b : set) {
                if (a.equals(b)) continue;
                char ch = makeGene(a, b);
                geneSet.add(ch);
            }
        }

        sb.append(geneSet.size()).append('\n');
        for (char ch : geneSet) {
            sb.append(ch).append(' ');
        }
        return sb.toString();
    } // End of solve()

    private static char makeGene(String a, String b) {
        char ch1 = a.charAt(0);
        char ch2 = b.charAt(1);

        if (ch1 > ch2) {
            return ch1;
        } else {
            return ch2;
        }
    } // End of makeGene()
} // End of Main class