본문 바로가기

전체 글

프로그래머스 - 징검다리 건너기(Java) 파라매트릭 서치(Parametric Search) 문제입니다. 파라매트릭 서치는 최적화 문제를 결정 문제로 바꾸는 이진 탐색 방법입니다. 내구도가 깍이는 징검다리가 있을 때와 한 번에 최대로 건널 수 있는 k가 주어졌을 때, 최대 몇명이 건널 수 있는지 구하는 문제입니다. 이 문제를 다시 생각해 보면 다음과 같이 바꿔 이해할 수 있습니다. '최소와 최대 내구도 사이의 값을 이용해 징검다리의 내구도를 변화시켰을 때 건널 수 있는가?' 입니다. 징검다리의 내구도를 변화시키면서 내구도가 0이 k개 이상 나오면 건널 수 없고, k개 미만으로 나오면 건널 수 있습니다. 이 내구도는 최소와 최대 내구도의 값을 절반씩 바꿔 나가는 이진 탐색을 쓸 수 있습니다. 이진 탐색의 시간 복잡도는 O(1)이고, 징검다리의 내구.. 더보기
프로그래머스 - 불량 사용자(Java) dfs 문제입니다. user_id와 banned_id가 문자열 배열로 주어집니다. user_id에서 banned_id 길이 만큼 조합을 만들어야 합니다. 만들어진 조합과 banned_id를 비교하여 매칭이 될 경우 정답에 추가하는 방법으로 문제를 해결할 수 있습니다. 단, 조합을 만들 때 순서가 보장되지 않으므로 정답에 추가할 때에는 정렬하여 추가해야 합니다. [구현 코드] import java.util.*; class Solution { private static Set ansSet; public static int solution(String[] user_id, String[] banned_id) { ansSet = new LinkedHashSet(); // user_id에서 banned_id의 개수.. 더보기
프로그래머스 - 단속카메라(Java) 그리디 문제입니다. 중간중간에 들어오는 곳과 나가는 곳이 존재하는 고속도로에 차량이 고속도로에 존재하는 좌표가 주어졌을 때, 모든 차량을 확인하는 카메라를 최소로 설치하는 개수를 구하는 문제입니다. 카메라의 개수를 구하는 것이지, 카메라의 정확한 위치를 구하는 문제가 아니기 때문에 그리디를 생각해 볼 수 있습니다. 고속도로에 처음으로 들어오는 차량을 확인하기 위해서는 최소한 해당 차량이 나가는 지점에는 설치해야 합니다. 위 그림에서는 최소 {-15} 위치에 카메라를 설치해야 합니다. 여기서 알 수 있다 싶이, 각 차량의 나가는 지점을 기준으로 오름차순 정렬을 하여 카메라를 설치하면 됩니다. 다음 카메라 설치 위치는 이전 카메라의 위치에 포함되지 않는 곳을 설치하면 됩니다. [구현 코드] import ja.. 더보기
프로그래머스 - 등굣길(Java) dp 문제입니다. 문제의 그림과 정보가 일치하지 않습니다. 문제에서 m*n 크기라 나와 있지만, n*m으로 생각해 풀어야 합니다. 이에 따라, 문제에서 주어지는 puddles의 좌표의 값도 서로 바꿔야 합니다. (1,1)부터 (n,m)까지 우측 또는 아래로만 가는 최단 경로 개수를 구하는 문제입니다. (최단 경로의 크기를 구하는 것인지 알고 오래 헤맸습니다...) 특정 위치를 (i,j)라고 하면 좌측 또는 상단의 위치인 (i, j-1)과 (i-1, j)을 확인해 더해주면 됩니다. 단, 우물의 경우는 무시합니다. [구현 코드] import java.util.*; class Solution { private static int[][] dp; private static int di = 1_000_000_007.. 더보기
프로그래머스 - 단어 변환(Java) dfs 문제입니다. begin 단어를 words 내부에 있는 단어만을 이용해 target으로 바꾸는 문제입니다. begin 단어를 words 내부의 단어로 바꿀 때 최대 한 개의 자리수만 바꿀 수 있습니다. 즉, begin과 words를 비교하여 단어 자리가 하나만 차이나는 경우를 탐색하면 됩니다. 단, 이미 탐색했던 곳은 다시 탐색하지 않게 해야 합니다. [구현 코드] import java.util.*; class Solution { private static Set wordSet; private static boolean[] visited; private static int min = Integer.MAX_VALUE; public static int solution(String begin, Strin.. 더보기
프로그래머스 - 야근 지수(Java) 힙 문제입니다. 일의 작업량이 정수 배열로 주어지고 야근 까지 남은 시간 n이 주어졌을 때, 야근 지수를 가장 적게 만들도록 하는 문제입니다. 야근 지수는 야근 이후에 남은 일의 작업량 원소들의 제곱 합 입니다. 그림에서 알 수 있듯이, a의 값이 클 수록 그 제곱의 크기는 급격히 커지게 됩니다. 따라서 일의 작업량을 처리할 때, 가장 큰 숫자부터 제거하는 방식을 사용해야 합니다. 자바의 PriorityQueue는 최소힙 입니다. 즉, 가장 작은 숫자부터 값을 빼낼 수 있는 구조이기 때문에 역순으로 돌려서 사용해야 합니다. [구현 코드] import java.util.*; class Solution { public static long solution(int n, int[] works) { long an.. 더보기
프로그래머스 - 네트워크(Java) bfs 문제입니다. 노드 n이 자연수로, 간선이 2차원 배열 형태로 주어집니다. 그래프에 주어진 조건을 입력하고, 노드의 개수만큼 탐색을 하면 끝나는 문제입니다. 단, 탐색을 하면서 방문한 노드는 다시 방문하지 않게 해야 합니다. [구현 코드] import java.util.*; class Solution { private static List graph; private static boolean[] visited; public static int solution(int n, int[][] computers) { int answer = 0; graph = new ArrayList(); for(int i=0; i 더보기
프로그래머스 - 최고의 집합 구현 문제입니다. 숫자 n과 그 합인 s가 주어졌을 때, 곱이 최대가 되는 집합을 구하는 문제입니다. n=2, s=9가 주어졌다고 가정하겠습니다. 이에 따르는 집합은 {1,8}, {2,7}, {3,6}, {4,5}입니다. 여기서 곱이 최대인 집합은 {4,5}입니다. 예제로 짐작할 수 있듯이, 최대 곱은 집합의 원소의 편차가 가장 적을 때 발생합니다. 편차를 작게하려면 s/n으로 이루어진 집합을 우선 구한 뒤, 나머지가 있을 때 원소에 각각 1씩 더해주면 됩니다. 나머지는 무조건 n보다 작기 때문에 집합의 최소 값은 s/n 입니다. 즉, 나머지가 없을 경우 최대는 s/n이고, 나머지가 있을 경우 최대는 (s/n)+1입니다. [구현 코드] import java.util.Arrays; class Solutio.. 더보기

티스토리툴바