Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

[Java]年俸1000万の会社の試験問題[速度重視]

More than 5 years have passed since last update.

4種類のアルファベット "A,C,G,T" から成るn文字の文字列のうち、
"AAG"という並びが含まれる文字列を全て列挙するプログラムを書きなさい。
ただし、nは3以上の整数とし、文字列内に同じアルファベットが出現しても構わないものとし、
出力順序は問わないものとします。
http://alpha.cgios.net/alpha/cgios

初投稿。しょぼい知識で高速化を図ってみました。もっといい方法あれば教えて下さい。

ACGTLogic.java
public class ACGTLogic {
    static final String[] CHARS = { "A", "C", "G", "T" };
    static final String REQUIRE_STR = "AAG";

    Map<Integer, List<String>> cache;

    public List<String> getList(int n) {
        if (n == REQUIRE_STR.length()) {
            List<String> list = new ArrayList<>();
            list.add(REQUIRE_STR);
            return list;
        }

        int reqNum = n - REQUIRE_STR.length();

        cache = new HashMap<>();
        List<String> pre, suf;
        Set<String> setList = new HashSet<>();
        createCache(reqNum);
        for (int i = 0; i <= reqNum; i++) {
            pre = cache.get(i);
            suf = cache.get(reqNum - i);

            for (int preIdx = 0; preIdx < pre.size(); preIdx++) {
                String preStr = pre.get(preIdx);
                for (int sufIdx = 0; sufIdx < suf.size(); sufIdx++) {
                    setList.add(new StringBuilder().append(preStr).append(REQUIRE_STR).append(suf.get(sufIdx))
                            .toString());
                }
            }
        }
        List<String> res = new ArrayList<>(setList);
        Collections.sort(res);
        return res;
    }

    private void createCache(int reqNum) {
        List<String> list = new ArrayList<>();
        list.add("");
        cache.put(0, list);
        for (int rep = 0; rep < reqNum; rep++) {
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                for (int j = 0; j < CHARS.length; j++) {
                    tmp.add(new StringBuilder().append(list.get(i)).append((CHARS[j])).toString());
                }
            }
            cache.put(rep + 1, tmp);
            list = tmp;
        }
    }
}
durandal
最近久々にマイクラを触って無性にMODを作りたくなったので頑張ってみる
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away