[프로그래머스] Summer/Winter Coding 스킬트리 level2

문제 :

programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

 

분석 :

분명 나보다 더 효율적인 코드가 있을 것이라 생각한다! 

하지만 이 문제는 다행히(?) 효율성 체크하는 문제가 아니여서 맞출 수 있었다. (soma 첫 게임 문제와 비슷한 유형의 문제라(근데 그 친구는 위상 정렬이었다) 꼭 풀고 싶었다)

 

이 문제는 전에 최장 공통 부분 수열 공부했을때 언뜻 봤었던 최장 공통 부분 문자열과 비슷해 보이지만 skill의 모든 문자열을 스킬 트리가 가지고 있지 않아도 된다는 점에서 조금 다르다.

만약에 제시된 skill 순서가 CBD 이고 순서에 맞는지 검사하고 싶은 대상들 {"CBADF", " AECB", "OPQ", "CED"}가 주어졌다고 했을 때 

답은 {"CBADF", " AECB"} 가 되어야 한다. 즉 순서에만 맞추면 되는 것이지 skill이 가진 모든 문자열을 skillTree가 가지고 있지 않아도 된다는 점이다.

 

그래서 접근한 방식은 

1. skillTree의 각 문자열에 접근해 skill에 있는 문자열만 re_skillTree 배열에 담기

2. re_skillTree에 대하여 size가 0일 경우 ex> "OPQ" skill 조건에 위배되지 않으므로 +1

3. re_skillTree에 대하여 size가 0이 아닐 경우 skill과 순서가 맞는지 검사

 

3번에서 re_skillTree는 skill에 있는 문자열만 담겼으므로 순서가 다르다면 위배되는 조건이다

따라서 인덱스가 같이 움직인다면 나중에 

 

k와 n의 인덱스가 같을 것으로 예상되므로 +1 증가시켜준다.

전체 코드는 아래와 같다!

 

c++ 코드 :

//
//  [SW] 2018_skillTree.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/30.
//

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <vector>


using namespace std;

int main(){
    int answer = 0;
    string skill = "CBD";
    vector<string> skillTree = {"BACDE", "CBADF", "AECB", "BDA","OPQ", "CED"};
    vector<char> re_skillTree;
    
    for(int i =0; i < skillTree.size(); i++){
        
        for(int j = 0; j < skillTree[i].size(); j++){
            if(skill.find(skillTree[i][j]) != string::npos){
                re_skillTree.push_back(skillTree[i][j]);
            }
        }
        
        //주어진 스킬 조건이 하나도 없어도 정답
        if(re_skillTree.size() == 0){
            answer++;
        }else{
            //있으면 순서 비교
            int k = 0; int n = 0;
            for(int i = 0; i < re_skillTree.size(); i++){
                if(re_skillTree[n] == skill[k++]){
                    n++;
                }else{
                    break;
                }
            }
            if(k != 0 && n != 0 && k == n){
                answer++;
            }
        }
        
        re_skillTree.clear();

    }

    cout << answer << '\n';
    return 0;
}

 

 

결과 :