알고리즘

[Java] 프로그래머스 Lv2 - [3차] 압축 (2018 KAKAO BLIND RECRUITMENT)

🔗 문제링크 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 📂 분류 구현 💡 풀이 문제 설명에 나와 있는 LZW 압축 과정을 구현하면 되는 문제이다. 접근 방식 A ~ Z까지 HashMap을 이용해 초기화를 한다. 현재 단어 w와 다음 단어 c를 받는다. w + c가 map에 저장되어있는지 확인하고, 저장되어있다면 continue로 건너뛰어 위 과정을 다시 진행한다. w + c가 없다면, w 값을 출력하고 map에 저장한 다음 w를 초기화시켜준다. 💻 코드 import java.util.ArrayList; import java.u..

[Java] 프로그래머스 Lv2 - 3 x n 타일링

🔗 문제링크 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 📂 분류 DP 💡 풀이 이 문제는 2 x n 타일링을 응용한 문제이다. 세로 길이가 3인 바닥이기 때문에 n이 홀수 일 경우 타일 배치를 하지못한다. 처음 점화식은 dp[i] = dp[i - 2] * 4 - dp[i - 4]로 쉽게 구해졌으나 나머지 연산에 문제가 있어서 이 점화식으로는 문제를 해결하지 못했다. 다른 점화식을 구하려고 고민을 했으나 생각이 나지않아 풀이법을 참고해서 풀었다. 점화식은 다음과 같다. tiles[i] = tiles[i - 2] * 3 + tiles[i - 4] * 2 + tils[i - 6] * 2 ... 💻 코드 public class Solution { private static final ..

[Java] 프로그래머스 Lv2 - 2 x n 타일링

🔗 문제링크 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 📂 분류 DP 💡 풀이 2 x n 타일링 문제는 메모이제이션을 대표하는 문제이다. 이 문제는 bottom-up 방식과 top-down 방식 두 가지로 해결할 수 있는데, 나는 bottom-up 방식으로 접근하여 문제를 해결했다. 접근 방식 n이 1일 경우 가로로만 배치할 수 있기 때문에 배치할 수 있는 경우는 한 가지만 존재한다. n이 2일 경우 가로로 배치하고 세로로도 배치할 수 있기 때문에 배치할 수 경우는 두 가지가 존재한다. n이..

[Java] 프로그래머스 Lv2 - 가장 큰 정사각형 찾기

🔗 문제링크 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 📂 분류 DP 💡 풀이 DP Bottom-up 방식으로 해결되는 문제이다. 접근방식 정 사각형의 넓이를 구하는 문제이기 때문에 왼쪽, 위쪽이 하나라도 0이라면 넓이는 1이 된다. 따라서 점화식은 아래와 같이 나온다. cache[i][j] = Math.min(cache[i - 1][j - 1], Math.min(cache[i - 1][j], cache[i][j - 1])) + 1; 💻 코드 public class Solution { private int[][] cache; public int solution(int[][] board) { in..

[Java] 프로그래머스 Lv2 - [3차] 방금 그 곡 (2018 KAKAO BLIND RECRUITMENT)

🔗 문제링크 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 💡 풀이 문자열 스플릿처리 한 후 문제를 해결하는 문제이다. 접근 방식 음 코드를 분리하기 위해 'C#', 'D#, 'F#', 'G#', 'A#' 를 'c', 'd', 'f', 'g', 'a' 로 바꿔준다. 재생 시간과 멜로디의 길이를 맞춰준다. 재생 시간, 음악 제목, 멜로디 정보를 클래스 객체로 만들어 리스트에 저장한 후 재생 시간 내림차순으로 정렬한다. 💻 코드 import static java.lang.Integer.parseIn..

[Java] 프로그래머스 Lv2 - 방문 길이

🔗 문제 코딩테스트 연습 - 방문 길이 programmers.co.kr 💡 풀이 해당 문제는 문제 설명대로 구현하면 되는 문제이다. 접근 방식 '원래 좌표 -> 움직인 좌표'와 '움직인 좌표 -> 원래 좌표'를 String에 저장하여 Set에 저장한다. 양방향으로 저장했기 때문에 Set.size / 2를 반환한다. 💻 코드 import java.util.*; public class Solution { private static final int MAX = 5; private static final int MIN = -5; Set visited = new HashSet(); Map map = new HashMap(); public int solution(String dirs) { int y = 0; int..