문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/49993
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
제한 조건
- 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 스킬 순서와 스킬트리는 문자열로 표기합니다.
- 예를 들어, C → B → D 라면 "CBD"로 표기합니다
- 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
- skill_trees는 길이 1 이상 20 이하인 배열입니다.
- skill_trees의 원소는 스킬을 나타내는 문자열입니다.
- skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
입출력 예
skill skill_trees return
| "CBD" | ["BACDE", "CBADF", "AECB", "BDA"] | 2 |
입출력 예 설명
- "BACDE": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
- "CBADF": 가능한 스킬트리입니다.
- "AECB": 가능한 스킬트리입니다.
- "BDA": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.
제출 코드
import java.util.*;
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
Map<Character,Integer> map = new HashMap<>();
for(int i=0; i<skill.length(); i++){
char c = skill.charAt(i);
map.put(c,i);
}
loop:
for(int i=0; i<skill_trees.length; i++){
String s = skill_trees[i];
int learned = -1;
for(int j=0; j<s.length(); j++){
char c = s.charAt(j);
int seq = map.getOrDefault(c,-1);
if(seq!=-1){
if(learned+1 == seq){
learned++;
}else{//그 이외의 모든 경우는 맞지 않다
continue loop;
}
}
}
//무사히 다 돌았다면 문제가 없는 것
answer++;
}
return answer;
}
}테스트 1 〉 통과 (0.13ms, 75.4MB)
테스트 2 〉 통과 (0.14ms, 68.8MB)
테스트 3 〉 통과 (0.17ms, 77.1MB)
테스트 4 〉 통과 (0.13ms, 74.5MB)
테스트 5 〉 통과 (0.16ms, 70.2MB)
테스트 6 〉 통과 (0.15ms, 77.5MB)
테스트 7 〉 통과 (0.33ms, 79.7MB)
테스트 8 〉 통과 (0.12ms, 73.4MB)
테스트 9 〉 통과 (0.17ms, 83.6MB)
테스트 10 〉 통과 (0.13ms, 75.2MB)
테스트 11 〉 통과 (0.21ms, 74.1MB)
테스트 12 〉 통과 (0.19ms, 74.7MB)
테스트 13 〉 통과 (0.15ms, 73.7MB)
테스트 14 〉 통과 (0.15ms, 75.5MB)코드 설명
HashMap에다 스킬트리의 순서를 저장함
스킬트리 하나씩 보면서 스킬트리중에 해당하는 것이 나오면 seq로 꺼내고
이전에 배웠던 스킬의 번호인 learned 와 비교함
seq가 존재할 경우 leanred보다 1만큼 크면 되는 스킬트리이고
그 이외의 모든 경우는 맞지 않아서 continue로 스킵해줌
스킵되지 않았다면 모든 순서가 맞는 스킬트리라 answer를 증가시켜줌
다른 사람의 풀이
1. 신기한 풀이
나는 이렇게 못 풀듯
import java.util.*;
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
ArrayList<String> skillTrees = new ArrayList<String>(Arrays.asList(skill_trees));
Iterator<String> it = skillTrees.iterator();
while (it.hasNext()) {
if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0) {
it.remove();
}
}
answer = skillTrees.size();
return answer;
}
}[^skill]를 사용하여 skill문자열을 제외한 나머지 문자 모두 제거 그리고 indexof로 순서를 무시하지 않았는지 확인 무시했다면 제거 마지막으로 길이 반환..
2. 빠른 풀이
나처럼 풀면 +2인데 이 사람처럼 풀면 +17..?
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
for (String skillTree : skill_trees) {
int learningIdx = 0;
boolean isAble = true;
for (char curSkill : skillTree.toCharArray()) {
int skillIdx = skill.indexOf(curSkill);
if (skillIdx == -1)
continue;
else if (skillIdx == learningIdx)
learningIdx++;
else {
isAble = false;
break;
}
}
if (isAble)
answer++;
}
return answer;
}
}나 나름 해쉬 생각해서 쓴건데... 이 코드가 훨씬 빠르다 charArray()를 보는것이 빠른가?
index쓰고 구조 자체는 나랑 비슷한거같기도
string.indexOf이거 처음봄 없으면 -1을 반환하는듯 함
내 코드에다 toCharArray() 적용해봄
import java.util.*;
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
Map<Character,Integer> map = new HashMap<>();
for(int i=0; i<skill.length(); i++){
char c = skill.charAt(i);
map.put(c,i);
}
loop:
for(int i=0; i<skill_trees.length; i++){
//String s = skill_trees[i];
char [] chars = skill_trees[i].toCharArray();
int learned = -1;
for(char c : chars){
int seq = map.getOrDefault(c,-1);
if(seq!=-1){
if(learned+1 == seq){
learned++;
}else{//그 이외의 모든 경우는 맞지 않다
continue loop;
}
}
}
//무사히 다 돌았다면 문제가 없는 것
answer++;
}
return answer;
}
}시간이 똑같다 거의
테스트 1 〉 통과 (0.14ms, 80.1MB)
테스트 2 〉 통과 (0.13ms, 71MB)
테스트 3 〉 통과 (0.15ms, 74.1MB)
테스트 4 〉 통과 (0.18ms, 77.5MB)
테스트 5 〉 통과 (0.18ms, 67.9MB)
테스트 6 〉 통과 (0.14ms, 84MB)
테스트 7 〉 통과 (0.16ms, 67.8MB)
테스트 8 〉 통과 (0.19ms, 80.3MB)
테스트 9 〉 통과 (0.13ms, 78.8MB)
테스트 10 〉 통과 (0.13ms, 72.7MB)
테스트 11 〉 통과 (0.25ms, 76.4MB)
테스트 12 〉 통과 (0.15ms, 75.4MB)
테스트 13 〉 통과 (0.14ms, 73.2MB)
테스트 14 〉 통과 (0.14ms, 80.9MB)
그러나 indexOf 를 쓰게 되면 굉장히 빨라진다
앞으로는 Hash대신 indexOf를 꼭 기억할 것...
import java.util.*;
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
// Map<Character,Integer> map = new HashMap<>();
// for(int i=0; i<skill.length(); i++){
// char c = skill.charAt(i);
// map.put(c,i);
// }
loop:
for(int i=0; i<skill_trees.length; i++){
//String s = skill_trees[i];
char [] chars = skill_trees[i].toCharArray();
int learned = -1;
for(char c : chars){
//int seq = map.getOrDefault(c,-1);
int seq = skill.indexOf(c);
if(seq!=-1){
if(learned+1 == seq){
learned++;
}else{//그 이외의 모든 경우는 맞지 않다
continue loop;
}
}
}
//무사히 다 돌았다면 문제가 없는 것
answer++;
}
return answer;
}
}테스트 1 〉 통과 (0.03ms, 76.9MB)
테스트 2 〉 통과 (0.05ms, 75MB)
테스트 3 〉 통과 (0.04ms, 75.2MB)
테스트 4 〉 통과 (0.05ms, 73.4MB)
테스트 5 〉 통과 (0.04ms, 75MB)
테스트 6 〉 통과 (0.04ms, 71.9MB)
테스트 7 〉 통과 (0.03ms, 75.4MB)
테스트 8 〉 통과 (0.03ms, 75.9MB)
테스트 9 〉 통과 (0.03ms, 76.5MB)
테스트 10 〉 통과 (0.03ms, 73.2MB)
테스트 11 〉 통과 (0.03ms, 74.6MB)
테스트 12 〉 통과 (0.06ms, 74.9MB)
테스트 13 〉 통과 (0.03ms, 71MB)
테스트 14 〉 통과 (0.03ms, 75.9MB)
그렇다면 내가 나름 머리써서 hash를 썼는데 charArray로 바꾼 다음에 그거 iterate하는 편이 더 빨랐던걸까도 해봄
import java.util.*;
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
// Map<Character,Integer> map = new HashMap<>();
// for(int i=0; i<skill.length(); i++){
// char c = skill.charAt(i);
// map.put(c,i);
// }
loop:
for(int i=0; i<skill_trees.length; i++){
//String s = skill_trees[i];
char [] chars = skill_trees[i].toCharArray();
int learned = -1;
for(char c : chars){
//int seq = map.getOrDefault(c,-1);
int seq = indexOf(c,skill);
if(seq!=-1){
if(learned+1 == seq){
learned++;
}else{//그 이외의 모든 경우는 맞지 않다
continue loop;
}
}
}
//무사히 다 돌았다면 문제가 없는 것
answer++;
}
return answer;
}
int indexOf(char target, String s){
int index = 0;
for(char c : s.toCharArray()){
if(c==target){
return index;
}
index++;
}
return -1;
}
}이렇게 해봤더니
테스트 1 〉 통과 (0.05ms, 82MB)
테스트 2 〉 통과 (0.03ms, 74.3MB)
테스트 3 〉 통과 (0.04ms, 76.7MB)
테스트 4 〉 통과 (0.06ms, 79.1MB)
테스트 5 〉 통과 (0.04ms, 73.3MB)
테스트 6 〉 통과 (0.04ms, 74.5MB)
테스트 7 〉 통과 (0.06ms, 75.1MB)
테스트 8 〉 통과 (0.04ms, 76.6MB)
테스트 9 〉 통과 (0.07ms, 75.7MB)
테스트 10 〉 통과 (0.04ms, 74.4MB)
테스트 11 〉 통과 (0.05ms, 73.2MB)
테스트 12 〉 통과 (0.05ms, 78.8MB)
테스트 13 〉 통과 (0.06ms, 65.8MB)
테스트 14 〉 통과 (0.06ms, 76.4MB)indexOf보다 느리긴 한데 확실히 해쉬 쓰는것보다 빨랐다
Hash는 비연속적일때나 쓰기로 했다
'Coding Test' 카테고리의 다른 글
| [프로그래머스] 프렌즈4블록 (1) | 2024.06.03 |
|---|---|
| [프로그래머스] 메뉴 리뉴얼 (1) | 2024.06.03 |
| [프로그래머스] 방문 길이 Java (0) | 2024.05.17 |
| [프로그래머스] 이모티콘 할인행사 (0) | 2024.04.17 |
| [백준] 나무 자르기 (0) | 2024.04.16 |
