고민의 흔적

step 2 - 4. 정수 삼각형

내가 떠올린 풀이 해설

1. DP 삼각형의 가장 왼쪽의 값 (DP[i][0])은 한 줄 위의 가장 왼쪽 값(DP[i - 1][0])에 현재 값(triangle[i][0])을 더한 값이 된다.
   DP[i][0] = DP[i-1][0] + triangle[i][0]이 됩니다.
2. 삼각형의 가장 오른쪽의 값 (DP[i][i])은 한 줄 위의 가장 오른쪽 값(DP[i-1][i-1])에 현재 값(triangle[i][i])을 더한 값이 된다.
   DP[i][i] = DP[i-1][i-1] + triangle[i][i]이 됩니다.
3. 삼각형의 1번과 2번을 제외한 나머지는 한줄 위의 오른쪽 값과 왼쪽 값 중 큰 값에 현재 값을 더한 값이 된다.
   DP[i][i] = Max(DP[i - 1][j - 1], DP[i - 1][j]) + triangle[i][j]가 됩니다.
4. DP 배열에서 max 값을 출력하기 위해 answer = Math.max(answer, dp[i][j])을 해준다.

정확한 풀이

public class step2_4 {

	public static void main(String[] args) {
		int[][] tri = {{7},
				{3, 8},
				{8, 1, 0},
				{2, 7, 4, 4},
				{4, 5, 2, 6, 5}};
		int [][]dp = new int[tri.length][tri[tri.length - 1].length];
		int answer = 0;
		int max = 0;
		dp[0][0] = tri[0][0];
		for(int i = 1; i < tri.length; i++) {
			dp[i][0] = dp[i - 1][0] + tri[i][0];
			dp[i][i] = dp[i - 1][i - 1] + tri[i][i];
			for(int j = 1; j <= i - 1; j++) {
				dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + tri[i][j];
				answer = Math.max(answer, dp[i][j]);
			}
		}
		System.out.println(answer);
	}
}

오늘의 회고

오늘은 DP문제와 프로그래머스 위장 문제와 유사한 문제를 백준에서 찾아서 HashMap 문제를 풀었습니다. 점화식은 도출을 해냈지만 DP 배열을 만들 생각을 하지 못하고 triangle 배열에서 점화식을 처리해주려고 했는데 생각처럼 되지 않았습니다. HashMap문제는 거의 동일해서 어렵지 않게 해결할 수 있었습니다. 알고리즘 고수가 되고 싶습니다.ㅠㅠ

step 2 - 3. 올바른 괄호의 개수

내가 떠올린 풀이 해설

괄호를 보고 stack을 이용해서 풀려고 했는데 괄호 문자를 입력으로 주지 않아 DFS의 성질을 이용해 풀었다. 올바른 괄호의 짝 중에, '('로 시작했으면 ')'로 끝나는 성질을 이용해 ')'의 개수가 '('보다 많으면 올바르지 않은 식으로 간주하고, 이 모든 경우의 수를 dfs로 찾았다.

https://tosuccess.tistory.com/173

정확한 풀이

import java.util.*;
public class step2_3 {
	static int answer;
	public static void main(String[] args) {
		int n = 2;
		answer = 0;
		DFS(0, 0, n);
		System.out.println(answer);
	}
	private static void DFS(int left, int right, int n) {
		if(left < right) {
			return;
		}
		if(left == n && right == n) {
			answer++;
			return;
		}
		if(left > n || right > n) {
			return;
		}
		DFS(left + 1, right, n);
		DFS(left, right + 1, n);
	}
}

오늘의 회고

오늘은 프로그래머스 3주 차 문제를 풀었습니다. DFS를 이용해서 푸는 문제였다. DFS 문제라고 떠올리기는 했지만 문제를 해결하는 방법의 아이디어가 떠오르지 않았다... 좀 더 넓은 방식으로 문제를 해결해야 되는데 어떻게 공부해야 될지 잘 모르겠다.ㅠㅠ

step 2 - 2. 게임 맵 최단거리

내가 떠올린 풀이 해설

DFS로 풀어도 답이 나오는 문제인데 저는 BFS로 풀었습니다. dx, dy로 상하좌우를 탐색할 배열을 만들어 준다. 또한 visit 배열을 만들어준다. visit배열은 BFS를 탐색하면서 거리가 1씩 늘어날수록 이동한 거리를 담아 줄 배열이다. 만약 answer가 0이면 -1, 아니면 answer를 리턴해준다. BFS 메서드에서는 BFS를 이용할 Queue를 생성하고 시작점인 0,0을 배열로 Queue에 add 해준다. Queue가 빌 때까지 반복한다. for문으로 상하좌우를 탐색하면서 만약 nx, ny가 0보다 같거나 크고, nx, ny가 map길이보다 작아야 하고, maps배열의 nx, ny위치가 1이고, visit배열의 nx, ny가 0이면 visit [nx][ny]에 visit [x][y] + 1 값을 넣어준다. 그리고 Queue에 nx, ny를 add 해준다.

