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/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..

문제: https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 아이디어 이 문제에서는 각 번호 사이의 포함관계가 아니라, 접두어 관계가 있는지 여부를 판단하는 것이 목적이기 때문에 주어진 전화번호 String들 중 가장 짧은 길이를 찾고, 각 전화번호의 앞에서부터 해당 길이만큼만 비교하는 방법을 취했다. 즉, 가장 짧은 길이가 n 이라면 전화번호들의 앞 n자리 글자들만 떼어내어 이를 key로 사용하는 map에 p..

문제 : programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 아이디어 1. 장르 데이터 정리 Map 변수를 사용하여 각 장르별 총 재생수를 계산한다. 장르 명, 총 재생수를 멤버 변수로 가지는 Genre class를 정의하고, Comparable을 implements 하여 총 재생수를 바탕으로 Genre끼리 대소비교가 가능하도록 해 준다. 이 때, 내림차순으로 정렬될 수 있도록 한다. 위 Map에 만들어놓은 정보를 바탕으로 ..

문제 - 프로그래머스 "여행경로" 풀이 과정 주어진 공항의 이름을 오름차순 정렬한다. 이동 가능한 경로가 2개 이상일 경우 알파벳의 오름차순으로 경로를 결정하기 위해 사용한다. 이름의 오름차순 정렬한 공항들에 index를 설정한다. 이 [이름 - index] 관계는 주어진 티켓에 따른 각 공항별 잔여 방문 횟수를 나타내는 2차원 배열을 나타내기 위해 사용한다. 위 1과 2에서 준비한 결과물을 바탕으로 출발/도착 공항별 잔여 방문 횟수를 2차원 배열로 나타낸다. 문제에서 주어진 예제 1번의 경우 아래의 표와 같이 나타낼 수 있다. DFS 방식으로 방문할 공항을 탐색한다. 최종 결과물을 주어진 조건에 맞게 공항의 이름으로 변경하여 반환한다. DFS 전개 주어진 출발공항을 현재까지 확인한 여행경로 Queue에..