SilentWalk

풀이 과정 프림 알고리즘을 떠올리면 풀이를 쉽게 진행할 수 있다. 섬의 갯수가 1 이상, 100 이하로 주어졌으며 절대로 연결될 수 없는 섬은 주어지지 않는다고 하였으므로 시작지점을 임의로 0번 섬으로 지정하여도 아무런 문제가 없다. 기본적인 풀이의 진행방식은 아래와 같다. Edge의 cost에 대해 오름차순 정렬하는 Priority Queue를 준비한다. 현재까지 방문한 각 섬에 대하여 이하의 과정을 수행한다. 전체 edge에서 현재 선택중인 섬과 연결된 edge를 찾는다. 해당 edge의 다른 한 쪽 끝이 아직까지 방문하지 않은 섬과 연결되어있는지를 확인한다. 방문하지 않은 섬과 연결되어 있는 edge는 다음번에 설치될 다리가 될 가능성이 있으므로 1에서 준비한 Priority Queue에 추가한다...

문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이과정 주어진 자동차 정보(출입지점, 이탈지점)을 이탈지점을 기준으로 오름차순으로 정렬한다. (단, 여기서 모든 차량은 한 방향으로만 진행한다는 가정이 있어야 한다.) 맨 앞 차량(가장 먼저 이탈하는 차량)이 카메라에 잡히기 위해서는 반드시 이 차량의 [진입 지점, 이탈 지점]의 범위 내에 단속 카메라가 설치되어야 한다. 여기서 가장 다른 차량과 동선이 겹칠 가능성이 높은 지점은 이 차량의 이탈지점이다. 그 이유는 이미 1에서 이탈지점을 기준으로 오름차순 ..

문제 이 풀이 및 코드는 2022년 3월 14일 재검토 시점에 오답으로 처리되고 있습니다. 풀이과정 주어진 문자열의 현재 위치(시작시 0)에서 가장 가까운 ‘A’가 아닌 문자의 위치를 찾는다. 해당 위치까지 이동할 때, 좌우 방향 중 더 적은 이동횟수를 센다. 해당 문자를 ‘A’로 바꾸기 위해 상하 방향 조작 횟수를 센다. 2와 3의 결과를 더한다. 해당 문자를 ‘A’로 교체한다. 더이상 ‘A’ 문자가 없을 때 까지 1~4 과정을 반복한다. 위 과정처럼 문제를 풀이했을 때 테스트 케이스 11, 13, 23, 25, 26에서 실패가 발생한다. 이에, 위 과정 중 2번 과정에서 좌우 방향 이동횟수가 같을 때 어느 한 쪽 방향에 대한 우선도가 존재하는지 확인 해 보았으나 별도의 우선도가 존재하지는 않는 것으로..

문제 : programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 먼저, 각 학생별 체육복 도난 및 여분 보유 여부를 정리한다. 각 학생들의 체육복 보유 수량을 나타내는 정수 배열을 선언하고 그 값을 모두 1로 초기화한다. (시작시점에는 모든 학생이 체육복을 가지고 있다.) 도둑질 당한 학생들의 번호에 해당하는 원소들에서 1씩 뺀다. 여분 체육복을 가지고 온 학생들의 번호에 해당하는 원소들에 1씩 더한다. 이후, 맨 앞 학생부터 차례..

문제 : programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 두 개의 Priority Queue를 사용하여 하나는 오름차순으로, 다른 하나는 내림차순으로 정렬하여 구현한다. 이 때, 별도로 원소의 갯수를 counting 하는 size 변수를 두어 size가 0이 되면 두 queue를 모두 clear 해 주어야 한다. 만일 이 과정을 넣어주지 않으면 다음과 같은 문제가 발생할 수 있다. 가정 : 이중 우선순위 큐 (이하 dpq)는 1, 2, 3을 원소로 가지고 있다. 전개 최솟값을 두 번 poll 한다. = 오름차순으로 정렬된 priority queue (이하 minQueue)에서 두 번 poll 한다. ..

문제 : programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr "작업의 요청부터 종료까지 걸린 시간의 평균"을 최소화 하기 위해서는 Shortest Job First로 Job scheduling을 해 주어야 한다. 또, 문제에 주어진 조건에서 하드디스크가 idle 상태일 때에는 먼저 들어온 작업부터 처리해야 하므로 이 부분도 같이 고려해야 한다. 이는 두 개의 priority queue를 사용하여 해결할 수 있다. 이 두 ..

문제 : programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 주어진 scoville array를 priority queue에 넣기만 하면 쉽게 해결되는 문제 소스코드 import java.util.PriorityQueue; class Solution { private int count = 0; public int solution(int[] scoville, int K) { PriorityQueue pq = new ..

문제 : programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 아이디어 주어진 부위의 의류를 입지 않는 것 또한 하나의 선택지로 간주하면 계산이 매우 빠르고 편리해진다. 예를 들어, 주어진 예시 #1의 경우 headgear에 2종류, eyewear에 1종류의 의류가 주어졌는데, 여기에 "선택 안함" 선택지를 추가하면 각각 3종류, 2종류가 된다. 그러면 선택 가능한 총 가짓수는 3 * 2 = 6가지가 되는데, 문제에 주어진 조건에서 최소 한 개의 의상은 입는다고 하였으므로 모두 "선택 안함"을 선택하는 한 종류를 빼주면 결과값으로 5를 얻을 수 있다. 소스코드 import java.util.HashMap; impo..