개발자를 향해...
프로그래머스 - 타켓 넘버 (java) 본문
728x90
반응형
https://programmers.co.kr/learn/courses/30/lessons/43165
코딩테스트 연습 - 타겟 넘버
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수
programmers.co.kr
처음에 bfs인지 몰랐다. 그냥 첫번째 수부터 쭈르륵 + -를 모든 경우에 대해 연산하면 되는게 아닌가 했는데 문항 분류가 bfs로 되어있어서 신기했다. 내가 푼 방식은 BFS로 풀었고 코드는 다음과 같다.
class Solution {
public int solution(int[] numbers, int target) {
int answer = 0;
int[][] tree = new int [numbers.length][((int)Math.pow(2,numbers.length))];
tree[0][0] = -numbers[0];
tree[0][1] = numbers[0];
// System.out.println(tree[0].length);
for ( int i = 1; i < numbers.length; i++ ){
int c = 0;
for(int j=0; j<Math.pow(2,i); j++){
int parent = tree[i-1][j];
tree[i][c] = parent - numbers[i];
c++;
tree[i][c] = parent + numbers[i];
c++;
}
}
// for(int i = 0; i<tree.length; i++){
// for(int j=0; j<tree[i].length; j++){
// System.out.print(tree[i][j]+" ");
// }
// System.out.println("");
// }
for(int i :tree[numbers.length-1]){
if(i==target) answer++;
}
return answer;
}
}
DFS의 코드는 아래 블로그를 참고하여 공부했다.
프로그래머스 - 타겟 넘버 (DFS, BFS) Python
문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. `1+1+1+1+1
velog.io
DFS 함수를 선언하고 재귀 호출을 통해 깊이 내려간다. 여기서 내가 햇갈렸던 부분은 어떻게 + -를 구분하느냐인데
먼저 그냥 수 그러니깐 +에대해 재귀호출을 해준 후 각각에 대해 -를 차례대로 붙여서 다시 재귀호출을 해주면 + -를 모두 할 수 있는 방법이다.
느낀점
내가 dfs를 잘 이해하지 못한것 같다고 생각했다. dfs 유형을 더 연습해야겠다.
반응형
'코테 공부 > 프로그래머스master' 카테고리의 다른 글
프로그래머스 -타겟 넘버 (java) (0) | 2022.04.10 |
---|---|
프로그래머스 - 네트워크 (java) (0) | 2022.04.10 |
프로그래머스 - k번째 수 (java) (0) | 2022.04.08 |