[C++] 프로그래머스 스킬트리 - 인덱싱 방법 실패, 해시 맵 알고리즘 구상

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49993#fn1

 

리뷰

주어진 skill의 character 순서에 맞는 skill_trees 인지를 구분하는 방법을 찾는 데 오랜 시간이 걸렸다.

처음에는 skill_trees의 string과 비교하면서 같은 문자일 경우, 이전 idx보다 작은 위치라면 false, ... 의 방식으로 indexing 으로만 해결하려고 하였다(그랬더니 2~3개의 예외 케이스에서 자꾸 실패했다)

실패하는 예외케이스를 생각할 수 없어 그 다음에는 배열을 만들어 비교하려고 하였으나, 엉성해서 성공하지 못했다.

 

어떠한 알고리즘을 사용해야 하는지 쉽게 떠올리지 못했고, 다소 빠르게 해결하고자 마음이 급했다.

 

포인트

• string을 가지고 문제를 풀 경우, string.find(), string::npos 등의 라이브러리 함수를 생각하면 더 쉽게 풀릴 수 있다.
• '아닌' 경우에 대해 bool flag를 이용하려다 보니 지저분해진다. 새로운 함수를 이용해 아닌 경우라면 flag = false 보다는, 바로 리턴해버리는 것도 간결한 코딩이 될 수 있다.
• 예외 케이스를 생각해내지 못했다. 이 문제의 경우 '예외'는
  1. 알파벳을 찾은 경우 && (이전 알파벳 idx보다 앞에 있는 경우) -- answer에 해당 X
  2. 알파벳을 못 찾은 경우 && 이전 알파벳은 찾은 경우                --- answer에 해당 X
  나머지는 answer.
  로 나뉜다. 간결하게 정리하면,
  1. 알파벳을 찾은 경우 && (이전 알파벳 idx보다 앞에 있는 경우 || 이전 알파벳은 못찾은 경우) answer X
  2. 그 외의 경우 answer ++
  이다.

 

해결

문제의 핵심은 주어진 문자열의 오름차순으로 만들어지는지를 확인하는 것이다(skill의 첫 문자부터 시작하는 부분문자열이어야한다는 것이 핵심) 이렇게 얘기하면 substr로 풀 수 있을 것 같지만, skill의 첫 문자부터 시작해야하기에 번거로운 작업이 들어갈 것이다.

이 경우 skill[i] == skill_tree[j][k]일 때의 cnt를 저장함으로써 비교할 수 있다.

주어진 skill 문자열의 문자 별 idx값을 map으로 지정할 수 있다. 이후 skill_tree의 문자열들에 대해, skill과 같은 문자일 경우 cnt++을 수행하면서, skill과 같은 순서로 구성되어있는지를 비교할 수 있다.

 

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

using namespace std;

bool skill_check(string& skill, string& skilltree){
    bool not_find = false;
    int prev = 0;
    
    for(auto s : skill){
        int cur = skilltree.find(s);
        if(cur != string::npos){
            if(not_find || prev > cur) // 이전 것은 못 찾았으나 현재 것은 찾았는 경우 + 둘 다 찾았는데 cur idx가 더 작은경우
                return false;
            else
                prev = cur;
        }
        else
            not_find = true;
    }
    
    return true;
}

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    /*
    // 방법 3
    for(auto skilltree : skill_trees){
        if(skill_check(skill, skilltree))  answer ++;
    }
    
    */
    
    /*
    // 방법 2
    map<char, int> skill_map;
    for(int i=0; i<skill.size(); i++)
        skill_map[skill[i]] = i+1;
    
    for(int st=0; st<skill_trees.size(); st++){
        string skilltree = skill_trees[st];
        map<char, int> compare;
        int idx = 1;
        
        for(int i=0; i<skilltree.size(); i++){
            for(int j=0; j<skill.size(); j++){
                if(skilltree[i] == skill[j]){
                    compare[skill[j]] = idx;
                    idx ++;
                }
            }
        }
        bool find_flag = true;
        for(auto iter=compare.begin(); iter!=compare.end(); iter++){
            if(compare[iter->first] != skill_map[iter->first]){
                find_flag = false;
                break;
            }
        }
        if(find_flag)
            answer ++;
    }
    */
    
    
    // 방법 1
    for(int st=0; st<skill_trees.size(); st++){
        string skilltree = skill_trees[st];
        int idx_before = -1;
        bool find_flag = true, before = false;
        
        for(int i=0; i<skill.size(); i++){
            int idx = skilltree.find(skill[i]);
            
            if(idx != string::npos){
                if(idx_before > idx || before){           // 이전 ch보다 idx가 작거나, 이전건 없었는데 이번엔 있는 경우
                    find_flag = false;
                    break;
                }
                else
                    idx_before = idx;
            }
            else
                before = true;                           // 이전 게 없는 경우 true로 해놓는다. 이후 것이 나오면 이제 틀린 것이다.
              
            /*
            if(skill[i] == skilltree[j]){       // 못 찾는 경우에 대한 케이스가 없다.
                if(i != 0 && (idx_before == -1 || idx_before > j))      // 이전 것보다 idx가 적거나, 처음 찾는 거라면 .. 이라고 했다.
                    find_flag = false;
                else
                    idx_before = j;
                break;
            }
            
            if(!find_flag)  break;
            */
        }
        if(find_flag)
            answer ++;
    }
    
    return answer;
}