반응형
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/49993#fnref1
문제
코드, 풀이
이 문제는 map을 통해서 간단하게 풀 수 있다고 생각합니다.
물론 vector에 push_back을 하면서 진행을 해도 괜찮다고 생각을 합니다.
최근에 map을 많이 사용하고 있어서 map으로 풀이를 진행하였습니다.
1. skill에 대한 인덱스를 넣어줍니다. (향후 비교를 위해)
2. 반복문을 돌면서 같은 idx가 나온다면 idx를 ++ 해줍니다 (1번의 인덱스와 같이 계속 늘어나겠죠.)
3. 순서가 뒤짚힌 것에 대한 체크를 해야하니 map에서 찾았는데 idx보다 크다는 것은 뒤에 와야할것이 먼저 왔으니 break;
4. 끝에 도달하였거나 idx == lastSkill -> 조금이라도 먼저 완성을 했다면 return 합니다.
/*
음.. 그냥 반복문 돌면서 확인하면 끝 아닌가?
아 아니다 맵을 사용하면 되겠다.
*/
#include <string>
#include <vector>
#include <map>
using namespace std;
int solution(string skill, vector<string> skill_trees) {
int answer = 0;
int lastSkill = skill.length() - 1;
map<char,int> m;
for(int i = 0; i < skill.length();i++)
m[skill[i]] = i;
for(int i = 0 ; i < skill_trees.size();i++){
int idx = 0;
for(int j = 0; j < skill_trees[i].length();j++){
if(skill_trees[i][j] == skill[idx])
idx++;
else{
//맵에 존재하고 index가 더 크다 -> 뒤에 스킬이다.
if(m.find(skill_trees[i][j]) != m.end() && m[skill_trees[i][j]] > idx)
break;
}
//끝에 도달했거나 idx == lastSkill이라는 것은 이제 스킬을 다 사용.
if(idx == lastSkill || j == skill_trees[i].length() - 1){
answer++;
break;
}
}
}
return answer;
}
반응형
'알고리즘 > c++ 프로그래머스' 카테고리의 다른 글
[프로그래머스 뒤에 있는 큰 수 찾기] c++ (코드, 풀이, 스택) (0) | 2023.06.02 |
---|---|
[프로그래머스 파일명정렬] c++ (풀이,코드,카카오3차코테) (0) | 2023.06.01 |
[프로그래머스 게임 맵 최단거리] c++ (코드,풀이, bfs) (2) | 2023.05.24 |
[프로그래머스 방문 길이] c++ (풀이, 코드) (0) | 2023.05.24 |
[프로그래머스 정수삼각형] c++ (풀이, 코드, level3) (1) | 2023.05.22 |
댓글