https://programmers.co.kr/learn/courses/30/lessons/49993?language=java

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public int solution(String skill, String[] skill_trees) {
    char[] ch = skill.toCharArray();

    List<ArrayList<Skill>> l = new ArrayList<ArrayList<Skill>>();
    for (String element : skill_trees) {
        ArrayList<Skill> list = new ArrayList<Skill>();

        for (int i = 0; i < ch.length; i++) {
            Skill s = new Skill();
            s.skill = ch[i];
            s.index = element.indexOf(ch[i]);

            if (s.index != -1) {
                list.add(s);
            }
        }

        l.add(list);
    }

    int answer = 0;
    for (ArrayList<Skill> list : l) {
        Collections.sort(list, new Comparator<Skill>() {
            @Override
            public int compare(Skill o1, Skill o2) {
                return o1.getIndex().compareTo(o2.getIndex());
            }
        });

        StringBuilder sb = new StringBuilder();
        for (Skill s : list) {
            sb.append(s.getSkill());
        }

        if (skill.startsWith(sb.toString())) {
            answer++;
        }
    }

    return answer;
}

public class Skill {
    private int index;
    private char skill;

    public Integer getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    public char getSkill() {
        return skill;
    }
    public void setSkill(char skill) {
        this.skill = skill;
    }
}

흐름

  1. 스킬트리에 있는 스킬들을 선행스킬 만큼 반복한다.

  2. 돌면서 스킬들에서 선행스킬의 index와 선행스킬명을 저장하는 클래스(Skill)에 저장하고 그 클래스를 List에 저장한다.

    • ex) List = [{index = 1, skill = A}, {index = 7, skill = Q}, …]

  3. 선행스킬명을 저장한 List를 다른 List(AllSkillList)에 저장한다.

    • 전체 스킬을 저장해야 하므로
    • ex) AllSkillList = [List1, List2, List3, …]

  4. 전체 스킬이 저장된 List(AllSkillList)를 돌면서 저장된 List의 Skill의 Index 순으로 정렬 시킨다.

  5. 정렬된 List를 돌면서 StringBuilder에 스킬명을 담는다.

  6. 입력받은 선행스킬과 비교하여 일치하면 answer을 증가 시킨다.

  7. 끝

다른 분의 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
public int solution(String skill, String[] skill_trees) {
    int answer = 0;
    ArrayList<String> skillTrees = new ArrayList<String>(Arrays.asList(skill_trees));
    Iterator<String> it = skillTrees.iterator();

    while (it.hasNext()) {
        if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0) {
            it.remove();
        }
    }
    answer = skillTrees.size();
    return answer;
}

로직

  • 스킬트리에 있는 스킬들 중 선행스킬이 아닌 녀석들을 없애버리고 선행스킬과 일치하는 지 확인해서 일치하지 않으면 List에서 삭제하고 List의 갯수를 return 하는 것으로 끝을 낸다.

  • ex) “CBD” 인 경우 “BACDE”에서 “C”, “B”, “D”가 아닌 녀석들은 삭제되서 “BCD”가 남지만 “CBD”.indexOf(“BCD”) 할 경우 “CBD”에 “BCD”가 존재 하지 않으므로 1을 return 하고 -1은 0이 아니므로 List에서 삭제된다.

  • “BDA” 인 경우엔 “CBD”.indexOf(“BD”) 할 경우 “CBD”에 존재하지만 1 번째 index에 존재하므로 1을 return 하고 List에서 삭제된다.

  • 직관적이고 가독성이 좋다.

  • 정규표현식 활용도 굿

결과

1 번

번호 속도
테스트 1 통과 (1.40ms, 52.1MB)
테스트 2 통과 (1.37ms, 50.1MB)
테스트 3 통과 (1.29ms, 52.7MB)
테스트 4 통과 (1.11ms, 52.3MB)
테스트 5 통과 (1.42ms, 50.6MB)
테스트 6 통과 (1.33ms, 52.4MB)
테스트 7 통과 (1.38ms, 50.5MB)
테스트 8 통과 (1.38ms, 50.8MB)
테스트 9 통과 (1.46ms, 52MB)
테스트 10 통과 (1.26ms, 52.4MB)
테스트 11 통과 (1.36ms, 54.3MB)
테스트 12 통과 (1.72ms, 52.5MB)
테스트 13 통과 (1.27ms, 52.3MB)
테스트 14 통과 (1.31ms, 52.2MB)

2 번

번호 속도
테스트 1 통과 (17.73ms, 54.5MB)
테스트 2 통과 (18.75ms, 52.2MB)
테스트 3 통과 (17.83ms, 52.4MB)
테스트 4 통과 (19.98ms, 54.3MB)
테스트 5 통과 (20.10ms, 52.3MB)
테스트 6 통과 (20.89ms, 52.5MB)
테스트 7 통과 (20.94ms, 54.3MB)
테스트 8 통과 (18.68ms, 52.2MB)
테스트 9 통과 (19.60ms, 52.8MB)
테스트 10 통과 (20.75ms, 54.4MB)
테스트 11 통과 (18.02ms, 52.3MB)
테스트 12 통과 (18.70ms, 54.3MB)
테스트 13 통과 (18.79ms, 52.5MB)
테스트 14 통과 (19.85ms, 54.8MB)
  • 2 번의 경우 Arrays.asList(skill_trees) 와 replace 때문에 속도가 살짝 느려진 것으로 판단된다.

테스트 케이스

1
2
3
4
5
6
assertEquals(3, test.solution("CBD", new String[] {"BACDE", "CBADF", "AECB", "BDA", "ASF", "BDF","CEFD"}));
assertEquals(4, test.solution("C", new String[] {"BACDE", "CBADF", "AECB", "BDA"}));
assertEquals(2, test.solution("CBD", new String[] {"C", "D", "CB", "BDA"}));
assertEquals(2, test.solution("AC", new String[] {"ABC", "CA", "ATEW", "SFCQTA"}));
assertEquals(2, test.solution("ACHQ", new String[] {"TWER", "FGCHQEA", "ATEW", "SFCQTA"}));
assertEquals(4, test.solution("CBDK", new String[] {"CB", "CXYB", "BD", "AECD", "ABC", "AEX", "CDB", "CBKD", "IJCB", "LMDK"}));
  • 임의로 만든 테스트 케이스 이므로 위 테스트 케이스를 통과해도 시험에서 통과하지 못할 가능성이 있다.