[Java/C++] 프로그래머스 Level 2 - 스킬트리

문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/49993? 

[Summer/Winter Coding 2018~]로 태그가 나와있던데 아무튼 그렇다.

직관적이고 단순하게 생각하면 된다.
복잡하게 생각하면 더 어려워지는 문제인 것 같다.

 

 

---

문제 핵심 및 풀이

---

선행 스킬 관계 만들기

특정 스킬을 익히기 전에 익혀야 할 스킬을 선행 스킬이라고 하겠다.

이건 단순하게 꼬리물기 구조로 만들어주면 된다."BCD"가 규칙일 때,
B → C → D라는 뜻인데, 연속적으로 이루어져 있다..

이걸 부모 자식 관계로 한번 바꿔서 생각해 보자.

C를 배우기 위해선 B가 필요하다. 즉, parent [C] = B가 된다.

D라는 스킬을 배우기 위해선 B, C 2개를 미리 배워야 하는데,
그렇다면 parent [D] = B, C가 될까?

이렇게 하지 않고 parent [D] = C로 표기해 줘도 된다.
스킬 C를 미리 배워놨다면, C의 선행인 B도 배운 것이 확정된다.

즉, 이런 식으로 자신의 바로 뒤에 있는 스킬(알파벳)을 부모로 삼기만 하면 된다.

이를 일반화하면 parent [i] = i-1 (여기서 i는 인덱스를 뜻함)가 된다.

 

---

가능한 스킬트리인지 체크하는 로직

선행관계만 만들었다면 이제 어려울 것이 없다.

여기서 부모가 없는 알파벳, 그러니까 선행스킬이 필요 없는 스킬들은
parent [k] = -1이 되도록 설정해 둔다.

그리고 해당 스킬을 찍었음을 알리기 위한 방문 배열 visited 또한 만들어둔다.

이제 skill_trees의 스킬트리를 하나씩 확인하면 된다.
각 스킬트리를 순차 탐색하면서 알파벳의 parent의 여부를 판단한다.

1. 해당 인덱스의 parent가 -1
방문 체크를 해주고, 다음 인덱스로 넘어간다.

2. 해당 인덱스의 parent가 -1이 아닐 때
선행 스킬이 존재한다는 뜻이다. 해당 시점에서 선행스킬이 방문됐는지를 확인한다.

만약 방문됐다면 선행스킬이 찍혀있는 것이므로, 해당 인덱스의 스킬도 방문처리하고 넘어간다.
만약 그렇지 않다면, false를 반환한다.

최종적으로 모든 반복문을 무사히 통과한다면,
스킬을 문제없이 찍을 수 있다는 뜻이므로 true를 반환하도록 한다.

 

---

알파벳의 인덱스화

문제에서 사용해야 하는 것이 문자라서 인덱스로 사용할 수 없다.
자료구조 Map을 쓰거나 하는 방법이 있겠지만, 나는 좀 더 간단한 방법으로 가보고자 한다.

바로 인덱스가 모두 하나의 대문자 알파벳인 것을 이용하는 것이다.
이는 모두 아스키코드로 이뤄져 있기 때문에 정수형으로 변환이 가능하다.

그래서 모든 알파벳에 'A'를 빼준다. 그러면 깔끔하게 0 ~ 25까지의 숫자가 나온다
이를 인덱스 번호로 사용하면 간단하게 해결된다.

이제 모든 문제점을 다 해결하고 로직도 제시했으니 바로 코드로 구현해 보자.

 

 

---

코드 구현

---

C++ 구현 코드

↓

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int parent[26]; // 모든 알파벳의 부모를 체크하기 위해 만든 배열

// 해당 스킬트리가 가능한지 체크
bool isPossible(string trees){
    bool visited[26] = {false,}; // 방문 확인을 위한 배열
    for(int i = 0; i < trees.size(); i++){
        int skill = trees[i]-'A';
        
        // 해당 알파벳의 선행 스킬이 존재하는 경우
        if(parent[skill] != -1){
            int pre = parent[skill]; // 선행 스킬
            
            // 선행 스킬을 방문하지 않았다면 false를 반환
            if(!visited[pre]) return false;
        }
        visited[skill] = true;
    }
    
    return true; // 모두 통과하면 true 반환
}

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    fill(parent,parent+26,-1); // 모든 부모를 -1로 초기화
    for(int i = 0; i < skill.size()-1; i++) {
    	// i번째를 i+1번째의 부모로 만듦
        parent[skill[i+1]-'A'] = skill[i]-'A';
    }
    
    for(auto trees : skill_trees){
        if(isPossible(trees)) answer++;
    }
    return answer;
}

 

 

 

---

Java 구현 코드

↓

import java.util.*;

class Solution {
    
    int[] parent = new int[26]; // 선행 스킬이 있는지 확인을 위한 배열
    
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        Arrays.fill(parent,-1); // parent 배열을 모두 -1로 초기화
        
        for(int i = 0; i < skill.length()-1; i++){
        	// i번째 알파벳을 i+1번째의 부모로 만듬
            parent[skill.charAt(i+1) - 'A'] = skill.charAt(i)-'A';
        }
        
        for(String trees : skill_trees){
            if(isPossible(trees)) answer++;
        }
        return answer;
    }
    
    // 해당 스킬트리가 가능한지 체크하는 함수
    public boolean isPossible(String trees){
    	// 각 스킬이 방문되었는지 확인하기 위한 배열
        boolean[] visited = new boolean[26];
        Arrays.fill(visited,false); // false로 초기화
        for(int i = 0; i < trees.length(); i++){
            int skill = trees.charAt(i)-'A';
           	
            // 부모(선행 스킬)가 존재하는 경우
            if(parent[skill] != -1){
                int pre = parent[skill]; // 선행 스킬
                
                // 선행 스킬이 방문되지 않았다면 false 반환
                if(!visited[pre]) return false;
            }
            visited[skill] = true;
        }
        return true; // 이를 모두 통과했다면 true 반환
    }
}

↑

 

 

 

 

---

시행착오

해당 문제는 직관적으로 풀 수 있었고,
구현도 딱히 어려웠던 부분은 없었어서 쉽게 풀 수 있었다.

https://toss.me/howudong

howudong님에게 보내주세요