레벨 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..

어려웠던 문제였다. 로직이 간단하지도 않고 마지막까지 방심하면 틀리는 문제였기 때문이다. 꼼꼼하게 생각하지 못한 탓인지 첫 풀이에는 테스트 케이스가 반 이상 틀렸고 한번 수정에 테스트 케이스를 1~2개씩 맞추기 시작해서 결국 전부 다 맞게 되었다. 다만 문제를 푸는데 시간이 너무 오래 걸렸다. 로직 일치하는 음악이 없을 때 바로 반환하기 위해 answer를 (None)으로 초기화한다. musicinfos 배열을 순회하면서 탐색을 시작한다. 순차적으로 재생 시간을 구하는 메서드, 재생 시간에 맞춰 악보를 만드는 메서드, 조합을 검사하는 메서드를 호출한다. 첫 번째 메서드는 재생 시간을 분으로 변환해서 총 재생시간을 분으로 변환하고 시간을 반환한다. 두 번째 메서드는 재생 시간만큼 멜로디를 만들어 list에..

문제를 읽자마자 재귀를 활용해서 풀어야 한다는 사실을 알 수 있었다. 다만 로직을 한참을 고민했다. 재귀 탈출은 어떤 조건에서 해야 할지 어떤 상황에서 재귀 탐색이 들어갈지 기준을 잘 잡지 못했기 때문이다. 문제를 풀고나서 이 문제가 분할 정복에 속한다는 것을 알게 되었다. 지금까지 분할정복 문제를 한 번도 풀지 않아서 더 헤맸던 것 같다. 로직은 x, y 좌표를 기준으로 탐색 범위를 지정한다. 그리고 영역 분할 메서드를 호출한다. 그리고 현재 영역이 압축이 가능한지 압축 메서드를 호출하여 확인한다. 압축이 가능하다면 answer 배열에 바로 값을 업데이트 하고 압축이 불가능하다면 영역을 4개로 나누어서 재귀 호출을 진행한다. 1번 영역이 위 왼쪽, 2번 영역이 위 오른쪽, 3번 영역이 아래 왼쪽, 4번..

많이 보던 탐색 문제여서 금방 해결할 수 있을 것 같았는데 시간이 좀 걸렸다. 좌표로 접근하여 위, 아래, 왼쪽, 오른쪽을 전부 체크해야 했는데 처음에는 Map을 이용하려고 했지만 실패했다. 3차원 배열을 쓰기 싫어서 다른 방법으로 시도해봤지만 실패하고 결국 3차원 배열을 이용해서 풀었다. 로직은 좌표가 -5부터 5까지의 범위임으로 배열크기를 11로 설정한다. x, y의 좌표를 5,5에서 호출해야 0,0과 같으므로 경로 탐색 메서드의 매개변수를 5,5 로 설정한다. 그리고 dirs을 순회하며 움직이는데 범위를 벗어나는지 체크하고 방향을 체크한다. 처음으로 방문한 경로라면 answer를 증가시키고 이동한다. 최종 코드 import java.util.*; class Solution { static int a..