정확한 풀이

import java.util.*;
public class step2_2 {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int answer;
    static int[][] visit;
	public static void main(String[] args) {
		int [][]maps = {{1, 0, 1, 1, 1},
				{1, 0, 1, 0, 1},
				{1, 0, 1, 1, 1},
				{1, 1, 1, 0, 1,},
				{0, 0, 0, 0, 1}};
		answer = 0;
		int [][] visit = new int[maps.length][maps[0].length];
		visit[0][0] = 1;
		BFS(maps, visit);  
		answer = visit[maps.length - 1][maps[0].length - 1];
		if(answer == 0) {
			System.out.println(-1);
		}
		System.out.println(answer);
	}
	private static void BFS(int[][] maps, int[][] visit) {
		Queue<int[]> que = new LinkedList<>();
		que.add(new int[] {0, 0});
		while(!que.isEmpty()) {
			int[] now = que.poll();
			int x = now[0];
			int y = now[1];
			for(int i = 0; i < 4; i++) {
				int nx = dx[i] + x;
				int ny = dy[i] + y;
				if(nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length && maps[nx][ny] == 1 && visit[nx][ny] == 0) {
					visit[nx][ny] = visit[x][y] + 1;
					que.add(new int[] {nx, ny});
				}
			}
		}
    }
}

오늘의 회고

요즘 계속 알고리즘 문제를 1문제밖에 풀지 못하네요. 알고리즘 고수가 되는 그날까지 분발하겠습니다. 

step 2 - 1. 위장

내가 떠올린 풀이 해설

문제를 읽다 보면 hashMap으로 풀어야 하는 단서가 되는 게 있다. 제한 사항에 같은 이름을 가진 의상은 존재하지 않습니다를 보고 떠올릴 수 있을 것 같다. 저는 hashMap의 key에 의상의 이름을 담고, value에 종류를 담아서 풀려고 했다. 하지만 key에 종류를 담고 value에 숫자를 담는다. 만약 담으려는 키가 존재하면 key의 value값을 리턴하고 만약 존재하지 않으면 default값을 반환하는 getOrDefault를 이용했다. 같은 종류의 의상은 1개밖에 입지 못하므로 경우의 수를 이용해서 풀었다. 

정확한 풀이

import java.util.*;

public class step2_1 {

	public static void main(String[] args) {
		String[][] clothes = {{"yellowhat", "headgear"}, 
								{"blue", "eyewear"}, 
								{"green_turban", "headgear"}};
		HashMap<String, Integer> map = new HashMap<>();
		int answer = 1;
		for(int i = 0; i < clothes.length; i++) {
			map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0) + 1);
        }
		Set<String> keySet = map.keySet();
		for(String key : keySet) {
			answer *= map.get(key) + 1;
		}
		System.out.println(answer - 1);
	}
}

오늘의 회고

문제를 풀면 풀수록 부족하다는 생각이 드네요. 언제쯤 쉽게 문제를 해결할 수 있을까요...? 오늘은 맥북 충전 단자가 고장이나서 서비스 센터에 갔다 오느라 정신없었던 하루였습니다. 공부도 많이 못했습니다. 남은 시간이라도 열심히 공부하겠습니다.

step 1 - 4. 숫자 게임

내가 떠올린 풀이 해설

두 배열을 Arrays.sort를 이용해서 정렬을 하고 aIndex가 a 길이랑 같지 않고 bIndex가 B길이보다 같지 않게 반복분을 실행한다. 반복문 안에서 만약 A배열의 aIndex위치에 있는 수와 B배열의 bIndex위치에 있는 수를 비교했을 때 B가 더 크면 answer의 수를 늘려주고 aIndex의 수를 하나 늘려준다. if문 조건을 만족하지 않으면 bIndex의 수를 하나 늘려준다.

정확한 풀이

import java.util.*;
class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        
        int aIndex = 0;
        int bIndex = 0;
        
        while(aIndex != A.length && bIndex != B.length) {
            if(A[aIndex] < B[bIndex]) {
                answer++;
                aIndex++;
            }
           bIndex++;
        }
        return answer;
    }
}

오늘의 회고

문제는 금요일에 풀었지만 블로그는 오늘 작성했습니다. 금요일에 친구들 중에 처음으로 결혼을 하는 친구가 있는데 신혼집에 들어가서 가구 조립이나 청소를 도와주었습니다. 행복하게 오래오래 살았으면 좋겠습니다. 이번 문제는 프로그래머스 1주 차 마지막 문제로 어렵지는 않은 문제였습니다. 프로그래머스에서 힌트를 주었는데 힌트에 맞춰서 코드를 작성하려다 보니 꼬여서 힌트 코드를 사용 안 하고 문제를 풀었습니다.

