[Java] 프로그래머스(level-2) - 스킬트리
문제 풀이
이번 문제는 문제의 요구사항대로 구현하면 풀 수 있는 간단한 문제이다.
아이디어 도출
사용자들이 만든 스킬트리들이 정해진 스킬트리를 잘 따랐는지를 확인하기 위한 방법은 많으나 필자가 떠올린 방법은 간단하다.
- 만든 스킬트리들을 순회하며 선행스킬에 포함된 스킬인지를 확인한다.
- 선행스킬에 포함된 스킬이라면 1번째 스킬인지, 2번째 ~ N번째 스킬인지 확인한다.
- 현재 스킬이 1번째 스킬이라면 바로 습득한다.
- 현재 스킬이 2번째 ~ N번째 스킬이라면 이전 스킬 습득여부를 확인한다.
4.1. 이전 스킬을 습득하지 않았다면 선행스킬순서를 지키지 않았기에 순회를 종료하고 가능여부를 불가능으로 갱신한다.
4.2. 이전 스킬을 습득했다면 현재 스킬을 습득한다.
위 아이디어를 구현하기 위해 HashMap과 Array를 적절하게 사용했다.
다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.
작성 코드
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.*;
class Solution {
public int solution(String skill, String[] skill_trees) {
// 가능한 스킬트리의 개수를 담을 변수
int answer = 0;
// 만든 스킬트리들 중에서 정해진 스킬트리를 잘 따랐는지 확인하기 위해 Map에 담는다.
Map<String, Integer> hm = new HashMap<>();
for(int i=0; i<skill.length(); i++) {
hm.put(String.valueOf(skill.charAt(i)), i);
}
for(int i=0; i<skill_trees.length; i++) {
// 스킬트리 가능 여부
boolean possiable = true;
// 선행 스킬 습득 여부를 담을 배열
int[] check = new int[skill.length()];
/**
* 만든 스킬트리를 순회하며 가능한 스킬트리인지를 검증한다.
* 정해진 스킬트리의 스킬이 아니라면 검사하기 않는다.
* 스킬트리의 포함된 스킬이라면 첫번째 스킬인지, 두번째~N번째 스킬인지 확인한 후,
* 선행 스킬 습득 여부를 판단하여 스킬 가능 여부를 갱신한다.
*/
for(int j=0; j<skill_trees[i].length(); j++) {
String now = String.valueOf(skill_trees[i].charAt(j));
// 스킬트리에 존재하지 않는 스킬이라면 스킵.
if(!hm.containsKey(now)) {
continue;
}
// 스킬트리의 첫번째 스킬일 경우
if(hm.get(now) == 0) {
check[0] = 1;
}
// 스킬트리의 두번째부터 N번째 스킬일 경우
else {
// 이전 스킬을 습득하지 않은 경우 불가능한 스킬트리이다.
if(check[hm.get(now)-1] == 0) {
possiable = false;
break;
}
// 이전 스킬을 습득했을 경우 현재 스킬도 습득 가능하다.
else {
check[hm.get(now)] = 1;
}
}
}
// 만든 스킬트리는 가능한 스킬트리이다.
if(possiable) {
answer++;
}
}
return answer;
}
public static void main(String[] args) {
Solution sol = new Solution();
String skill = "CBD";
String[] skill_trees = new String[]{"BACDE", "CBADF", "AECB", "BDA"};
sol.solution(skill, skill_trees);
}
}
회고
- 다른 분들의 풀이를 보니 스트림 공부의 필요성을 절실히 느낀다.
출처
- —
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.