고민의 흔적

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 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;
    }
    
}

오늘의 회고

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