꽤나 재밌어 보이는 문제여서 선택했지만 2단계 문제 치고 어렵다는 느낌이 들었다. 지금까지 풀어본 문제 중에 가장 구현 난이도가 높았던 것 같다. 그래서인지 이번에는 입력값을 n과 m을 30 이하, 블록은 A~Z 까지로 제한 시간을 넉넉하게 준 것 같다. 입력값이 크지 않으니 실제 코드를 작성할 때도 우당탕 3중 for문까지 돌려가면서 풀었던 것 같다. 설계는 간단하지만 생각해야 할 포인트가 꽤 있다. 1. 제거할 블록은 한 번에 제거해야 한다. 2, 제거할 블록이 겹친다면 겹쳐지는 부분은 한 번만 카운팅 되어야 한다. 3. 블록을 아래로 떨어트리는 로직을 생각하는 것이 쉽지 않다. 내가 생각한 로직은 1. 제거할 블록의 좌표를 찾는다. 나는 3중 for문을 이용해서 모든 i, j값을 돌며 오른쪽, 아래..

처음에는 완전 탐색으로 구현해야 하나 생각했다. 그런데 생각해보니 매 실행마다 각 큐의 합계를 비교하면 답이 나올 것 같았다. 그래서 그리디 알고리즘을 사용해서 코드를 작성했다. 처음 작성한 코드는 실제로 큐를 2개 생성해서 삽입과 삭제를 반복하며 체크하는 로직이었다. sumQ1나 sumQ2 값이 target 값과 같아질 때까지 while문을 돌린다. 그리고 q1Clone을 만들어서 q1이 처음과 같아지면 한 바퀴를 돌아도 답을 못 찾은 것이기 때문에 answer를 -1로 설정하고 탐색을 그만두게 했다. 그런데 이 코드는 테스트 케이스 11번에서 시간 초과로 계속 실패했다. 실제 queue에 삽입과 삭제를 반복하는데 시간이 꽤 걸렸던 것 같고 while문 조건을 변경하거나 break 조건을 만들면 통과될..

저번 카카오 공채 시험에서 나왔던 문제이다. 그때는 시간이 부족해서 대강 로직만 생각하고 풀지 못했었다... 이번에는 코드 작성에 40분 정도 걸렸고 주차 요금을 계산하는 방식을 잘못 이해해서 수정에 20분, 런타임 에러가 계속 나서 디버깅하는데 20분이 걸렸다. 충분히 풀 수 있는 문제이지만 풀이 시간이 발목을 좀 잡는 것 같다. 구현을 얼마나 빠르게 하는지가 관건인데... 역시 연습밖에 답이 없는 것 같다. 필요한 알고리즘이 없어서 문제에서 요구한 대로 구현하면 된다. 내가 잘못 이해했던 포인트는 주차 요금 계산은 모든 입력이 끝나고 한번에 계산해야 한다는 것이다. 처음에는 이 조건을 잘못 이해해서 출차가 일어날때마다 요금 계산을 했는데 이렇게 하면 테스트 케이스 1번에 0000 차량은 34분 - 5..

