JAVA풀이 => 15점밖에 안나옴 샘플케이스가 다 맞았어도 실제 채점해보면 런타임에러나고 오류나는 경우가 많다
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | package programmers; import java.util.*; import java.io.*; public class pretest7{ public static void main(String[] args){ /* String str1[]={"ba","na","n","a"}; String t1[]={"banana"}; solution(str1,t1); String str2[]={"app","ap","p","l","e","ple","pp"}; String t2[]={"apple"}; solution(str2,t2); String str3[]={"ba","an","nan","ban","n"}; String t3[]={"banana"}; solution(str3,t3); } */ // System.out.println(solution(new String[] { "ab", "na", "n", "a", "bn" }, "nabnabn")); // System.out.println(solution(new String[] { "ba", "an", "nan", "ban","n" }, "banana")); System.out.println(solution(new String[] { "ba", "na", "n", "a" }, "banana")); System.out.println(solution(new String[] { "app", "ap", "p", "l", "e", "ple", "pp" }, "apple")); System.out.println(solution(new String[] { "ba","an","nan","ban","n"},"banana")); } private static int solution(String[] strs,String t){ String[] dp = new String[t.length()]; int[] dpMin = new int[t.length()]; //Arrays.fill은 전체 배열을 채우는 방식이다. Arrays.fill(dp,""); Arrays.fill(dpMin,999999); dpMin[0] = 0; int pivot =0; for(int index=0;index < t.length(); index++){ // String word = strs[index]; //이전 dp를 쓰기 위한 pivot pivot = (index ==0)? 0 : index-1; int depth = dpMin[pivot]; String tempDp = dp[pivot]; //(text - 이전 dp)에서 남은 것 중 찾기 for(String word : strs){ if(t.substring(tempDp.length(), index+1).startsWith(word)==true){ dp[index] = tempDp + word; dpMin[index] = depth + 1; // System.out.println("dp: " + dp[index]); break; } } System.out.println("index: " + index + " pivot: "+ pivot); //더 나은 것 없나 찾기 while(pivot-1 >=0){ for(String word : strs){ depth = dpMin[pivot-1]; tempDp = dp[pivot-1]; if(t.substring(tempDp.length(), index + 1).startsWith(word) == false) continue; depth++; //dpMin[index]보다 크거나 같으면 의미 없으니 멈춤 if(depth>=dpMin[index]) continue; //만약 tempDp를 제외한 나머지가 word랑 같으면, tempDp if(t.substring(tempDp.length(),index+1).equals(word)==true){ tempDp = tempDp + word; break; } //아니라면 그 다음것도 찾아봄 for(int count=0;count < strs.length;count++){ String innerWord = strs[count]; if(t.substring(tempDp.length(),index+1).startsWith(innerWord) == false) continue; //depth값이 최소값보다 크거나 같으면 의미 없으니 멈춤 if(depth+1 >= dpMin[index]) break; depth++; tempDp = tempDp+word; //만약에 tempDp와 text(0~index+1)이 같으면 찾았으니 멈춤 if(t.substring(0,index+1).equals(tempDp)==true){ break; } } } //만약 지금 찾은 depth가 최솟값보다 낮으면 적용시키고 멈춤 System.out.println("index: " + index+ " pivot: "+ pivot+" depth: "+depth+" tempDp: "+tempDp); if(depth<dpMin[index]&&tempDp.equals(t.substring(0,index+1))){ dpMin[index] = depth; dp[index] = tempDp; break; } //아니라면 pivot을 감소하고 돌림 pivot--; } } System.out.printf("======dp======"); for(String p : dp){ System.out.println(p); } //다 찾아봤는데 dp끝 값이 text와 같지 않으면 -1 return(dp[t.length()-1].equals(t))? dpMin[t.length()-1]: -1; } } | cs |
C++풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <string> #include <vector> #include <set> #include <algorithm> using namespace std; int pretest7(vector<string> strs, string t) { //vector에 있는 단어 조각들을 빠르게 탐색 set<string> str_set(strs.begin(), strs.end()); //무한대를 나타내는INF 변수 const int INF = 987654321; //dp배열 선언 int dp[20002]; //문자열의 길이를 나타내는 len int len = t.length(); for(int i=0;i<len; i++) //dp배열 무한대로 초기화 dp[i] = INF; //dp의 문자열의 마지막 //문자열의 길이가 len이므로 문자열의 마지막 index는 len-1이 됩니다. dp[len] = 0; //문자열을 뒷쪽 방향부터 순서대로 순회한다. for(int i=len-1;i>=0;i--){ //i가 현재 가르키는 index부터 한개에서 5개를 이어붙힌 문자열을 이어붙히기 위해 변수 하나 선언 string tmp =""; //길이가 1~5인 문자열을 저장하기 위한 for문 이때 i+j가 가리키는 위치와 문자열 전체 위치가 문자열 길이보다 크면 안됨 for(int j=0; i+j<len && j<5;j++){ tmp += t[i+j]; //for문돌떄마다 이어붙힌 문자열 더할 수 있다. //현재 만들어진 문자열이 주어진 단어 조각에 있는지 확인하기 위함 //포함되어 있다면 i+j+1번 위치부터 주어진 단어조각을 이용해서 만들수 있는지 확인해야합니다. 무한대가 아니라면 if(str_set.find(tmp) != str_set.end() && dp[i + j + 1] != INF) //dp[i]값 갱신 dp[i] = min(dp[i], dp[i+j+1]+1); } } //dp[0]가 무한대면 주어진 단어들로 만들수 없어서 -1 출력 아니라면 dp[0] 자체 출력 가능 if(dp[0] = INF) return -1; return dp[0]; } | cs |
'완전탐색(DP,재귀함수) ' 카테고리의 다른 글
| 프로그래머스 모의테스트 6 > 스티커 모으기 > DP문제의 기본기 (0) | 2019.02.28 |
|---|---|
| 정올 함수 3 형성평가 6 > ntechservice문제와 비슷 자가진단6과비슷 각자리수 곱하는거 다시 하기 (0) | 2019.02.18 |
| 정올 함수3 형성평가5 > level+1인 이유가 이해 안감 (0) | 2019.02.18 |
| 정올 함수3 형성평가4 > timelimited60 (0) | 2019.02.18 |
| 정올 함수3 형성평가3 > 이해x 주사위 문제 (0) | 2019.02.18 |