문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49993
문자열 비교 문제이다.
skill 이라는 문자열과 skill_trees 라는 배열이 입력으로 주어질 때
( ※ skill_trees는 문자열이 담긴 배열이다.)
skill_trees에 담긴 각 문자열들 중에서, skill의 순서를 따르는 문자열을 골라 그 개수를 출력하는 문제이다.
문제에 적힌 예시를 적어보면,
skill = "CBD" 이고
skill_trees = ["BACDE", "CBADF", "AECB", "BDA"] 일 때
ㄱ. BACDE ==>> B 스킬을 배우기 전에 C 스킬을 먼저 배워야하므로 규칙에 위배된다.
ㄴ. CBADF ==>> 규칙에 맞으므로 가능한 스킬트리이다.
ㄷ. AECB ==>> 규칙에 맞으므로 가능한 스킬트리이다.
ㄹ. BDA ==>> B 스킬을 배우기 전에 C 스킬을 먼저 배워야하므로 규칙에 위배된다.
따라서, 가능한 스킬트리는 모두 2개이므로 정답은 2가 된다.
내가 푼 방법은 이러하다.
문제의 설명에서 입력값은 중복없이 알파벳을 나열한 문자열이라고 하였다.
어차피 중복이 없으므로, 루프당 최고로 수행되는 횟수는 26이다. ( 알파벳은 26개이다. )
그렇기에 제일 첫 번째로 생각한 방법은 skill_trees의 각 문자열들에서 불필요한 문자들을 제거한다는 생각을 하였다.
중복이 없기때문에 이 방법을 시행한다면, 나중에는 skill에 존재하는 알파벳들만 존재할 것이다.
이렇게 할 경우, 위의 예시에서 skill_trees의 값들은 ["BCD", "CBD", "CB", "BD"] 이렇게 바뀔 것이다.
이 방법을 진행하면 skill_trees에 존재하는 값들은 모두 skill에 존재하는 알파벳만 남게 될 것이고
중복이 없으므로 skill의 길이보다 작거나 같을 것이다.
즉, 인덱스가 같은 부분만 비교한 후 같지 않으면 규칙에 위배되므로 다음 스킬트리로 넘어가는 알고리즘을 만들 수 있다.
아래는 코드이다.
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
|
#include <string>
#include <vector>
using namespace std;
int solution(string skill, vector<string> skill_trees) {
int answer = 0;
int skillSize = skill.size(); //스킬의 개수
int treeSize = skill_trees.size(); //스킬트리의 개수
int exception = 0; //올바르지 않은 스킬트리의 개수
//불필요한 문자열 제거
for (int i = 0; i < treeSize; i++) {
string duplication = "";
string temp = skill_trees[i];
int tempSize = temp.size();
for (int j = 0; j < tempSize; j++) {
for (int k = 0; k < skillSize; k++) {
if (skill[k] == temp[j]) {
duplication += temp[j];
}
}
}
skill_trees[i] = duplication;
}
//문자열 비교
for (int i = 0; i < treeSize; i++) {
string temp = skill_trees[i];
int tempSize = temp.size();
for (int j = 0; j < tempSize; j++) {
//같은 인덱스 값이 같지 않을 경우 무조건 규칙에 어긋난다.
if (temp[j] != skill[j]) {
exception++;
break;
}
}
}
answer = treeSize - exception;
return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'컴퓨터 공학 > 문제풀이' 카테고리의 다른 글
키패드 누르기(프로그래머스) (0) | 2022.03.19 |
---|---|
카카오프렌즈 컬러링북(프로그래머스) (0) | 2020.04.16 |