kwang2134 님의 블로그

[Programmers] 피로도 - LV 2 접근완전 탐색풀이피로도가 주어지고 던전을 돌 때마다 던전이 요구하는 피로도가 소모된다. 던전에 입장하기 위한 최소 피로도가 존재할 때 가장 많은 던전을 탐험할 때 몇 개의 던전 탐험이 가능한지 구하는 문제이다. 그리디나 dp도 생각은 해봤는데 최소 피로도가 존재해 이전 선택이 다음 선택에 영향을 미치다 보니 그냥 완전탐색으로 풀었다.  private static int answer; public int solution(int k, int[][] dungeons) { answer = 0; boolean[] isVisited = new boolean[dungeons.length]; dfs(k, dungeons..

[Programmers] 더 맵게 - LV 2 접근힙풀이음식의 스코빌 지수가 주어지고 모든 음식의 스코빌 지수를 K 이상으로 만드는 문제이다. 음식을 섞어 스코빌 지수를 올릴 수 있고 음식을 몇 번 섞어야 모든 음식의 스코빌 지수가 K를 넘는지 구해야 한다. 힙 카테고리의 문제로 힙을 통해 구현된 우선순위 큐를 사용하면 간단하게 풀 수 있다. public int solution(int[] scoville, int K) { PriorityQueue pq = new PriorityQueue(); for (int i : scoville) { pq.offer(i); } int answer = 0; while (!pq.isEm..

[Programmers] 프로세스 - LV 2 접근큐풀이프로세스를 우선순위에 맞춰 실행하였을 경우 특정 위치의 프로세스가 몇 번째에 실행되는지 구하는 문제이다. 스택과 큐 파트에 있는 문제인데 설명부터 실행 대기 큐에 존재하는 프로세스로부터 수행되기 때문에 큐를 사용하는 문제이다. 큐에서 꺼낸 프로세스보다 우선순위가 높은 프로세스가 큐에 존재하는 경우 프로세스를 다시 큐에 넣게 되고 한 번 실행한 프로세스는 그대로 종료된다. 큐에 특정 위치의 프로세스가 몇 번째 실행되는지 구해야 하는 문제이기 때문에 우선순위와 위치를 같이 관리해주어야 한다. private class Process { int location; int priority; public Process(..

[Programmers] 의상 - LV 2 접근해시풀이의상을 조합해 만들 수 있는 모든 경우의 수를 구하는 문제이다. 의상의 카테고리에서 최대 1개의 의상을 입을 수 매일 최소 1개의 의상은 필수로 입어야 한다.  public int solution(String[][] clothes) { Map clothesMap = new HashMap(); for (String[] clothe : clothes) { clothesMap.merge(clothe[1], 1, Integer::sum); } int answer = 1; for (int count : clothesMap.values()) { answer..

[Programmers] 전화번호 목록 - LV 2접근완전 탐색해시Trie풀이전화번호가 들어있는 배열이 주어지고 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 없다면 true를 반환하는 문제이다. [119, 119552]와 같은 번호가 주어졌을 때 119가 다른 번호인 119552의 접두어이기 때문에 false를 반환해야 한다.완전 탐색 단순하게 하나씩 다 비교해 보는 방법이다. 전화번호를 길이순으로 정렬해 준 뒤 짧은 번호들을 접두어로 보고 긴 번호들에 하나씩 전부 비교해 보는 방법이다.  public boolean solution(String[] phone_book) { Arrays.sort(phone_book, Comparator.comparingInt(String::..

[Programmers] 무인도 여행 - LV 2접근dfs풀이무인도 여행이라는 문제로 좌표가 주어지고 X 가 적혀있는 곳은 바다 숫자가 적혀있는 곳은 무인도로 숫자는 해당 땅에서 숫자 일수만큼 버틸 수 있는 식량이 존재한다는 뜻이다. 연결된 섬들에서 머무를 수 있는 일수를 모두 구한 뒤 배열에 담아 오름차순으로 반환하는 문제이다.  유사한 문제를 많이 풀었기 때문에 제일 먼저 생각나는 bfs, dfs로 풀었다. 이 문제는 모든 위치를 탐색하기만 하면 되기 때문에 dfs, bfs 중 아무거나 사용해도 큰 상관이 없어 재귀를 이용한 dfs로 풀었다. LeetCode에서 문제를 풀다 보니 재귀로 해결한 코드와 큐나 스택을 직접 사용한 코드의 속도 차이를 보니 자연스럽게 재귀로 해결이 가능하다면 시도해 보는 것..

[Programmers] 호텔 대실 - LV 2접근그리디풀이오랜만의 프로그래머스 문제이다. 호텔 대실이라는 문제로 대실에 대한 시작 시간과 종료 시간이 주어지고 모든 예약 처리를 위해 최소 몇 개의 방이 필요한 지 구하는 문제이다. 특이 사항으로 대실이 종료된 후 청소 시간이 존재하기 때문에 종료 후 10분간은 청소를 위해 대실이 제한된다.  public int solution(String[][] book_time) { Arrays.sort(book_time, (a,b) -> a[0].compareTo(b[0])); PriorityQueue endTimeQueue = new PriorityQueue(); int result = 1;우선 예약 관리를..

[NeetCode-LeetCode] Sum of Two Integers - Medium접근비트 조작풀이단순하게 두 수를 더하는 문제인데 +, - 연산자를 사용하지 않고 두 수의 합을 구하는 문제이다. 즉 비트 연산자를 사용해 덧셈을 구현하면 되는 문제이다.  간단하게 생각하면 비트 연산으로 더하기가 되려면 1과 0이 만나면 1이 되어야 하고 1과 1이 만나면 0, 0과 0이 만나도 0이 되어야 한다. XOR을 쓰면 정확하게 두 비트가 다른 경우에만 1이 되기 때문에 더하기 과정을 구현할 수는 있다. 그러나 단순하게 XOR 연산만 수행하다 보면 올림 처리된 즉 캐리가 발생하는 경우 캐리에 대한 처리가 이루어지지 않는다. //캐리가 발생하지 않는 덧셈1 + 2 = 01 ^ 10 = 11 = 3 -> 정상 값..

[NeetCode-LeetCode] Set Matrix Zeroes - Medium접근수학(?)풀이행렬에 0이 있는 위치의 행과 열 모든 숫자를 0으로 만드는 문제이다. 0이 있는 위치가 [3,4]이라면 3행에 있는 모든 숫자와 4열에 있는 모든 숫자를 0으로 만드는 것이다. 이 문제에 주어진 추가 질문으로는 O(mn)의 공간 복잡도로 푸는 건 대체적으로 좋지 않은 방법이고 개선하여 O(m+n)의 공간 복잡도로 풀 순 있지만 최선의 방법은 아니다 그렇다면 상수 공간 복잡도로 해결을 해보라는 말인데 상수 공간 복잡도로 해결하려면 추가적인 배열을 사용하지 않아야 한다는 소리다. public void setZeroes(int[][] matrix) { int m = matrix.length;..

[NeetCode-LeetCode] Rotate Image - Medium접근행렬 회전풀이n x n 배열의 원소들을 90도로 회전한 결과를 반환하는 문제이다. 원소를 그대로 오른쪽 90도로 돌린 상태로 만들면 되는데 추가 적인 공간을 할당하지 않고 주어진 배열을 조작해서 변경해야 한다. 수학과 공간 지각 문제다 보니 조금 만나기 싫은 유형의 문제였다. public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i 90도로 회전하는 방법은 행렬을 전치한 뒤에 각 행을 뒤집게 되면 90도로 전환이 된다고 한다. 위는 행렬을 전치하는 과정으로 행과 열의 위치를 바꾸는 것이다.  for (int i = 0..