step 1 - 2. 가장 큰 수

내가 떠올린 풀이 해설

처음에 문제를 보았을 때 투 포인터로 전체를 탐색하면서 문자를 연결해서 숫자 형식으로 바꿔서 max값을 구해서 다시 String으로 바꿔서 출력을 하려고 했는데 실패했다. int형 배열을 String 배열로 바꾸고 Array.sort를 이용해서 정렬을 한다. 만약 전부 0이면 0000으로 나와서 0으로 된 배열만 예외 처리를 해준다.

정확한 풀이

import java.util.*;
import java.io.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] str = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++) {
            str[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return (b + a).compareTo(a + b);
            }
        });
        if(str[0].equals("0")) {
            return "0";
        }
        else {
            for(int i = 0; i < str.length; i++) {
                answer += str[i];
            }
        }
        return answer;
    }
}

step 1 - 3. 예산

내가 떠올린 풀이

이분 탐색으로 해결하면 되는 문제였다. 근데 이분탐색을 푸는데 갑자기 머릿속이 꼬여서 엄청 헤매면서 풀었다. 정답도 100점 만점에 90점이다.

정확한 풀이

import java.util.*;
class Solution {
    public int solution(int[] budgets, int M) {
       int answer = 0;
        int sum = 0;
        Arrays.sort(budgets);
        for(int i = 0; i < budgets.length; i++) {
            sum += budgets[i];
        }
        int max = 0;
        if(sum >= M) {
        	int start = budgets[0];
            int end = budgets[budgets.length - 1];
            sum = 0;
            while(start <= end) {
                int midv = (start + end) / 2;
                sum = 0;
               //midv = 119 124 127
                for(int i = 0; i < budgets.length; i++) {
                    if(midv > budgets[i]) {
                        sum += budgets[i];
                    }
                    else {
                        sum += midv;
                    }
                }
                if(sum > M) {
                    end = midv - 1;  //end 129 
                }
                else {
                	start = midv + 1;
                	answer = midv;
                }  
            }
        }
        else {
            answer = budgets[budgets.length - 1];
        }
        return answer;
    }
}

오늘의 회고

오늘 문제를 풀면서 너무 헤맷습니다. 공부를 좀 더 열심히 해야 될 것 같습니다. 자신감이 떨어진 하루입니다.ㅠㅠ 좀 더 분발해서 공부하겠습니다. 중간고사도 있는데 중간고사 때 많이 못 풀 것 같은 느낌이.... 열심히 하겠습니다.

기지국 설치

입출력 예

내가 떠올린 풀이 해설

while문으로 현재 있는 위치부터 n보다 작거나 같을 때까지 반복한다. while문 안에서 현재 위치가 모든 기지국의 범위를 넘어선 경우와(만약 idx가 기지국 위치 배열의 길이보다 작거나 같고) 또한 현재 위치가 기지국의 범위보다 작은 경우일 때(현재 위치가 기지국 위치와 전파를 뺐을 때 보다 작으면) 기지국을 설치해준다. 그리고 현재 위치를 기지국의 전파 곱하기 2 더하기 1을 하고 현재 위치를 더해준다. 이는 설치한 기지국의 위치에서 벗어난 곳으로 위치해주기 위해서이다. 또한 위의 if문에 만족을 못하면 현재 위치가 모든 기지국의 범위보다 작으며 특정 기지국에 범위 내에 있는 경우이므로 현재 위치를 기지국의 파장의 범위 밖으로 옮기고 기지국의 위치도 옮겨준다.

정확한 풀이

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int now = 1;
        int idx = 0;
        while(now <= n) {
            if(idx >= stations.length || now < stations[idx] - w) {
                answer++;
                now = (w * 2 + 1) + now;
            }
            else {
                now = stations[idx] + w + 1;
                idx++;
                
            }
        }
        return answer;
    }
    
}

오늘의 회고

프로그래머스로 처음 풀어본 문제였습니다. 커뮤러닝을 통해 예전에 배운 개념을 복습하는 식으로 진행이 될 것 같아 만족합니다. 또한 다른 사람들의 코드를 리뷰해주고 제 코드도 리뷰받는 방식으로 진행이 되어서 코딩 테스트뿐만 아니라 코드를 짜는 실력도 같이 성장할 것 같습니다. 열심히 공부하겠습니다. 오늘 문제 풀어보니까 아직 많이 부족한데 이 과정을 통해 한층 더 성장하는 제가 되었으면 좋겠습니다.