프로그래머스에 새로운 문제가 올라왔길래 오랜만에 풀어보았다.최초에는 완전탐색으로 접근하면 시간초과가 나는걸 알면서도 다른 로직이 안떠올라서 일단 완전탐색으로 구현하고이진탐색으로 수정해서 풀이에 성공했다. 로직배열의 크기가 300,000 이므로 완전 탐색으로 접근하면 100% 시간 초과가 난다.여기서 이진 탐색을 떠올려야 하는데, level의 최댓값이 diffs 요소중 가장 큰 값이라는걸 캐치해서 풀어야 한다.그러므로 1 level의 최솟값 이진탐색으로 level의 값들을 cal 함수에 넣어주면서 탐색하면 최종적으로 level의 최솟값이 나오게 된다. cal 함수에서는 제한시간을 넘으면 탐색을 중지하고 False를 반환하고, 제한시간안에 모든 탐색을 끝냈다면 True를 반환한다. cal 함수의 반환 결과에..

30분이면 풀 수 있을 줄 알았지만 몇 시간을 고민한 문제이다. 각 열을 돌면서 매번 bfs를 탐색해도 시간초과에 안 걸릴 것 같았는데, 효율성 테스트에서 전부 시간 초과가 나서 bfs 탐색이 끝나면 각 열에 오일 개수를 추가하는 로직으로 풀이에 성공했다. 로직 일반적인 bfs와 다른점은 bfs 탐색이 끝나면 석유가 있는 열 set을 따로 만들어서 set을 순회하며 원래 oil 리스트에 인접 영역의 석유의 양인 cnt을 더해주는 것이다. 이렇게 하면 bfs 탐색은 한 번만 실행하고 석유가 있는 인접영역을 모두 열에 추가하여 답을 구할 수 있다. 최종 코드 from collections import deque def solution(land): answer = 0 n, m = len(land), len(l..

지난겨울 카카오 인턴을 지원하면서 이미 풀어보았던 문제였다. 그때는 인접 리스트를 구성해서 실제로 BFS 탐색을 돌리다가 시간 초과로 실패했었다. 이번에는 방법을 달리해서 풀이에 성공했다. 로직 각 노드의 들어오는 간선과 나가는 간선을 구하면 생각보다 쉽게 풀리는 문제다. 각 그래프마다 특정 규칙을 만족시키는 노드가 1개씩 존재한다. 정점은 들어오는 간선이 없으므로 들어오는 간선의 개수가 0이고, 나가는 간선의 개수는 문제의 조건에 따라서 2개 이상이다. 막대 모양 그래프는 이어진 노드중에 1개가 나가는 간선이 없는것이고, 8자 모양 그래프는 나가는 간선이 2개이면서 들어오는 간선은 2개 이상이다. 도넛 모양 그래프는 정점에서 나가는 간선의 개수 - 막대 모양 도형의 개수 - 8자 모양 도형의 개수를 하..

오랜만에 풀어보는 알고리즘 문제였다. 왠지 문제가 그리디하게 접근하면 풀릴것 같아서 시도했더니 한시간만에 풀 수 있었다. 로직 첫번째로 targets 배열을 정렬해야 한다. 어떤 기준으로 정렬하냐가 중요한데, 나는 s를 오름차순으로 정렬했다가 최솟값에 맞지 않는다는 것을 깨닫고 e을 오름차순으로 정렬했다. for문을 돌며 미사일이 날아오면 미사일의 시작지점인 s와 e중 한 지점에서 요격해야 한다. 미사일 하나에 맞춰서 요격을 하고 다음 미사일이 현재 요격 기준에 맞지 않으면 answer를 추가하고 요격 기준을 갱신하는 방식으로 생각하면 된다. 최종 코드 import java.util.*; class Solution { public int solution(int[][] targets) { int answe..

BFS + 조건이 붙은 문제였다. 문제를 읽고 예전에 했던 게임이 생각나서 재미있게 풀었다. 로직 먼저 board를 순회하며 아직 계산되지 않은 노드를 INF로 초기화 하고, 시작 지점과 도착 지점의 좌표를 저장한다. 시작지점에서 BFS 탐색을 시작하는데, 다른 점은 우선순위 큐를 사용한다는 것이다. 우선순위 큐를 이용하면 상하좌우 중 지금까지 가장 적은 방문 횟수를 가진 노드를 먼저 방문하게 되기 때문이다. 상하좌우를 선택하였다면, D를 만나거나 배열에 끝에 다다를때까지 계속 같은 방향으로 진행한다. 그리고 도착한 노드에 횟수를 더해주고 계속 탐색하면 된다. 최종 코드 import java.util.*; class Solution { static int[] dRow = {1, -1, 0, 0}; sta..

입력값이 매우 큰 편이었기 때문에 O(n) 이내에 끝내야겠다는 생각을 했다. 처음에는 내림차순으로 정렬을 하고 k를 우선적으로 사용하고, 나머지는 n을 사용하는 로직을 생각했다가 잘못된 로직이라는 것을 깨닫고 우선순위 큐를 이용하여 풀었다. 어떻게 생각하냐에 따라 엄청 간단한 문제일 수도 있지만, 내가 배배 꼬아서 생각했던지 풀이에 오랜 시간이 걸렸다. 로직 먼저 enemy 배열을 순회하며 n을 빼주고 우선순위 큐에 삽입한다. 만약 n이 음수로 내려간다면, 지금까지 지나왔던 라운드에 가장 큰 값이 우선순위 큐에 첫 번째 값으로 들어 있으니 그 값을 빼서 다시 n에 더해준다. 이렇게 하면 지나온 라운드 중 가장 큰 값에만 무적권을 쓰게 된 것과 같다. 더 이상 쓸 수 있는 무적권이 없다면 순회를 종료하면 ..

문제를 읽고 입력값이 크지 않아 완전탐색을 생각했었다. 백트래킹을 이용하면 어찌어찌 구현할 수 있겠다고 생각했지만, 그리 끌리지는 않았다. 주어진 순서대로 탐색을 해야 하고 가중치가 있기 때문에 그리디로 해결할 수 있다고 생각하여 도전한 결과 풀이에 성공했다. 로직 곡괭이가 없거나, 더 캘 광물이 없다면 종료해야 하므로 매 순회마다 종료 조건을 설정했다. 하나의 곡괭이는 5번을 사용할 수 있으므로 미네랄 배열을 5개씩 그룹을 만들어 탐색한다. 하나의 그룹을 각각 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이로 채굴했을 때의 피로도를 객체로 만들어 list에 넣는다. list안의 객체를 돌 곡괭이를 사용했을 때의 피로도를 기준으로 내림차순 정렬하고 가장먼저 다이아몬드 곡괭이부터 사용하고, 철 곡괭이를, 돌 곡..

오랜만에 푸는 BFS 문제였다. 기본적인 BFS 문제에서 약간 더 생각을 해야했는데, 로직을 생각하는데 그리 오래 걸리지는 않았다. 로직 먼저, 탈출을 하기 위해서는 레버까지 가야한다. 그렇기 때문에 레버까지 BFS를 통해 최단거리 탐색을 진행한다. 레버에 도착하고 다시 한번 탈출지점까지 BFS 탐색을 하는데, 여기서 중요한것은 왔던길을 다시 갈 수도 있다는 것이다. 따라서 방문 배열을 초기화 하고 BFS 탐색을 진행해야 한다. 탈출 조건이 (시작지점에서 레버에 도달 && 레버에서 탈출지점까지 도달) 이므로 둘중 하나라도 만족하지 못하면 -1을 리턴해야 한다. 최종 코드 import java.util.*; class Solution { static int[] dRow = {-1, 1, 0, 0}; sta..

문제에 각 단계에 맞게 계산하는 쉬운 문제였다. 오랜만에 Comparator를 사용하는 것과 비트 연산이 나와서 재밌었다. 다만 문제 설명이 친절하지는 않아서 예시를 보며 풀었다. 로직 문제 각 단계에 맞게 로직을 작성하면 된다. 1. Comparator를 사용하여 문제에 제시된 대로 정렬하면 된다. 2. 배열을 순회하며 값을 찾아 list에 넣는다. 주의해야 할 것은 각 컬럼의 값이 0부터가 아니라 1부터이고 주어진 타입은 배열이기 때문에 col, row_begin, row_end 값을 보정해야 한다. 3. list를 순회하며 answer에 XOR 연산을 진행한다. 최종 코드 import java.util.*; class Solution { public int solution(int[][] data, ..