DFS / BFS 둘 중 편한 것을 선택해서 풀 수 있는 문제였다. DFS가 더 편해 보여서 DFS를 이용해서 풀었는데 로직을 설계하는 게 어려워서 꽤 고민하며 풀었었다. 테스트 케이스도 5개밖에 되지 않고, 입력값이 크지 않아서 수행 시간은 생각하지 않고 풀었다. 로직 먼저 words와 동일한 크기로 방문 배열을 초기화한다. 다음으로 target 문자열이 words 배열에 있는지 검사한다. target 문자열이 words에 없다면 바로 0을 반환하고 탐색하지 않는다. 그리고 DFS 탐색을 시작하는데 begin 문자열이 target 문자열과 몇 글자가 다른지 확인한다. 만약 한 글자만 다르다면 한 번만 변환하면 되므로 리스트에 cnt + 1 값을 저장한다. 한 글자 이상이 다르다면 words 배열을 순회..

문제가 잘 이해되지 않아서 몇 번을 읽었다. 이해하고 보니 결국 연결되어 있는 노드의 개수를 저장하고 최댓값 2개를 꺼내서 곱을 반환하면 되는 문제였기에 DFS를 이용해서 풀이했다. 로직 cards 배열의 크기가 처음 선택하는 카드의 숫자이기 때문에 visited 배열의 크기를 n으로 설정한다. 첫 번째 상자부터 n번째 상자까지 순회하며 방문하지 않았다면 DFS 메서드를 호출하고 재귀 탐색한다. 열었던 상자까지 도달하면 상자의 개수를 우선순위 큐에 넣고 리턴한다. 모든 순회가 끝나면 우선순위큐의 첫 번째 두 번째 값을 곱해서 answer를 반환한다. 이때 우선순위큐의 사이즈가 1이면 첫 번째 상자 그룹 하나밖에 없다는 의미임으로 0을 반환한다. 최종 코드 import java.util.*; class S..

