문제 https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 풀이 정말 어려웠지만 재밌는 문제였다. 풀이법이 잘 생각나지 않지만 생각만 잘한다면 코드 길이가 매우 짧고 명료하게 해결할 수 있다. 이 문제는 DP를 이용하면 해결할 수 있다. 나는 DP 배열을 다음과 같이 정의했다. DP[0][i][j] = (i,j) 좌표에 세로로 들어오는 경우의 수 DP[1][i][j] = (i, j) 좌표에 가로로 들어오는 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 풀이 이 문제는 정말 재밌는 문제였다. 문제에 나온대로 그냥 덧셈을 모두 하게 되면 시간초과가 발생할 수 밖에 없다. N*M배열에 K개의 명령이 있을 때 O(KNM)이라는 시간복잡도가 발생하기 때문이다...
문제 https://programmers.co.kr/learn/courses/30/lessons/72413?language=java 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 이 문제는 접근법만 알면 간단한 문제이다. 예전..
문제 https://programmers.co.kr/learn/courses/30/lessons/72412?language=java HTML 삽입 미리보기할 수 없는 소스
문제 https://programmers.co.kr/learn/courses/30/lessons/72410?language=java 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 풀이 문제에 주어진대로 구현하면 되는 아주 간단한 문제이다. 코드를 보면 충분히 이해할 수 있다. 코드 class Solution { public String solution(String new_id) { // 1단계 String answer = new_id.toLowerCase(); // 2단계 String temp = "..
문제 https://programmers.co.kr/learn/courses/30/lessons/60063?language=java 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 풀이 나는 이 문제를 조금 복잡하게 푼 것 같다. 우선 Robot 클래스를 만들어서 x좌표와 y좌표, 현재 방향(0은 가로 1은 세로), 걸린 시간을 저장하게 만들었다. 참고로 방향이 가로일 때 x, y는 왼쪽 좌표 기준, 세로일 때 x, y는 위쪽 좌표를 기준으로 한 것이다. 이후 탐색은 BFS를 통해서 모든 경우의 수를 따지면 된다. 이때 상하좌우로 움직이는..
문제 https://programmers.co.kr/learn/courses/30/lessons/60059?language=java 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 풀이 이 문제는 배열을 확장시켜서 풀면 쉽게 해결할 수 있다. 위와 같이 배열을 확장시켜서 차례대로 자물쇠와 키를 맞춰보면 된다. 이때 배열을 얼마나 확장시켜야 할까? 잘 보면 "자물쇠의 길이 + (키의 길이*2) - 2"만큼 확장시키면 된다는 것을 알 수 있다. 따라서 해결 과정은 다음과 같다. 1. "자물쇠의 길이 + (키의길이*2) - 2" 크기의 배열 map[][]을 만든다..
문제 https://programmers.co.kr/learn/courses/30/lessons/60058?language=java 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 풀이 간단한 구현 문제로 정말 문제에서 시키는 대로 함수를 작성하면 끝이다. 자세한 내용은 코드를 참고하자. 코드 import java.util.*; class Solution { public String solution(String p) { String answer = dfs(p); return answer; } public sta..
문제 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 이 문제는 간단한 구현 문제이다. 문자열을 압축할 zip 함수를 만들어 해결하였다. 1개씩 묶는 것부터 s의 길이까지 묶는 갯수를 늘려서 가장 짧은 길이로 압축 되는 것을 확인 하면 된다. 코드 import java.util.*; class Solution { public int solution(String s) { int answer = 1000000; for(int i=1; i 1){ ret += String.valueOf(cnt) + pr..
문제 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 이 문제는 트리의 성질에 대해 잘 안다면 쉽게 해결할 수 있는 문제이다. 직접 이진트리를 구현하여 전위 순회, 후위 순회로 트리를 탐색하기만 하면 된다. 이때 이진트리를 구현하기 위해 Node 구조체를 만들어야 한다. 이후 y좌표가 큰 순서대로, y좌표가 같다면 x좌표가 작은 순서대로 정렬하여 저장한 리스트를 탐색하면서 이진트리를 구성하면 된다. 자세한..