hansjour 개발일지

[프로그래머스] 다리를 건너는 트럭

문제 파악- 큐 자료구조 활용 접근 방법-다리 길이를 한정해두고 0으로 채워둔다. 그리고 1초 지날 때마다 한 칸씩 이동한다고 생각하기.-다리를 이동하는 거리를 시간과 연계 시켜 생각하는 게 중요하다. 풀이 코드 import java.util.*;class Solution { public int solution(int bridge_length, int weight, int[] truck_weights) { Queue bridge = new ArrayDeque(); for(int i=0;i - 핵심) for문으로 truck_weights 배열을 돌며 체크했었는데, 이러면 트럭이 올라가지 못할 경우에도 루프가 돌아 다음 원소로 넘어가게 된다.while과 인덱스 수동 증가를 ..

문제 파악 & 접근 방법-BFS-4방이 뚫리거나 or 해당되는 알파벳 전부 -> 주어진 요청 형태(1자 or 2자) 에 따라 소거해간다1글자이면 모든 해당 컨테이너 제거2글자이면 공기와 맞닿은 컨테이너 제거 1차 코드 구현import java.util.*;class Solution { static int x; static int y; public int solution(String[] storage, String[] requests) { int answer = 0; x = storage.length; y = storage[0].length(); char[][] storages = new char[x][y]; for(int i..

문제 파악 & 접근 방법-실제 컴퓨터가 프로세스를 관리할 때 사용하는 큐 자료구조를 이해하고 이를 바탕으로 풀기-우선순위 큐를 사용해 먼저 사용해야하는 자원(서버)을 소진한다. O(1)-24시간동안 접속하는 사용자 수(players)가 주어지면 -> 서버가 몇개 필요한지 체크 -> 지금 올라온 서버(size)와 비교, 차이 발생하면 필요한만큼(more) 증설하고, 만료 시간 배열로 함께 큐에 저장 *주의 사항 : /m (=몫n)당 서버 n개 필요. 소숫점은 버린다. (기존 서버가 포용 가능) 코드 구현import java.util.*;class Solution { public int solution(int[] players, int m, int k) { PriorityQueue pq ..

문제 파악-주어진 k부터 n까지 최소 거리를 구하는 문제-다익스트라 함수 구현하기-가중치 = 시간접근 방법-Edge, Entry 클래스로 구조체형태 만들기-우선순위 큐를 활용해 거리가 짧은 노드들부터 순회-큐에 들어간 원소를 전부 비워낼 때까지 while문 돌며 distance가 최소거리인지 체크-(+) 그와 연결 된 노드들과의 거리도 최소거리인지 체크-절대적인 최솟값 거리를 저장하는 distances 배열 통째로 리턴⇒ 왜? 특정 노드 n까지의 최소거리가 아니라, 모든 노드를 순회할 때의 최솟값이기 때문.(순서가 있는 그래프가 아니므로 n까지 != 최댓값임)-리턴받은 최솟값 모음 배열을 돌며 가장 그 중 가장 오래 걸린 시간을 찾는다.(max)코드 구현import java.util.*;class Sol..

문제 파악-dp활용  제한 사항1 1 0 접근 방법-0~n까지 현재 금액 누적해가기(for문)-금액 도달 전까지 누적해가며 dp 수행, 수행하면서 대상 값을 업데이트해가며 돌려줌(amount-coin)-완전탐색으로도 구현이 가능하나 효율성에서 문제 발생!!-메모이제이션 활용) n번째 계단처럼, n번째 값까지의 최소값을 하나하나 메모해두고계산하지 않은 것만 dp수행, 이미 계산된 것은 배열 안에서 골라서 result값 갱신하기코드 구현import java.util.*;class Solution { public int solution(int[] coins, int amount) { int[] memory = new int[amount+1]; Arrays.fill(memory,I..

문제 파악-dp를 이용해 구현한다.Constraints:2 0 접근 방법-bottom-up 방식으로 구현한다.-n(cost.length) 계단까지 최소비용을 구하기 위해 최소비용 배열 선언하여 메모하기-마지막 계단에 해당하는 최소 비용 리턴코드 구현import java.util.*;class Solution { public int minCostClimbingStairs(int[] cost) { //memoization initialization int[] dp = new int[cost.length+1]; for(int i=2;i배우게 된 점처음에 첫 계단 혹은 둘째 계단에서 시작할 수 있으므로 둘 다 비용 계산 의미 없음고로 2번째 계단에서부터 ..

문제 파악-저번 실습으로 나온 문제. 각 방을 돌며 최초의 좌석 찾고 그로부터 되는 방향을 나아가며 거리가 2 이내에 좌석이 발견되면 false리턴places의 행 길이(대기실 개수) = 5places의 각 행은 하나의 대기실 구조를 나타냅니다.places의 열 길이(대기실 세로 길이) = 5places의 원소는 P,O,X로 이루어진 문자열입니다.places 원소의 길이(대기실 가로 길이) = 5P는 응시자가 앉아있는 자리를 의미합니다.O는 빈 테이블을 의미합니다.X는 파티션을 의미합니다.입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.return 값 형식1차원 정수 배열에 5개의 원소를 담아서 return 합니다.places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로..

문제 파악-주어진 2차원 배열은 서로 간선으로 연결 된 관계-주어진 그래프에서 최대 거리에 있는 노드 갯수를 구하기노드의 개수 n은 2 이상 20,000 이하입니다.간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.접근 방법💡 -각 노드와 연결관계를 파악하고 인접리스트 형태로 변환하여 진행-bfs 를 이용하여 해당 그래프의 순회 거리를 구하고 최대 거리의 노드 갯수 구하기-방문 노드는 제외하고 큐 순회를 한다.-간선 별로 몇번 째로 순회하는지 세기 위한 cnt와 직관적으로 보기 편한 리스트 구현하기 코드 구현import java.util.*;class Solution { public ..

문제 파악-서로 이어져있는 그래프의 간선을 ‘하나’ 끊었을 때, 두 개로 나누어진 그래프를 각각 순회-순회 시 방문 노드를 카운트하여 리턴하고, 각 순회가 끝났을 때 두 그룹의 카운트 차를 비교-최솟값을 갱신하여 최종 리턴n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.1 ≤ v1 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.접근 방법💡 -BFS를 이용하여 각 노드를 순회 -그래프를 둘로 쪼갤 때 ⇒ 간선을 순회하며 하나씩 다 삭제해보기(O(n))-인접리스트 형태로 ..

https://leetcode.com/problems/number-of-islands/ 문제 파악-2차원 배열이 주어지고, 1이 상하좌우로 있는지 체크하여 섬이 총 몇 개 있는지 센다. (분기체크)m == grid.lengthn == grid[i].length1 grid[i][j] is '0' or '1'.접근 방법-0은 물, 1은 섬. 물 만나거나 범위 벗어나지 않는 이상, 섬 한 덩어리로 본다.-1이면 계속 순회하며 visit 체크(무한 루프 방지)-처음 기준 노드는 ‘1’ 나오면 시작. 타고 가서 상하좌우 dfs 체크⇒ 막히면 return되고, 다른 방향으로 탐색 시작-If 0이거나, 벽이면 순회 끝(base case)코드 구현import java.util.*;class Solution { p..