DP를 사용하여 Bottom Up으로 풀이했고, 문제 예시에서의 banana로 예를 들어보자.
b
ba
ban
bana
banan
banana
dp배열의 각 idx는 위의 값들을 만족하는 최소값들로 채워나갔다.
strs의 원소에서, t의 인덱스마다 같은 substring이 있는지 확인하였고, 같다면 dp배열에 입력해나갔다.
//strs에서 선택한 문자열과 t의 부분이 일치하는지 확인
if(word.equals(t.substring(i - wordLength, i))) {
//word하나로 현재까지의 문자를 만들 수 있을 경우ⓐ
if(i - wordLength == 0) {
dp[i] = 1;
continue;
}
//이전에 만든 문자열이 있을 경우
if(dp[i - wordLength] > 0) {
//dp[i]가 0일 경우, 이전 위치까지의 최소단어개수에서 + 1처리를,
dp[i] = dp[i] == 0 ? dp[i - wordLength] + 1
//dp[i]가 이미 채워져있다면(위의 ⓐ경우를 만족했던 경우. ex)ba, a)
//둘 중 비교하여 작은 경우의 수를 입력
: Math.min(dp[i], dp[i - wordLength] + 1);
}
}
import java.util.*;
class Solution {
public int solution(String[] strs, String t) {
int tLength = t.length();
int strsLength = strs.length;
int[] dp = new int[tLength + 1];
for(int i = 1; i < tLength + 1; i ++) {
for(int j = 0; j < strsLength; j ++) {
String word = strs[j];
int wordLength = word.length();
if(i - wordLength < 0) continue;
if(word.equals(t.substring(i - wordLength, i))) {
if(i - wordLength == 0) {
dp[i] = 1;
continue;
}
if(dp[i - wordLength] > 0) {
dp[i] = dp[i] == 0 ? dp[i - wordLength] + 1 : Math.min(dp[i], dp[i - wordLength] + 1);
}
}
}
}
int answer = dp[tLength];
if (answer == 0) return -1;
return answer;
}
public static void main(String[] args) {
Solution sol = new Solution();
sol.solution(new String[]{"ba", "na", "n", "a"}, "banana");
}
}
2. list 사이즈가 짝수일 경우만 고려해주었다. 홀수일 경우는 x*x=sum이 되는 x의 값이 정답이라고 생각함.
총 카펫 크기에 대한 약수를 구했기 때문에, 해당 약수의 곱이 yellow가 일치하는지 꼭 확인해주어야했다.
예를들어 brown = 18 yellow = 6일 경우 검증해주지 않으면 8,3의 정답이 6,4가 나와버린다.
if(list.size()%2==0) {
int x = list.size()/2;
int y = list.size()/2-1;
while((list.get(x)-2)*(list.get(y)-2)!=yellow) {
y--;
x++;
}
answer[0] = list.get(x);
answer[1] = list.get(y);
}
else {
answer[0] = list.get(list.size()/2);
answer[1] = list.get(list.size()/2);
}
전체 코드
import java.util.ArrayList;
import java.util.List;
class Solution {
static List<Integer> list = new ArrayList<>();
public int[] solution(int brown, int yellow) {
int[] answer = new int[2];
int sum = brown+yellow;
div(sum);
if(list.size()%2==0) {
int x = list.size()/2;
int y = list.size()/2-1;
while((list.get(x)-2)*(list.get(y)-2)!=yellow) {
y--;
x++;
}
answer[0] = list.get(x);
answer[1] = list.get(y);
}
else {
answer[0] = list.get(list.size()/2);
answer[1] = list.get(list.size()/2);
}
return answer;
}
public void div(int sum) {
for(int i=1; i<=sum/2; i++) {
if(sum%i==0) {
list.add(i);
}
}
list.add(sum);
}
}
다른 풀이
프로그래머스 내의 신재권님의 풀이가 비슷한 접근방법이면서도 엄청 간단하게 풀어진 것 같아서 리뷰해보려 한다.
class Solution {
public static int[] solution(int brown, int yellow) {
int sum = brown + yellow;
return find(yellow, sum);
}
private static int[] find(int yellow, int sum) {
int y = 0, x = 0;
for (int i = 1; i <= yellow; i++) {
if (yellow % i == 0) {
y = Math.min(i, yellow / i);
x = Math.max(i, yellow / i);
if ((y + 2) * (x + 2) == sum) {
break;
}
}
}
return new int[] {x + 2, y + 2};
}
}
같은 약수를 찾는 완전탐색이지만,
yellow자체를 처음부터 나눠가면서 x+2,y+2의 곱이 전체 카펫의 크기와 같을 때 리턴해주었다.
내가 x-2, y-2로 yellow 자체의 크기와 비교한 것과 같은 맥락으로
x+2, y+2를 했을 경우 sum의 x와 y의 길이일 것이기 때문에, 곱했을 경우 전체 카펫의 크기가 된다.
