1. 타겟 넘버 - 프로그래머스
내 코드
dfs 재귀로 구현했다.
index가 순서대로이기 때문에 1씩 증가해서 재귀를 하고, sum은 플러스와 마이너스 두 경우 다 계산하도록 해서
numbers 배열의 숫자를 다 사용했을 때 && sum이 target에 도달했을 때 이렇게 두 경우에 count를 증가하고 종료하도록 구현했다.
어려웠던 점: 종료 조건 설정을 잘 못하는 것 같다.
class Solution {
static int count = 0;
public int solution(int[] numbers, int target) {
dfs(numbers,0,0,target);
return count;
}
public static void dfs(int[] numbers, int index, int sum, int target){
// 종료 조건 설정
if (index == numbers.length){
if(sum == target){
count++;
}
return;
}
dfs(numbers, index+1, sum + numbers[index], target);
dfs(numbers, index+1, sum - numbers[index], target);
}
}더 나은 방법
1. return 방식 dfs를 사용하자 -> 항상 static 변수를 사용했었는데 이 문제에서는 return 방식으로 해야 전역 변수 count에 의존하지 않을 수 있음
return dfs(numbers, index+1, sum + numbers[index], target)
+ dfs(numbers, index+1, sum - numbers[index], target);-
BFS로 하는 방법 - 더 복잡한데 나은 방법은 아님
큐 사용해서 현재 인덱스, 현재합 상태를 큐에 넣는 방식으로 -
잘 쓴 풀이 분석하기
class Solution {
public int solution(int[] numbers, int target) {
int answer = 0;
answer = dfs(numbers, 0, 0, target);
return answer;
}
int dfs(int[] numbers, int n, int sum, int target) {
if(n == numbers.length) {
if(sum == target) {
return 1;
}
return 0;
}
return dfs(numbers, n + 1, sum + numbers[n], target) + dfs(numbers, n + 1, sum - numbers[n], target);
}
}- 전역으로 변수를 두지 않음
- return 방식으로 dfs 돌림 -> 내 코드는 백트래킹 방식인데, 상태 변경하고 다시 되돌리는 방식으로 하기 때문에 이 문제에서는 return dfs 방식이 더 적합. 개수만 구하기 때문에
2. 촌수 계산 - 백준
내 코드
import java.util.*;
import java.io.*;
class Main {
static boolean[] visited;
static List<Integer>[] graph;
static int answer = -1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int target1 = Integer.parseInt(st.nextToken()) - 1;
int target2 = Integer.parseInt(st.nextToken()) - 1;
int count = Integer.parseInt(br.readLine());
// 사람 인접리스트로 만들기
graph = new ArrayList[n];
for(int i = 0; i < n; i++){
graph[i] = new ArrayList<>();
}
for(int i = 0; i < count; i++){
StringTokenizer stz = new StringTokenizer(br.readLine());
int p1 = Integer.parseInt(stz.nextToken());
int p2 = Integer.parseInt(stz.nextToken());
graph[p1-1].add(p2-1);
graph[p2-1].add(p1-1);
}
visited = new boolean[n];
int depth = 0;
dfs(target1,target2,depth);
System.out.println(answer);
}
public static void dfs(int node, int target, int depth){
if (node == target){
answer = depth;
return;
}
visited[node] = true;
for(int nextNode : graph[node]){
if(!visited[nextNode]){
dfs(nextNode,target,depth+1);
}
}
}
}
어려웠던 점: 인접리스트로 풀어본적이 처음이라서 어떻게 풀어야할지 좀 어려웠다. 촌수를 depth를 넘겨주는 방식으로 해서 풀었다.
[사람] -> [사람1,사람2,사람3] 3. 게임 맵 최단거리
import java.util.*;
class Solution {
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,1,-1};
static int n,m;
public int solution(int[][] maps) {
n = maps.length;
m = maps[0].length;
boolean [][] visited = new boolean[n][m];
int answer = bfs(0,0,visited,maps);
return answer;
}
public int bfs(int x, int y,boolean[][] visited,int[][] maps) {
Queue<int[]> q = new LinkedList<>();
// x, y, 거리 저장
q.add(new int[]{x,y,1});
// 시작 지점은 방문처리
visited[x][y] = true;
while(!q.isEmpty()){
// 현재 상태 처리
int [] cur = q.poll();
int curx = cur[0];
int cury = cur[1];
int dist = cur[2];
// 범위 검사 조건: 도착했을 시
if(curx == n - 1 && cury == m - 1) {
return dist;
}
// 4방향으로 탐색
for(int i = 0; i < 4;i++){
int nx = curx + dx[i];
int ny = cury + dy[i];
if (nx >= 0 && ny>=0 && nx<n && ny<m && maps[nx][ny] == 1 && !visited[nx][ny]){
// 방문 처리
visited[nx][ny] = true;
// 상태 전이
q.add(new int[]{nx,ny,dist+1});
}
}
}
return -1;
}
}어려웠던 점: 방향으로 나누어져 있을 때 4방향 탐색이랑 이런 식으로 배열 만들어서 현재 좌표 계산하는 식으로 하는 걸 잘 몰랐어서 어려웠다.
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,1,-1};4.반복수열 - 백준
import java.util.*;
import java.io.*;
class Main {
static List<Integer> numbers = new ArrayList<>();
static int result = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
numbers.add(a);
int next = toNextNum(a,p);
dfs(next,p);
System.out.println(result);
}
public static void dfs(int next, int p) {
if(numbers.contains(next)){
result = numbers.indexOf(next);
return;
}
numbers.add(next);
dfs(toNextNum(next,p),p);
}
public static int toNextNum(int a, int p){
String[] nums = String.valueOf(a).split("");
int sum = 0;
for(String next : nums){
int thisN = 1;
for(int i = 0; i < p; i++){
thisN*=Integer.parseInt(next);
}
sum+=thisN;
}
return sum;
}
}푼 방법:
- 리스트에서 수열 숫자 저장하고 리스트에 있는것들 중에 나오면 반복 시작이므로 종료
- toNextNum 메서드에서 다음 수열 숫자 계산
개선 방법:
1. contains, indexOf은 각각 O(n)이므로 최악의 경우 O(n^2)이다 ..
- 해결: HashMap을 사용해서 수열 숫자, 인덱스 이렇게 저장하면 O(n)이다.
public static void dfs(int current, int p) {
int next = toNextNum(current, p);
if (map.containsKey(next)) {
result = map.get(next);
return;
}
map.put(next, map.size());
dfs(next, p);
}- 문제: split으로 하고있는데 문자열처리 말고 계산으로 처리. 나머지연산자 사용하면 된다. 이건 그냥 순수 수학 문제 느낌
public static int toNextNum(int a, int p){
int sum = 0;
while (a > 0) {
int digit = a % 10;
int pow = 1;
for (int i = 0; i < p; i++) {
pow *= digit;
}
sum += pow;
a /= 10;
}
return sum;
}
백엔드 개발자 지망 대학생