https://programmers.co.kr/learn/courses/30/lessons/42895
코딩테스트 연습 - N으로 표현
programmers.co.kr
해당 문제는 주어진 숫자를 최소한 으로 반복하여
원하는 숫자를 만들어 내는 문제이다.
처음 문제를 보고 생각했을 때
문제유형을 보고
DP 접근 방식으로 풀이를 생각했다.
~~를 하기위한 최소한의 방법 같은 문제를 보았을 때 DP를 떠올리자
( 하지만 난 생각이 나질 않아유형을 봐서 알아냈음... 경험치가 부족한거 같다.)
DP 의 인덱스 접근을 아래와 같이 정이해봄
DP[ i ] => 주어진 숫자를 i 번 사용하여 만들수 있는 숫자들
DP의 값이 여러 숫자가 가능하기 때문에 List<Set<Integer>> 형태로 선언함.
public int solution(int N, int number) {
int answer = 0;
List<Set<Integer>> countList = new ArrayList<>();
for(int i=0; i<=9; i++){
countList.add(new HashSet<Integer>());
}
countList.get(1).add(N);
//...중략
여기서 이제 차근차근 i = 1 일때 부터 생각.
N 1개로 만들수 있는 숫자는 N 1개 뿐
인덱스 1에 N 한개만 넣어준다.
이제 다음 i 부터는 아래와 같이 계산 할 수 있다.
( j 를 1~i-1 까지 증가시키며 )
i 개로 만들수 있는 수 -> j 개로 만들수 있는 수 ( +, -, *, /) i-j개로 만들수 있는수
먼저 i=2를 예로 들면
N + N , N - N , N * N, N / N 이렇게 4가지가 가능하다.
i=3 은 j = 1 로만들수 있는 수 N 과 i-j=2로 만들수 있는 수 N + N , N - N , N * N, N / N를
또 다시 4가지 사칙연산으로 계산해 준다.
여기서 Set 자료구조를 이용한 이유는
j=1, i-j=2 일때 덧셈 곱셈연산과 j=2, i-j=1 의 덧셈 곱셈 연산이 같은 수가 나오기 때문에
Set 자료구조를 이용하여 중복을 제거해 준다.
for(int i=2; i<=9; i++){
Set<Integer> set = countList.get(i);
for(int j=1; j<=i; j++){
Set<Integer> preSet = countList.get(j);
Set<Integer> postSet = countList.get(i - j);
for(int preNum : preSet){
for(int postNum : postSet){
set.add(preNum + postNum);
set.add(preNum - postNum);
set.add(preNum * postNum);
if(preNum != 0 && postNum != 0)
set.add(preNum / postNum);
}
}
}
// .. 중략
여기다 추가로 N을 아무 연산없이 i 번 반복한 경우도 숫자로 만들수 있으므로
이 숫자도 추가해 준다.
String str = String.valueOf(N);
StringBuilder ss = new StringBuilder();
for(int j=0; j<i; j++){
ss.append(str);
}
set.add(Integer.parseInt(ss.toString()));
}
( 문자 계산시 += 연산보다 StringBuilder를 사용할 때 더 빠르게 작업이 가능하다.)
(이 문제에서는 += 연산을 사용해도 시간복잡도가 문제가 되지 않지만 습관을 들이기 위해 사용함)
마지막으로 리스트에서 지금 만드려는 숫자가 있는 Set 의 순서를 가져온다.
없으면 문제에서 주어진 것 처럼 -1 을 반환!
for(Set<Integer> set : countList){
if(set.contains(number)){
return countList.indexOf(set);
}
}
return -1;
리스트의 인덱스의 의미 -> N을 사용한 횟수.
즉 가장 작은수 부터 순회하면서 가장 첫번째로 원하는 Number가 나온 인덱스를 반환하면
N을 최소로 사용하여 Number를 만든 N의 갯수가 반환된다.
댓글