출처 프로그래머스
문제
문제는 다음과 같다.
"CBD"가 스킬이라고 하면
B가 C보다 앞에 있거나
D가 C나 B보다 앞에 있으면 불가능한 스킬트리이다.
그런데 고려해야할 점이 있다.
1. skill_trees의 문자열들이 skill의 문자열을 일부만 포함하거나 아예 없는 경우
이 경우는 가능한 스킬이다
위의 입출력 예시에서도
skill이 "CBD" 일 때 "AECB"는 'D'가 없어도 가능한 스킬이다.
2. skill의 길이가 1인 경우
이 경우엔 선행스킬이 없는 것이나 마찬가지다. 따라서 모두 정답이다
풀이
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
|
#include <string>
#include <vector>
#include <iostream>
#define NOT_FOUND string::npos
#define ONLY_ONE_SKILL 1
using namespace std;
int solution(string skill, vector<string> skill_trees) {
int answer = 0;
vector<string>::iterator iter;
int current_index = 0,check_index=0;
bool enable;
if (skill_len == ONLY_ONE_SKILL)
return skill_trees.size();
for (iter = skill_trees.begin(); iter != skill_trees.end(); iter++) {
enable = false;
for (int i = 0; i < skill_len-1; i++) {
current_index = (*iter).find_first_of(skill[i]);
check_index = (*iter).find_first_of(skill[i+1]);
if (current_index == NOT_FOUND)
{
enable = true;
for (int j = i + 1; j < skill_len; j++) {
if ((*iter).find_first_of(skill[j]) != NOT_FOUND)
enable = false;
}
break;
}
if (current_index < check_index || check_index == NOT_FOUND)
enable = true;
else {
enable = false;
break;
}
}
if (enable)
answer++;
}
return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
소스가 좀 복잡하다.
문자를 처음 하나하나씩
string의 find_first_of()를 이용하여 처음으로 나온 문자의 위치(index)를 찾았고
바로 그 다음 문자의 위치를 같은 함수로 찾아서 비교하였다.
발견되지 않는 문자의 경우 해당 문자 뒤의 문자들을 검색하여 가능여부를 판단하였다.
ex) "CBD"에서 "C"가 발견되지 않는 경우
"B", "D"를 검색했을 때
문자가 있다면 -> 그 스킬트리는 불가능하다
문자가 없다면 -> 그 스킬트리는 가능하다
문자가 발견되는 경우엔 다음 문자의 위치와 비교하여 가능여부를 판단하였다.
ex) "CBD"에서 'C'의 위치를 찾음
그 후 'B'의 위치를 찾는다
"B"가 존재하면 'B'의 위치와 'C'의 위치를 비교하여 'C'가 더 앞에 있다면 가능하다고 판단하였다.
"B"가 존재하지 않는 경우도 가능하다고 판단하였다. (고려사항 1번)
마지막으로 스킬의 길이가 1인 경우 모두 가능한 스킬이라 판단하여
스킬트리의 사이즈를 바로 리턴하였다.
'About > Algorithm' 카테고리의 다른 글
[프로그래머스][C++] 크레인 인형뽑기 게임(카카오 2019 개발자 겨울 인턴십 문제) (0) | 2020.05.07 |
---|---|
[프로그래머스][C++] 카카오 프렌즈 컬러링 북 (0) | 2020.03.28 |
[프로그래머스][C++] 땅따먹기 (0) | 2020.03.28 |
[프로그래머스][C++] 가운데 글자 가져오기 (0) | 2020.03.26 |
[프로그래머스][C++] 124 나라의 숫자 (0) | 2020.03.26 |