티스토리

Roy's Blog

검색하기

블로그 홈

Roy's Blog

rovictory.tistory.com/m

로승리 님의 블로그입니다.

구독자: 5

방명록 방문하기

주요 글 목록

(Python) 프로그래머스 - 퍼즐 게임 챌린지 프로그래머스에 새로운 문제가 올라왔길래 오랜만에 풀어보았다.최초에는 완전탐색으로 접근하면 시간초과가 나는걸 알면서도 다른 로직이 안떠올라서 일단 완전탐색으로 구현하고이진탐색으로 수정해서 풀이에 성공했다. 로직배열의 크기가 300,000 이므로 완전 탐색으로 접근하면 100% 시간 초과가 난다.여기서 이진 탐색을 떠올려야 하는데, level의 최댓값이 diffs 요소중 가장 큰 값이라는걸 캐치해서 풀어야 한다.그러므로 1 level의 최솟값 이진탐색으로 level의 값들을 cal 함수에 넣어주면서 탐색하면 최종적으로 level의 최솟값이 나오게 된다. cal 함수에서는 제한시간을 넘으면 탐색을 중지하고 False를 반환하고, 제한시간안에 모든 탐색을 끝냈다면 True를 반환한다. cal 함수의 반환 결과에.. 공감수 3 댓글수 1 2024. 9. 14.
(Python) 프로그래머스 - 석유 시추 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.. 공감수 1 댓글수 1 2024. 3. 8.
(Python) 프로그래머스 - 도넛과 막대 그래프 지난겨울 카카오 인턴을 지원하면서 이미 풀어보았던 문제였다. 그때는 인접 리스트를 구성해서 실제로 BFS 탐색을 돌리다가 시간 초과로 실패했었다. 이번에는 방법을 달리해서 풀이에 성공했다. 로직 각 노드의 들어오는 간선과 나가는 간선을 구하면 생각보다 쉽게 풀리는 문제다. 각 그래프마다 특정 규칙을 만족시키는 노드가 1개씩 존재한다. 정점은 들어오는 간선이 없으므로 들어오는 간선의 개수가 0이고, 나가는 간선의 개수는 문제의 조건에 따라서 2개 이상이다. 막대 모양 그래프는 이어진 노드중에 1개가 나가는 간선이 없는것이고, 8자 모양 그래프는 나가는 간선이 2개이면서 들어오는 간선은 2개 이상이다. 도넛 모양 그래프는 정점에서 나가는 간선의 개수 - 막대 모양 도형의 개수 - 8자 모양 도형의 개수를 하.. 공감수 1 댓글수 1 2024. 3. 6.
(Java) 프로그래머스 - 미사일 요격 오랜만에 풀어보는 알고리즘 문제였다. 왠지 문제가 그리디하게 접근하면 풀릴것 같아서 시도했더니 한시간만에 풀 수 있었다. 로직 첫번째로 targets 배열을 정렬해야 한다. 어떤 기준으로 정렬하냐가 중요한데, 나는 s를 오름차순으로 정렬했다가 최솟값에 맞지 않는다는 것을 깨닫고 e을 오름차순으로 정렬했다. for문을 돌며 미사일이 날아오면 미사일의 시작지점인 s와 e중 한 지점에서 요격해야 한다. 미사일 하나에 맞춰서 요격을 하고 다음 미사일이 현재 요격 기준에 맞지 않으면 answer를 추가하고 요격 기준을 갱신하는 방식으로 생각하면 된다. 최종 코드 import java.util.*; class Solution { public int solution(int[][] targets) { int answe.. 공감수 0 댓글수 0 2023. 11. 8.
(Java) 프로그래머스 - 리코쳇 로봇 BFS + 조건이 붙은 문제였다. 문제를 읽고 예전에 했던 게임이 생각나서 재미있게 풀었다. 로직 먼저 board를 순회하며 아직 계산되지 않은 노드를 INF로 초기화 하고, 시작 지점과 도착 지점의 좌표를 저장한다. 시작지점에서 BFS 탐색을 시작하는데, 다른 점은 우선순위 큐를 사용한다는 것이다. 우선순위 큐를 이용하면 상하좌우 중 지금까지 가장 적은 방문 횟수를 가진 노드를 먼저 방문하게 되기 때문이다. 상하좌우를 선택하였다면, D를 만나거나 배열에 끝에 다다를때까지 계속 같은 방향으로 진행한다. 그리고 도착한 노드에 횟수를 더해주고 계속 탐색하면 된다. 최종 코드 import java.util.*; class Solution { static int[] dRow = {1, -1, 0, 0}; sta.. 공감수 0 댓글수 0 2023. 8. 1.
(Java) 프로그래머스 - 디펜스 게임 입력값이 매우 큰 편이었기 때문에 O(n) 이내에 끝내야겠다는 생각을 했다. 처음에는 내림차순으로 정렬을 하고 k를 우선적으로 사용하고, 나머지는 n을 사용하는 로직을 생각했다가 잘못된 로직이라는 것을 깨닫고 우선순위 큐를 이용하여 풀었다. 어떻게 생각하냐에 따라 엄청 간단한 문제일 수도 있지만, 내가 배배 꼬아서 생각했던지 풀이에 오랜 시간이 걸렸다. 로직 먼저 enemy 배열을 순회하며 n을 빼주고 우선순위 큐에 삽입한다. 만약 n이 음수로 내려간다면, 지금까지 지나왔던 라운드에 가장 큰 값이 우선순위 큐에 첫 번째 값으로 들어 있으니 그 값을 빼서 다시 n에 더해준다. 이렇게 하면 지나온 라운드 중 가장 큰 값에만 무적권을 쓰게 된 것과 같다. 더 이상 쓸 수 있는 무적권이 없다면 순회를 종료하면 .. 공감수 0 댓글수 0 2023. 7. 29.
(Java) 프로그래머스 - 광물 캐기 문제를 읽고 입력값이 크지 않아 완전탐색을 생각했었다. 백트래킹을 이용하면 어찌어찌 구현할 수 있겠다고 생각했지만, 그리 끌리지는 않았다. 주어진 순서대로 탐색을 해야 하고 가중치가 있기 때문에 그리디로 해결할 수 있다고 생각하여 도전한 결과 풀이에 성공했다. 로직 곡괭이가 없거나, 더 캘 광물이 없다면 종료해야 하므로 매 순회마다 종료 조건을 설정했다. 하나의 곡괭이는 5번을 사용할 수 있으므로 미네랄 배열을 5개씩 그룹을 만들어 탐색한다. 하나의 그룹을 각각 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이로 채굴했을 때의 피로도를 객체로 만들어 list에 넣는다. list안의 객체를 돌 곡괭이를 사용했을 때의 피로도를 기준으로 내림차순 정렬하고 가장먼저 다이아몬드 곡괭이부터 사용하고, 철 곡괭이를, 돌 곡.. 공감수 0 댓글수 0 2023. 7. 25.
(Java) 프로그래머스 - 미로 탈출 오랜만에 푸는 BFS 문제였다. 기본적인 BFS 문제에서 약간 더 생각을 해야했는데, 로직을 생각하는데 그리 오래 걸리지는 않았다. 로직 먼저, 탈출을 하기 위해서는 레버까지 가야한다. 그렇기 때문에 레버까지 BFS를 통해 최단거리 탐색을 진행한다. 레버에 도착하고 다시 한번 탈출지점까지 BFS 탐색을 하는데, 여기서 중요한것은 왔던길을 다시 갈 수도 있다는 것이다. 따라서 방문 배열을 초기화 하고 BFS 탐색을 진행해야 한다. 탈출 조건이 (시작지점에서 레버에 도달 && 레버에서 탈출지점까지 도달) 이므로 둘중 하나라도 만족하지 못하면 -1을 리턴해야 한다. 최종 코드 import java.util.*; class Solution { static int[] dRow = {-1, 1, 0, 0}; sta.. 공감수 0 댓글수 0 2023. 7. 22.
(Java) 프로그래머스 - 테이블 해시 함수 문제에 각 단계에 맞게 계산하는 쉬운 문제였다. 오랜만에 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, .. 공감수 0 댓글수 0 2023. 7. 19.
(Java) 프로그래머스 - 마법의 엘리베이터 처음에는 DP 문제라고 생각하고 풀었는데, 잘못된 접근이었다. 다음으로 storey를 String 배열로 바꾸어서도 풀어보았는데, 자리수가 늘어나는 예외를 처리하지 못했다. 마지막으로 storey를 나눠가는 방식으로 겨우 풀이에 성공했다. 로직 storey가 0이 될때까지 while을 돌린다. 매 roof 마다 가장 끝자리인 num과 num의 앞자리인 nextNum만 확인하면 된다. 왜냐하면 roof에 끝에서 10씩 나누어 주기 때문이다. num이 5보다 크면 현재 층수에서 올라가는것이 빠르고, num이 5보다 작으면 현재 층수에서 내려가는게 빠르다. num이 5라면 num의 앞자리 숫자를 확인해야 한다. 앞자리 숫자가 4보다 크면 올라가는게 빠르고, 작으면 내려가는게 빠르기 때문이다. 최종 코드 imp.. 공감수 0 댓글수 0 2023. 7. 13.
(Java) 프로그래머스 - 호텔 대실 문제를 보자마자 누적합을 이용하면 쉽게 풀수 있을것이라고 생각했다. 다만, 누적합을 어떻게 구현해야 하는지 잘 생각이 나지 않아 LocalTime 클래스를 이용해서 풀어보았으나, 테스트 케이스 통과를 하지 못하였다. 그래서 누적합에 대해 검색했고, 쉽게 풀 수 있었다. 로직 2차원 배열 book_time을 순회하며 방 입실 시간과, 퇴실 시간을 구한다. 퇴실 시간에 청소시간을 고려하여 10분을 더해주면 된다. arr 배열에 모든 입실시간과 퇴실시간을 더해주고, 누적합을 구하며 최댓값을 찾으면 된다. 최종 코드 import java.util.*; class Solution { public int solution(String[][] book_time) { int answer = 0; int[] arr = n.. 공감수 0 댓글수 0 2023. 7. 10.
(Java) 프로그래머스 - 우박수열 정적분 문제가 콜라츠 추측과 정적분이 같이 있어서 조금 읽기 어려웠다. 문제가 이해가 된다면 그리 어렵지 않은 문제였다. 인풋값이 작아서 시간 초과 걱정은 하지 않았고 완전 탐색으로 모든 넓이의 조합을 다 만들어 둘까 생각하다 너무 비효율적인 것 같아 배열을 돌면서 바로바로 넓이를 구했다. 로직 k가 1이 될때까지 나머지 숫자를 구하고 list에 추가한다. 그리고 정적분을 진행하면 되는데, 먼저 정적분의 범위를 구하고 시작 값이 끝 값보다 크다면 answer 배열에 -1을 추가하고 넘어간다. 시작 값이 끝 값보다 작다면 x의 크기를 1로 고정하고 사다리꼴의 넓이를 구하고 이를 sum에 추가한다. 사다리꼴의 넓이는 (윗변 + 아랫변) x 높이 / 2인데, 여기서 높이는 1로 고정되어 있으므로 (윗변 + 아랫변) .. 공감수 0 댓글수 0 2023. 7. 8.
(Java) 프로그래머스 - 연속된 부분 수열의 합 문제를 읽고 완전 탐색은 인풋값이 크기 때문에 당연히 시간 초과가 난다고 생각해서 배제했다. 부분 수열 문제에서 O(N) 로직을 가지는 건 투포인터와 슬라이딩 윈도우인데, 이번 문제는 정렬되어 있고, 부분 수열의 길이가 가변적이니 투포인터를 사용했고 문제 조건에 맞게 저번 카카오 문제에서 썼던 Comparator를 사용하여 정렬하고 값을 리턴했다. 오랜만에 투포인터를 써서 더듬거리며 풀었지만 꽤 재미있었다. 최종 코드 import java.util.*; class Solution { public int[] solution(int[] sequence, int k) { int[] answer = new int[2]; List list = new ArrayList(); int start = 0; int end.. 공감수 0 댓글수 0 2023. 5. 7.
(Java) 프로그래머스 - 이모티콘 할인행사 문제를 읽고 대략적인 로직은 빠르게 세워졌지만 구현에는 꽤 많은 시간이 소요되었다. 인풋 값이 크지 않아서 시간 초과는 생각하지 않고 풀었다. 먼저 가능한 할인 조합을 만들고 users 배열과 emoticons 배열을 순회하며 계산후 result 배열에 담고 정렬해주었다. 총 1시간 정도 걸렸는데 풀이 시간을 더 빠르게 하고 싶다... 최종 코드 import java.util.*; class Solution { static List list; static int[] dis = new int[] {10,20,30,40}; public int[] solution(int[][] users, int[] emoticons) { int[] answer = new int[2]; list = new ArrayList(.. 공감수 0 댓글수 0 2023. 5. 6.
(Java) 프로그래머스 - 택배상자 문제 설명부터 Stack을 쓰라고 말하는 것 같았다. 메인 컨베이어 벨트는 Queue로 서브 컨베이어 벨트는 Stack을 이용해서 풀이했다. 90% 풀이 금방 끝냈지만, while문의 종료 조건을 생각하느라 시간이 걸렸다. flag 변수를 이용해서 어떠한 작업도 하지 않는다면 while문을 종료시켜 풀이에 성공했다. 최종 코드 import java.util.*; class Solution { public int solution(int[] order) { int answer = 0; Stack stack = new Stack(); Queue queue = new LinkedList(); for(int i = 1; i 공감수 1 댓글수 0 2023. 5. 6.
(Java) 프로그래머스 - 롤케이크 자르기 문제가 간단하지만 시간 제한을 맞추는게 꽤 까다로웠다. 인풋값이 크기 떄문에 O(n^2) 로직은 무조건 시간 초과가 나고, O(n log n) 이내로 작성해야 된다고 생각해서 최종적으로 O(n) 로직으로 풀이에 성공했다. 실패 코드 import java.util.*; import java.util.stream.Collectors; class Solution { public int solution(int[] topping) { int answer = 0; for(int i = 1; i < topping.length; i++) { Set set1 = Arrays.stream(Arrays.copyOfRange(topping, 0, i)) .boxed() .collect(Collectors.toSet()); S.. 공감수 0 댓글수 0 2023. 5. 5.
(Java) 프로그래머스 - 숫자 변환하기 처음에는 DFS를 이용해서 탐색하는 로직을 시도했다. 그러나 너무 많은 재귀 호출로 인한 스택 오버플로우와 시간 초과가 났다. 최소횟수를 찾는것과 최단거리를 찾는것이 똑같다는 생각이 들어 BFS로 변경했다. 더이상 스택 오버플로우는 나지 않았지만 시간 초과가 나는건 똑같았다. 한참을 고민하다 방문 배열과 똑같은 역할을 하는 Set을 추가해서 문제를 해결할 수 있었다. 최종 코드 import java.util.*; class Solution { public int solution(int x, int y, int n) { int answer = 0; answer = bfs(x, y, n); return answer; } public int bfs(int x, int y, int n) { Queue queue.. 공감수 0 댓글수 0 2023. 5. 5.
(Java) 프로그래머스 - 뒤에 있는 큰 수 찾기 제한사항을 보고 O(n^2) 로직으로는 100% 시간 초과가 날 것이라고 생각했다. 그래서 O(n) Queue를 이용한 로직을 한참 고민했는데, 결국 해결하지 못해 검색을 통해 힌트를 얻어 해결했다. 최종 코드 import java.util.*; class Solution { public int[] solution(int[] numbers) { int[] answer = new int[numbers.length]; Stack stack = new Stack(); for (int i = numbers.length - 1; i >= 0; i--) { while (!stack.isEmpty()) { if(stack.peek() > numbers[i]) { answer[i] = stack.peek(); brea.. 공감수 0 댓글수 0 2023. 5. 4.
(Java) 프로그래머스 - 연속 부분 수열 합의 개수 처음에는 단순히 슬라이딩 윈도우를 사용해서 풀려고 시도했다. 그러나 부분 수열의 크기가 고정되어 있지 않아서 풀이에 많은 시간이 걸렸다. 최종 코드 import java.util.*; class Solution { public int solution(int[] elements) { int answer = 0; // 부분 수열 크기 int size = 1; Set set = new HashSet(); // 부분 수열 크기가 elements 길이가 될때까지 반복 while (size 공감수 0 댓글수 0 2023. 4. 28.
(Java) 프로그래머스 - 공원 산책 추가된 1단계 문제중 가장 정답률이 낮은 문제였다. 전형적인 그래프 탐색 문제였는데, 한칸씩 이동하며 조건을 검사해야 했지만 한번에 n칸씩 이동한다는걸 뒤늦게 깨닫고 수정하느라 풀이 시간이 많이 늘어났다. 최종 코드 import java.util.*; class Solution { static int startX; static int startY; public int[] solution(String[] park, String[] routes) { int[] answer = new int[2]; // 동서남북 이동할 좌표 map에 삽입 Map map = new HashMap(); map.put("N", new int[]{-1, 0}); map.put("E", new int[]{0, 1}); map.put(.. 공감수 1 댓글수 0 2023. 4. 26.
(Java) 프로그래머스 - 개인정보 수집 유효기간 카카오 문제치고 쉬운 문제였다. 인풋 값도 적어서 시간 초과를 생각하지 않고 편한 마음으로 풀었다. Date와 SimpleDateFormat를 이용해서 계산하는 방법도 생각했지만 그냥 계산하는게 더 간단해 보여서 사용하지는 않았다. 로직 먼저 terms 배열을 순회하며 map에 약관종류와 유효기간을 넣어준다. 그리고 privacies를 순회하며 약관 종류에 맞는 유효기간을 가져와 cal 메서드를 호출한다. 유효기간이 1이 될 때까지 날짜를 계산하여 년월일을 일자로 바꾸어 현재 날짜와 비교한다. cal 메서드의 반환값이 false이면 list에 추가하고 모든 순회가 끝나면 stream을 이용해 배열로 변환한다. 최종 코드 import java.util.*; class Solution { public int.. 공감수 0 댓글수 0 2023. 4. 25.
(Java) 백준 15652 - N과 M (4) 문제 분류가 백트래킹으로 되어 있지만 그냥 재귀를 생각하면서 풀었다. 재귀 탈출문이 실행되고 리턴되면 idx++로 증가시켜 조건에 맞게 문자열을 만들었는데 이걸 백트래킹이라고 볼 수 있는지는 잘 모르겠다... 로직 스트림을 사용하기 위해서 입력을 int 배열을 이용해서 받았는데 , 사실 n, m 변수 하나씩 만들어서 받는 게 편할 수도 있다. n과 m을 받았다면 재귀 함수를 호출해서 문자열 조합을 만든다. 재귀 호출마다 depth를 증가시키고 depth가 m과 같으면 substring을 사용해서 문자열 앞 공백을 제거하고 문자열을 stringBuilder에 추가하고 리턴한다. 문제 조건에 맞추기 위해서 리턴후에는 idx를 증가시키고 모든 조합이 나올 때까지 재귀 호출을 반복하면 된다. 최종 코드 impo.. 공감수 0 댓글수 0 2023. 2. 17.
(Java) 프로그래머스 - 둘만의 암호 문제 해결 로직은 쉬웠지만 깔끔하게 풀지는 못한 것 같다. 스트림을 이용하면 조금 더 보기 좋게 코드를 작성할 수 있을 것 같은데 아직 스트림이 익숙하지 않다.. 로직 제시된 String을 char 배열로 바꾸고 contains() 메서드를 이용하기 위해 skipArr을 list에 넣어준다. arr 배열을 순회하며 문자를 다음 문자로 바꾸어 'z' 이후 문자인지 확인하여 이후 문자라면 'a'로 바꿔준다. 그리고 list에 넘어가야할 문자가 있는지 확인한다. 바꾼 문자가 list에 있다면 cnt를 증가시키지 않고 넘어가고, 없다면 cnt를 증가시켜 cnt가 index와 같아질 때까지 문자를 바꾼다. 마지막으로 바꾼 문자를 StringBuilder에 추가하면 된다. 최종 코드 import java.util... 공감수 0 댓글수 0 2023. 2. 16.
(Java) 프로그래머스 - 카드 뭉치 마스터즈 코스를 진행하며 CS 공부하기에도 시간이 너무 부족하지만 하루에 한 문제씩 알고리즘 문제 풀기를 다시 시작하려고 한다. 요즘 프로그래머스에 문제들이 많이 추가되고 있다. 예전에 프로그래머스 2단계 문제까지 전부 다 풀었었는데 추가된 문제가 많아서 전부 다 풀어보고 3단계로 가야겠다! 로직 사실 문제가 너무 간단해서 로직을 크게 생각하지 않았다. goal 배열을 순회하면서 cards1 배열과 cards2 배열을 동시에 탐색하면 된다. 각 cards 배열의 인덱스를 만들고 배열의 크기를 벗어나지 않으면서 goal 문자와 같으면 인덱스를 추가하고 다음 문자로 넘어간다. 만약 어떤 cards 배열의 어떤 문자도 일치하지 않으면 바로 No를 리턴해서 탐색을 종료한다. 모든 탐색이 종료되면 문자열을 만들 .. 공감수 1 댓글수 0 2023. 2. 16.
(Java) 프로그래머스 - 베스트앨범 한번에 로직이 세워지지 않았던 문제이다. HashMap에 익숙해졌다고 생각했지만 values를 기준으로 내림차순 정렬하는데 어려움을 겪었다. 로직 먼저 genres와 play값을 HashMap에 넣어 각 장르별 플레이 횟수를 센다. 그리고 keySet을 리스트에 넣어 플레이 횟수별로 내림차순 정렬한다. 정렬된 list의 값을 순회하면서 첫번째와 두번째로 많이 재생된 노래의 인덱스를 result 리스트에 넣고 마지막으로 배열로 복사해서 반환하면 된다. 최종 코드 import java.util.*; class Solution { public int[] solution(String[] genres, int[] plays) { List result = new ArrayList(); // 각 장르별로 HashMa.. 공감수 2 댓글수 0 2022. 10. 20.
(Java) 프로그래머스 - 단속카메라 오랜만에 문제를 읽고 어떻게 풀어야 하는지 감이 오지 않았다. 문제 유형이 그리디로 분류되어 있었지만, 로직 자체가 생각나지 않았다. 결국 고민하다가 검색을 통해서 힌트를 얻었다. 로직 이 문제의 키포인트는 정렬이다. 각 자동차의 진출 시간인 routes [i][1] 값을 기준으로 정렬하면 문제를 쉽게 해결할 수 있다. 왜냐하면 n번째 자동차의 진출시간과 n+1 자동차의 진입시간을 비교해 n+1번째 자동차의 진입시간이 n번째 자동차의 진출 시간 이전이라면 카메라의 숫자를 늘릴필요가 없어 다음 차량으로 넘어가면 되고, n+1번째 자동차의 진입시간이 n번째 자동차의 진출 시간 이후라면 min의 값을 바꾸고 카메라의 숫자를 +1 하면 되기 때문이다. 최종 코드 import java.util.*; class S.. 공감수 0 댓글수 0 2022. 10. 17.
(Java) 프로그래머스 - 등굣길 문제를 읽고 DFS / BFS로도 풀 수 있겠다는 생각을 했다. 그런데 문제 유형이 DP로 분류되어 있어서 시간 초과가 나지 않을까 싶어서 DP로 풀수 있는 방법을 생각해서 해결했다. 로직 먼저 m x n인 arr 배열을 만들고 웅덩이를 -1로 초기화한다. 그리고 첫 번째 행과 열이 아니면 이전 행과 열의 값을 더하며 탐색을 진행한다. 최종적으로 마지막 행과 열에는 도달할 수 있는 방법의 개수가 값으로 들어있게 된다. 최종 코드 class Solution { public int solution(int m, int n, int[][] puddles) { int answer = 0; // n x m 배열 초기화 int[][] arr = new int[n][m]; // 시작점은 1 arr[0][0] = 1; .. 공감수 0 댓글수 0 2022. 10. 17.
(Java) 프로그래머스 - 단어 변환 DFS / BFS 둘 중 편한 것을 선택해서 풀 수 있는 문제였다. DFS가 더 편해 보여서 DFS를 이용해서 풀었는데 로직을 설계하는 게 어려워서 꽤 고민하며 풀었었다. 테스트 케이스도 5개밖에 되지 않고, 입력값이 크지 않아서 수행 시간은 생각하지 않고 풀었다. 로직 먼저 words와 동일한 크기로 방문 배열을 초기화한다. 다음으로 target 문자열이 words 배열에 있는지 검사한다. target 문자열이 words에 없다면 바로 0을 반환하고 탐색하지 않는다. 그리고 DFS 탐색을 시작하는데 begin 문자열이 target 문자열과 몇 글자가 다른지 확인한다. 만약 한 글자만 다르다면 한 번만 변환하면 되므로 리스트에 cnt + 1 값을 저장한다. 한 글자 이상이 다르다면 words 배열을 순회.. 공감수 0 댓글수 0 2022. 10. 11.
(Java) 프로그래머스 - 혼자 놀기의 달인 문제가 잘 이해되지 않아서 몇 번을 읽었다. 이해하고 보니 결국 연결되어 있는 노드의 개수를 저장하고 최댓값 2개를 꺼내서 곱을 반환하면 되는 문제였기에 DFS를 이용해서 풀이했다. 로직 cards 배열의 크기가 처음 선택하는 카드의 숫자이기 때문에 visited 배열의 크기를 n으로 설정한다. 첫 번째 상자부터 n번째 상자까지 순회하며 방문하지 않았다면 DFS 메서드를 호출하고 재귀 탐색한다. 열었던 상자까지 도달하면 상자의 개수를 우선순위 큐에 넣고 리턴한다. 모든 순회가 끝나면 우선순위큐의 첫 번째 두 번째 값을 곱해서 answer를 반환한다. 이때 우선순위큐의 사이즈가 1이면 첫 번째 상자 그룹 하나밖에 없다는 의미임으로 0을 반환한다. 최종 코드 import java.util.*; class S.. 공감수 1 댓글수 0 2022. 10. 7.
(Java) 프로그래머스 - 할인 행사 새롭게 나온 레벨 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; //.. 공감수 0 댓글수 0 2022. 10. 7.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.