본문 바로가기

프로그래머스28

[자바] 프로그래머스 - 도둑질 (코딩테스트 연습 Lv4) 문제 : Programmers-도둑질 레벨 4라 보기엔 프로그래머스의 다른 레벨4 문제에 비해 너무 쉽다. DP가 개인적으로 내 최대 약점이라 생각하는데도 금방 점화식이 생각날 정도니 2~3정도가 적당할 것 같다. 레벨4 스킬 체크 딸 때 이거 나왔으면 더 꿀이었을 것 같다. 일단 점화식은 간단하다. dp[i]를 i번 집을 털 때 얻을 수 있는 최대 돈이라 하면 아래와 같이 세울 수 있다. 즉, 현재 i번 집을 털 때 얻을 수 있는 최대 돈은, 이전집을 털고 현재집을 털지 않는것과 이전으로 2번째 집을 털고 이번 집도 터는 것 중 max값을 선택하면 된다. 이렇게 하면 '100 1 1 100' 처럼 중간에 두 집을 건너띄고 털어야 하는 것 까지 한번에 해결된다(세 집을 건너띄는 경우는 없다. 그 경우라면.. 2022. 4. 21.
[자바] 프로그래머스 - 타겟 넘버 (코딩테스트 연습 Lv2) 문제 : Programmers-타겟넘버 결국 주어진 numbers를 순서대로 + 한번, - 한번씩 모든 경우를 구해보면 된다. 이 경우 O(2^n)이 된다(+,-의 2가지 경우를 n번 봐야 하므로). 예를들어 numbers가 [1, 2, 3]일 경우 다음과 같이 진행된다. 이 중 target과 동일한 경우를 세서 return해주면 된다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges */ class Solution { int cnt = 0; private void rec(int[] numbers, int target, int idx, int sum) { if (idx == numbers.length.. 2022. 4. 18.
[자바] 프로그래머스 - 가사 검색 [코딩테스트 연습 Lv4] 문제 : Programmers-가사검색 트라이(Trie) 개념으로 구현하면 된다. 내 경우 words에 들어있는 String으로 트라이 트리를 구성했는데, 각 길이마다 별도로 앞에서 부터 진행한 트리와 뒤에서 부터 진행한 트리를 둘 다 구성했다. 만약 '*' 같은것도 있으면 길이마다 구성한게 의미가 없었을테지만, 이 문제의 경우 queries의 길이가 고정되어 있으므로 길이마다 별도로 구성하는 것이 더 빠르게 연산할 수 있다. 또한 '?'가 접미사 혹은 접두사에 있으므로 둘 다 찾기 위해서는 앞에서 부터 구성한 트라이와 뒤에서 부터 구성한 트라이 둘 다 유지해야 한다. 접미사에 '?'가 있다면 뒤에서 부터 구성한 트라이 트리를 봐야 하고, 접두사에 있다면 앞에서 부터 구성한 트라이 트리를 봐야 한다. 추.. 2022. 4. 10.
[자바] 프로그래머스 - 모의고사 [코딩테스트 연습 Lv1] 문제 : programmers-모의고사 주어진 대로 구현을 하면 된다. 반복문과 배열만 다룰 줄 안다면 풀 수 있다. 이 때 1번, 2번, 3번 수포자의 공통된 부분의 길이가 서로 다른 부분(각각 5, 8, 10)에서 좀 어려울 수 있다. 각자 다른 index 변수를 사용해서 해당 배열의 크기가 됬다면 0으로 변경하는 방식으로 하거나, 3명의 공통부분 길이의 최소공배수인 40번 만큼 배열에 적어둔 후 풀면 쉽게 할 수 있다. 코드적으로 이해가 될 것 같다면 아래와 같이 %(나머지 연산)를 사용해 더 편하게 할 수 있다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges */ class Solution .. 2022. 4. 8.
[자바] 프로그래머스 - 체육복 [코딩테스트 연습 Lv1] 문제 : programmers-체육복 1. '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.' 부분부터 처리해야 한다. lost와 reserve에 동시에 포함되는 항목이 있다면 양쪽에서 제거해서, '2' 이후의 로직에 영향을 끼치면 안된다. 2. +-1인 학생한테 체육복을 빌릴 수 있으므로 무지성으로 lost 기준으로 +-1 학생한테 빌릴 수 있으면 바로 빌리고, reserve에서 제거하면 된다. 뭐 오름차순으로 -1인 학생부터 빌리고 이런 과정이 필요 없다. 만약 +-2 이상으로 빌릴 수 있었다면 누가 누구한테 빌리는지에 따라 빌릴 수 있는 학생의 수가 변경될 것.. 2022. 3. 23.
[자바] 프로그래머스 - 순위 [코딩테스트 연습 Lv3] 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%203/%EC%88%9C%EC%9C%84.java 방향 그래프로 표현할 수 있는 문제의 경우 일단 그래프로 그려보면 답이 보이는 경우가 많다. 따라서 일단 무지성으로 그려봤다. 그럼 길찾기 처럼 거리를 한번 재보자! 정확힌 어디까지 갈 수 있는지만 알 수 있으면 된다. arr[i][j]를 대해 i번에서 j번까지의 거리라고 생각하고 표를 작성하면 아래와 같다. 그럼 이쯤에서 이 문제를 풀 수 있는 아이디어를 찾을 수 있다. 저기 '5'의 경우 4명한테 져서 순위가 확정됬.. 2021. 11. 12.
[자바] 프로그래머스 - 위장 [코딩테스트 연습 Lv2] [ 문제 링크 ] [ 코드 링크 ] 문제 출처 : 프로그래머스 코딩 테스트 연습 각 의상 종류에 해당하는게 몇 가지씩인지만 알면 된다. 이 때 의상 이름의 경우 '같은 이름을 가진 의상은 존재하지 않습니다.' 에 따라 의미가 없으므로 버려도 된다. 즉, 예제1의 경우 의상 이름은 필요없고 아무튼 headgear 2 eyewear 1 라는 점만 알면 되며, 사실 종류명도 별로 상관없다. 동일한지만 hashing을 통해 확인할 수 있으면 된다. 그럼 계산은 어떻게 해야하냐면, 옷이 2종류라고 치면 2칸을 둬보자. 'ㅇㅇ' 첫번째 칸은 headgear를 입거나 입지 않을것이고, 2번째칸은 eyewear를 입거나 입지 않을 것이다. 그럼 경의의 수는 (2+1) * (1+1) 이 된다. 여기서 +1은 '입지 않는.. 2021. 11. 8.
[자바] 프로그래머스 - 지형 이동 [코딩테스트 연습 Lv4] - 문제 : https://programmers.co.kr/learn/courses/30/lessons/62050 - 코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%204/%EC%A7%80%ED%98%95%20%EC%9D%B4%EB%8F%99.java 1. 모든 칸을 방문한다고 했지, 한 칸에 여러번 가면 안된다는 말은 없었다. 따라서 높이차이가 height 이하인 곳은 가중치 0으로, 아무런 제약 없이 돌아다닐 수 있다. -> 다시 말해, 상하좌우로 높이차이가 height 이하인 곳은 서로 그룹으로 생각해도 됨. -> 예를들어 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, .. 2021. 9. 29.

티스토리툴바