카카오 문제답게 지문이 길고 조건이 많은 편이어서 문제를 이해하는데 시간이 조금 걸렸다. 로직은 완전 탐색으로 모든 중복 조합을 만들고 점수를 계산해서 라이언이 이기는 경우 info2 배열을 반환한다. 먼저 라이언이 쏜 화살을 result 배열에 넣는다. 화살은 n번 쏠 수 있으므로 result 배열을 n으로 초기화한다. 그리고 중복 조합 메서드인 com을 호출한다. 예를 들어, n이 9라면 만들어진 조합은 {0,0,0,0,3,5,9,10,10}와 같이 만들어질 것이다. 이 배열의 값이 의미하는 것은 9번의 기회에서 0번째 과녁을 4번, 3번째 과녁 한번, 5번째 과녁 한번 9번째 과녁 한번, 10번째 과녁 2번을 맞췄다는 의미이다. 이것을 info 배열의 형식으로 바꾸면 0번째 과녁은 10점이므로 {4..

카카오 레벨 1 문제가 새로 생겼길래 풀어보았다. 문제의 로직이 복잡하지는 않지만 구현에 시간이 좀 걸리겠다고 생각했다. 30분이면 풀 수 있을 것이라고 느꼈는데 한 시간이 걸렸다. 로직은 각 지표별 배열을 생성하고 List안에 Map을 만들어 초기화한 후 설문 결과에 맞게 Map의 value를 업데이트하는 것으로 생각했다. 설문 결과에 따라 유형별 점수 판별을 switch문을 사용하여 해결했다. switch문을 쓰지 않고도 가능할 것 같기도 한데 빨리 풀고 싶어서 그냥 사용했다. Map 사용에 꽤나 익숙해졌다고 생각했는데 아직 자유롭게 사용하지는 못하고 있는 것 같다. 다른 사람들 코드를 보면 내가 좀 복잡하게 푼 것 같다.... 최종 코드 import java.util.*; class Solution..

처음에 문제의 2번째 조건을 읽지않아서 스택으로 풀면 되겠다고 생각하여 풀었다. 그런데 테스트 케이스 이외에는 다 틀렸다... 만약 두번째 조건이 없었다면 간단한 문제였을것이다. 성공 코드는 재귀를 이용해서 풀었다. 코드 자체는 간단하지만 은근히 생각할게 많았던 문제였다. 2번째 조건이 있으므로 1번 기둥에서 3번 기둥으로 바로 이동하지 못한다. 2번 기둥을 경유해서 가야 하는데 2번 기둥으로 가기 위해서는 3번 기둥을 먼저 이용해야 한다. 그리고 2번 기둥에서 3번 기둥으로 이동할때 1번 기둥을 이용해야 한다. 실패 코드 import java.util.*; class Solution { public int[][] solution(int n) { List list = new ArrayList(); Sta..

백트래킹을 사용해야 하는 유명한 문제이다. 어떻게 푸는지는 대강 알고 있었는데 실제로 풀어본 적이 없어서 풀어봤다. 2차원 배열 arr과 visited를 이용해서 문제를 풀어보려고 시도했는데 뭔가 코드만 복잡해지고 생각한 것처럼 구현이 되지 않았다. 1시간을 시도하다가 검색하니 2차원 배열을 1차원 배열로 압축해서 풀이가 있어 간단하게 풀었다. 2차원 배열을 이용해도 풀 수 있을 것 같은데 다시 풀어봐야겠다. 최종 코드 class Solution { static int[] arr; static int cnt; public int solution(int n) { int answer = 0; // 2차원 배열을 1차원으로 압축 -> 인덱스를 행, 값을 열로 보는것 arr = new int[n]; // Bac..

문제를 읽고 최단거리를 탐색하는 내용이기에 BFS로 해결할 수 있을줄 알았는데 많은 어려움을 겪었다. BFS 코드를 작성하다가 검색을 통해 힌트를 얻었고 다익스트라나 플로이드 와샬을 사용할 수 있다는 것을 알아서 모든 방법으로 풀어봤다. 다익스트라와 플로이드 와샬은 처음 배우는 알고리즘이여서 어려웠다. 이 문제는 하나의 정점에서 다른 정점들의 최단 거리임으로 다익스트라로 접근하는것이 가장 맞는것 같다. 다익스트라와 플로이드 와샬을 모른다면 잘 정리해놓은 다른분의 블로그를 첨부한다. [알고리즘/ 그래프] 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) (JAVA) 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) Dijkstra 알고리즘은 하나의 정점..

레벨 2 치고는 너무 쉬운 문제였다. 이게 왜 레벨 2에 있는지 모를 정도로... 예전에 백준에서 비슷한 문제를 풀어봐서인지 문제를 보자마자 DP로 풀었다. 거리가 1일 때는 뛰는 방법이 1칸 이동 - 1가지 거리가 2일 때는 뛰는 방법이 (1칸 이동, 1칸 이동), (2칸 이동) - 2가지 거리가 3일 때는 뛰는 방법이 (1칸 이동, 1칸이동, 1칸 이동), (1칸이동, 2칸이동), (2칸이동 1칸이동) - 3가지 따라서 dp [i] = dp[i-1] + dp[i - 2]이라는 점화식이 바로 나온다. 오버플로우 때문에 dp [i]을 구할 때마다 1234567로 나눈 나머지를 해줘야 한다. n이 1인 경우 런타임 에러가 나서 따로 빼주었다. 최종 코드 class Solution { public long ..