새롭게 나온 레벨 2 문제인데 입력값이 크지도 않고 로직이 복잡한 것도 아니라서 어렵지 않다. 어느 기업인지는 기억이 안나지만 코딩 테스트에서 비슷한 문제를 풀었던 기억이 있다. 로직 i일부터 10일동안 할인 품목을 map에 넣는다. 그리고 각 품목을 비교하는데 하나라도 number보다 작으면 안 되므로 작은 값이 나오면 탐색을 중단한다. 또한 map에 want 품목이 하나라도 없으면 안 되므로 마찬가지로 탐색을 중단한다. 모든 조건이 맞으면 answer 값을 증가시킨다. 최종 코드 import java.util.*; class Solution { public int solution(String[] want, int[] number, String[] discount) { int answer = 0; //..

레벨 3에 맞지 않게 간단한 문제였다. 문제를 풀고 나서 다른 분들 코드를 봐도 거의 똑같은 방식이라서 놀랐다. DFS / BFS 둘 다 가능한데 DFS가 먼저 떠올라서 DFS를 이용해서 풀이했다. 로직 n개의 컴퓨터를 탐색할 visited 배열을 만들고 n번 탐색한다. 최종 코드 class Solution { public int solution(int n, int[][] computers) { int answer = 0; // 방문 배열 초기화 boolean[] visited = new boolean[n]; // n개의 컴퓨터에 대해 탐색 for (int i = 0; i < n; i++) { // 방문하지 않은 컴퓨터라면 탐색 if(!visited[i]) { dfs(computers, visited, ..

효율성 테스트를 통과하기 어려웠던 문제였다. 최대한 시간 복잡도를 줄여서 코드를 작성하려고 노력했지만 한 번에 통과하진 못하고 여러 가지 로직으로 시도해서 성공했다. 로직 첫 번째 시도는 list를 사용해서 최댓값의 인덱스를 찾고 set을 통해 값을 변경하는 로직이었지만 효율성에서 통과하지 못했다. 아마 최댓값의 인덱스를 찾는 과정에서 시간이 꽤 소요돼서 통과하지 못했던 것 같다. 두 번째 시도는 매번 배열을 정렬하면서 가장 뒤에 있는 값에 -1 해주며 n을 줄이는 로직으로 시도했지만 이것도 효율성을 통과하지 못했다. 마지막 시도는 내림차순 우선순위 큐를 선언하고 큐의 가장 앞에 있는 값을 줄이는 로직으로 성공했다. 실패 코드 import java.util.*; class Solution { public..

입력값이 매우 클수도 있기 때문에 효율성 맞추기가 어렵겠다라는 생각이 들었다. 처음에는 재귀를 이용해서 조합을 만드려고 했는데 100% 효율성 테스트에서 걸린다고 생각해서 최대한 간단한 로직으로 풀기위해 고민했다. 조금 생각해보니 금방 로직이 보여서 성공했다. 로직 answer 배열의 크기를 n으로 초기화 한다. for문을 돌면서 answer 배열의 값을 찾는데 s를 cnt로 나눈 temp의 값이 배열의 첫번째 값이다. 만약 temp가 0이면 모든 원소의 곱은 0이 되기 때문에 바로 배열에 -1를 넣고 반환한다. temp의 값이 0이 아니면 s에서 temp값을 빼주고 cnt를 줄인다. 이렇게 n번 반복하게 되면 최고의 집합을 찾을수 있다. 최종 코드 import java.util.*; class Solu..

전에 백준에서 비슷한 문제를 풀어본 기억이 있어서 쉽게 해결했다. 힙을 이용해서 직접 구현해야 한다면 꽤 복잡해질 것 같은데 Java에는 우선순위 큐가 정의되어있기 때문에 그냥 두 개의 우선순위 큐를 만들어서 풀었다. 로직 낮은 숫자부터 정렬되는 우선순위 큐와 높은 숫자부터 정렬되는 우선순위 큐를 선언한다. operations 배열을 순회하며 명령어와 숫자를 분리하고 명령어가 삽입인 경우 두 큐 모두에 추가하고 명령어가 삭제라면 먼저 queue가 비어있는지 확인하고 비어있지 않으면 최솟값 삭제인지 최댓값 삭제인지 구별한다. 최솟값 삭제라면 queue1의 값을 peek 해서 저장하고 queue1에서 하나를 삭제한다. 그리고 peek 했던 값을 queue2에서 삭제한다. 최댓값 삭제라면 반대로 진행하면 된다..

문제 유형에 DP라고 쓰여있었기 때문에 어떻게 DP로 구현해야 할지 고민을 많이 했다. 점화식을 떠올리기 쉽기 때문에 레벨 3보다는 레벨 2에 더 적합한 문제라는 생각이 들었다. Bottom-up 방식이 가장 먼저 떠올라서 풀었지만 Top-down 방식으로도 풀이가 가능할 것 같다. 로직 가장 밑에 층에서부터 가장 위층까지 올라가며 각 층의 최댓값을 찾는다. 그 층에서 최댓값을 찾았다면 바로 위층에 i - 1에 해당하는 값을 더해서 바꿔준다. 결과적으로 가장 위층에는 최댓값이 남게 된다. 점화식은 triangle[i - 1][j] = triangle[i - 1][j] + triangle[i][j] 의 최댓값이다. 최종 코드 class Solution { public int solution(int[][] ..

프로그래머스 레벨 2의 마지막 문제였다. 레벨 1, 2의 문제를 모두 풀어서 약간의 성취감이 느껴졌다. 정답률이 낮아서 어렵겠다 싶었는데 문제 맨 밑에 교점을 구하는 공식을 주었기 때문에 생각보다는 쉬운 편이었다. 로직 line 배열을 순회하며 2개의 식의 교점을 찾는다. AD - BC가 0이면 0으로 나눌 수 없기 때문에 반환하고 찾은 좌표가 정수인지 판별하여 정수라면 list에 저장한다. 그리고 x, y의 최댓, 최솟값을 MinMax 배열에 저장한다. 별을 찍을때 최댓, 최솟값이 배열의 경계가 되기 때문이다. x, y의 최솟값부터 최댓값까지를 순회하며 list에 저장된 교점의 좌표가 나오면 *을 찍고 그게 아니라면 . 을 찍어 문자열로 만든다. 최종 코드 import java.util.*; class..