요르딩딩

이번문제는 범위에 대한 구분만 잘 한다면, 풀 수 있는 문제이다. 보다 쉬운 방법이 있지만, 나는 아래와 같은 방식으로 구현하였다. 여기서 중요한 점은 도착점이 가장 작은거 부터 확인을 해야한다는 것이다. import java.util.*; class Solution { public int solution(int[][] routes) { int answer = 0; Arrays.sort(routes, (a,b)-> Integer.compare(a[1], b[1])); boolean[] visited = new boolean[routes.length]; // 갯수만큼 생성 for (int i = 0; i < routes.length; i++) { // 범위 전체 반복 if (visited[i]) { // ..

이번문제는 생각보다 한번에 해결책이 떠오르지 않아 조금 오래걸렸던 문제입니다. 딱히 효율적인 방안이 떠오르지 않고, 경우의 수가 6개 밖에 되지 않아 전부 다 계산하는 방법을 선택했습니다. [설명] 해당 수식을 숫자와 연산자를 각각 리스트에 담는다. 6가지 경우 수에 따라 연산자 우선순위대로 계산을 진행한다. 이때, 연산은 List에서 직접 수행한다. 연산자가 나오면 앞뒤로 계산을 수행 후, 연산에 관여된 3개의 데이터를 삭제 한다. 이때, 리스트삭제로 인해 index가 변경되니, 주의하자. -> (i-1)위치 3번삭제 후 -> i--적용 한번의 경우의 수가 끝나면, 절댓값 적용 후 다른 경우의 값보다 크면 업데이트한다. 주의, 결과값을 long형으로 타입을 변경해 주어야한다. import java.ut..

이번문제는 생각보다 애를 먹은 문제입니다. 처음에는 DPS로 최단경로를 구하였으나, 효율성 문제 실패로 인해 DP로 다시 풀어보았습니다. 물론 DP로 풀때는 다른 분들의 로직을 참고하였습니다. 이번문제는 m,n의 값이 반대인 경우라 조금 헷갈리는 부분이 있었습니다. 하지만 한번 이해하면 그다지 어려운 문제는 아니라 생각합니다. 2차원 배열에서의 해당 위치까지오는 최단 경로 구하는 문제의 핵심은 해당 위치까지 오는 최단 경로의 수 = 그 전(상/좌) 경로의 수의 합 이라는 것을 생각하면 됩니다. 또한 효율성을 위해 1,000,000,007을 매번 계산하여 구하는 것 보다 해당 값을 넘는 경우만 나머지를 구하여 적용하면 보다 더 효율적인 코드가 됩니다. import java.util.*; class Solu..

이번문제는 Array.sort를 사용하면 충분히 빠르게 풀 수 있는 문제입니다. 곱의 값을 가장 작게 만들기 위해서는 가장 작은값 X 가장 큰값을 해주어야합니다. 그러기위해서, A배열을 오름차순으로 B배열을 내림차순으로 정렬하여, 서로 곱해주면 됩니다. Arrays.sort의 내림차순정렬을 위해 Collections.reverseOrder()를 사용하려면 int형이 아닌 integer형으로 형변환을 해주어야합니다. Arrays.sort(T[] a, Comparator c) method를 제공해 주는데 왜 안되면, Arrays.sort(T[] a, Comparator c)에서 사용되는 T는 Generic Class로 어떠한 객체도 허용하게 해주었지만, int는 객체가 아닌 primitive type이었던 ..

이번문제는 처음에 생각보다 접근 방식은 좋았다고 생각한다. 다만 오랜만에 BFS 관련 문제를 풀다보니, 헷갈리는 부분에 있어서 오래걸렸다. 이 문제를 BFS라고 판단한 이유는 최단경로를 구하는것이기 때문이다. 우선, 각각의 글자를 노드라고 생각하고, 접근 가능한(한글자 차이나는 값)노드를 연결시켜, 연결리스트 형태를 만들었다. List list = new ArrayList(); list.get(0) = [1,3] list.get(1) = [0,2,3] list.get(2) = [1,4,5] list.get(3) = [0,1,4] list.get(4) = [2,3,5] list.get(5) = [2,4] 추가로, 각각의 노드의 방문상태를 나타내는 visited[], 각각의 노드의 거리를 나타내는 resul..

이번문제는 dfs/bfs로 풀 수 있는 문제입니다. 처음에는 이차원 배열을 활용한 dfs로 구현하였으나, 단방향/양방향에 이슈로 인해 정답이 제대로 나오지 않았습니다. 처음에 구현한 방식은 이차원 배열의 값들을 하나씩 체크하여, 지나갈 수 있고 방문가능한 갯수를 세었습니다. [1, 0, 0, 1] [0, 1, 1, 0] [0, 1, 1, 0] [1, 1, 0, 1]] 이렇게 하다보니 위와 같은 케이스에서 단방향/양방향 이슈에 직면하였습니다. (2->4 = 0) 물론 이것을 양방향으로 만들어도 원하는 결과를 도출해 낼 수 없었습니다. 그 이유는 원하는 정답을 도출해 내는 방식이 틀렸기 때문이라고 생각합니다. 그리하여, 리스트를 활용한 dfs를 활용했습니다. 네트워크와 같이 하나의 흐름을 쭉 확인해야하는 문..

이번문제는 우선순위 큐로 풀었어야 했을거 같은데, 시간관계상 리스트를 매번 정렬하는 방식으로 풀어보았다. 리스트를 매번 정렬하는게 비효율 적이라 생각되어, 나중에 우선 순위 큐로 다시 한번 풀어봐야겠다. import java.util.*; class Solution { public int[] solution(String[] operations) { int[] answer = new int[2]; ArrayList list = new ArrayList(); for (String a : operations) { String[] tmp = a.split(" "); String cmd = tmp[0]; int value = Integer.parseInt(String.valueOf(tmp[1])); if (cmd..

이번문제는 기본적인 흐름대로 구현하여도 무난하게 풀 수 있는문제이다. 다만, 2차원 배열의 내부가 길이가 다 다르다는 점만 주의하면된다. import java.util.*; class Solution { public int solution(int[][] triangle) { int answer = 0; int n = triangle.length; List arr = new ArrayList(); // 루트노드부터 계산한 합만 들어가 리스트 for(int i=0; i < n; i++) { // 초기화 arr.add(new int[i+1]); } int[]a = arr.get(0); // 최초갑 세팅 a[0] = triangle[0][0]; for (int i = 1; i < triangle.length; ..