Coding Test/Coding Test 문제 풀이
-
프로그래머스(Level 3) - 가장 먼 노드Coding Test/Coding Test 문제 풀이 2022. 1. 29. 11:51
문제 설명 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 1번 노드로부터 가장 멀리 떨어진 노드는 총 몇 개인지 구하는 문제이다. 매개변수로 주어진 간선의 정보를 이용해서 그래프를 구성하고, 1번 노드부터 너비 우선 탐색을 시작한다. 다음 노드를 탐색할 때마다 각 노드의 깊이를 이전 노드의 깊이 +1을 해줌으로써 각 노드의 깊이를 계산하였다. 모든 노드의 깊이를 계산하였으면, 그중 가장 깊이 있는 노드의 개수를 반환해줌으로써 문제를 해결하였다. 전체 소스코드 import java.io.*; import java.util.*; class Solution11 { static ..
-
프로그래머스(Level 2) - 카펫Coding Test/Coding Test 문제 풀이 2022. 1. 28. 12:36
문제 설명 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 풀이 카펫의 갈색 격자의 수와 노란색 격자의 수가 주어졌을 때, 이를 만족하는 카펫의 가로, 세로 길이를 구하는 문제이다. 우선 갈색 격자의 수와 노란색 격자의 수를 합쳐서 전체 격자의 수를 구한다. 전체 격자의 수에서 구성될 수 있는 모든 가로, 세로 조합을 탐색한다. 이때 적합한 가로, 세로 조건은 다음과 같다. 1. 가로, 세로의 길이는 정수여야 한다. 2. 가로의 길이는 세로의 길이와 같거나, 길어야 한다. 위 조건에 부합하는 가로, 세로를..
-
프로스래머스(Level 2) - H-IndexCoding Test/Coding Test 문제 풀이 2022. 1. 28. 11:33
문제 설명 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 풀이 처음 지문을 읽어 봤을 때 무슨 문제인지 감을 못 잡았다. 지문을 2, 3번 반복해서 읽어보니 어떤 문제인지 대충 알 것 같은 느낌이었다. "논문 n 편 중, h 번 이상 인용된 논문이 h 편 이상이고 나머지 논문이 h 번 이하 인용되었다면 h의 최댓값이 H-Index이다."라고 지문에 나와있다. 이 문장을 해석해보자면 h 번 이상 인용된 논문이 h 편 이상인 h의 최댓값을 구하라는 문제이다. 우선, 논문 인용 수..
-
프로그래머스 (Level 3) - 가장 큰 수Coding Test/Coding Test 문제 풀이 2022. 1. 27. 18:49
문제 설명 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 풀이 처음에는 완전 탐색 알고리즘을 이용해 모든 수의 조합을 탐색한 후 가장 큰 수를 찾으려고 했다. 하지만 코드를 제출했을 때 메모리 초과가 나는 것을 확인하고, 다른 풀이를 모색하였다. 정수형 배열 numbers를 문자열 배열로 변환한다. 문자열 배열을 특정 기준으로 정렬해주기 위해서 Comparator 인터페이스 내 compare( ) 메서드를 재정의해주어야 한다. 예제 2의 경우 ..
-
프로그래머스 (Level 3) - 여행경로Coding Test/Coding Test 문제 풀이 2022. 1. 27. 16:52
문제 설명 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 풀이 주어진 항공권 정보를 이용해 방문하는 공항 경로를 찾아내는 문제이다. 방문 가능한 경로가 2개 이상일 경우 알파벳 순서로 방문을 해야 하는 조건 때문에 까다로웠던 문제이다. 해당 조건을 고려해서 방문할 수 있는 모든 여행경로를 DFS 알고리즘을 이용해서 탐색한 후 List 자료구조에 저장을 하였다. 모든 여행경로의 탐색이 끝났으면, List 자료구조 내의 데이터를 알파벳 순으로 오름차순을 한다. 오름차순으로 정렬..
-
프로그래머스 (Level 3) - 단어 변환Coding Test/Coding Test 문제 풀이 2022. 1. 26. 23:09
문제 설명 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 주어진 단어 정보를 이용해서 그래프를 생성한다. 한 문자만 빼고 나머지 문자가 같은 단어끼리 간선을 추가한다. 그래프가 완성되면 begin 단어에서 target 단어까지 경로의 길이를 반환하는 방법으로 문제를 해결하였다. /** 그래프를 구성하는 각 노드의 정보를 정의한 클래스 */ static class Node { String word; // 단어 List adjacents; // 인접한 단어들(한 ..