문제

[프로그래머스] 스킬트리

접근방법

1. 임의의 스킬트리에서 요구 스킬트리과 겹치는 부분은 string 에 담는다
2. 요구스킬트리의 i 번째요소와 저장된 string의 i 번째를 비교한다
3. 같다면 count를 증가
4. string의 길이와 count가 같다면 순서대로 되어 있는 것

위와 같은 풀이가 가능한 것은 요구스킬트리의 뒷부분은 생략가능해도 앞부분은 생략불가이기 때문이다
또 가운데 부분도 생략불가이다

그러므로 두 string의 i번째는 같아야 한다

어려웠던 점

문제를 잘 이해하지 못했다

앞부분도 생략가능하다고 생각하고 문제를 푸니 문제풀이가 복잡하게 느껴졌다
bitset과 askiii에 따라 배열에 넣고 문제를 푸는 방법도 생각해봤는데 명확한 방법이 떠오르지 않았다

해결

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
	int answer = 0;

	for (auto x : skill_trees) {
		string s = "";
		for (auto y : x) {
			for (auto a : skill) {
				if (y == a) { // 겹치는 부분 검사
					s += a;   // 스킬트리에 있다면 string에 넣어준다
					break;    // 중복되는 것은 없으니 찾았다면 break
				}
			}
		}
		cout << s << '\n';
		int len = s.size();
		int cnt = 0;
		for (int i = 0; i < len; i++) {
			if (skill[i] == s[i]) {		// skill과 비교한다 뒤는 빠질 수 있지만 앞에 것들은 반드시 빠질 수 없다
				cnt++;					// 그래서 i번째를 비교하면 된다
			}
		}
		if (cnt == len) {
			answer++;					// 길이가 같다면 모두 순서에 맞는 것이다
		}
	}
	return answer;
}

참고블로그