문제https://www.acmicpc.net/problem/12865 풀이 [Algorithm] 동적 계획법(Dynamic Programming)작성 이유 [Programmers] 완전범죄 - Java문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제 좀 어려웠다...처음에는 이gretea5.tistory.com을 참고해서 풀이를 작성하겠다. 1. 어려운 문제가 될 수 있는 요소 찾기물건무게(w)가치(v)준서가 넣는 물건들 중 k 이하의 무게로 넣었을때 얻을 수 있는 최대의 가치이다.결국 어려운 문제가 되려면 물건을 고르고, 최대 무게(w)가 되었을때가 어려운 문제라고 말할 수 있을 것이다.최대 ..
Problem Solving
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이wallpaper에 있는 문자열의 문자들중 #이 있는 것이 파일이 있는 칸인데, 드레그 할 수 있는 최소 영역을 구하는 문제이다. 프로그래머스 예제에 있는 이 그림을 보자 파일이 있는 위치를 좌측 상단에 있는 좌표 생각하면 패턴이 보이기 시작한다.여기에서, 드레그를 시작하는 위치는 파일 위치들 중 x, y 좌표가 가장 작은 값이라는 것이 보였고, 드레그가 끝나는 위치는 파일 위치들 중에 x, y 좌표가 가장 큰 값을 가진다는 것이 보였다.이 두가지를 모두 봐도, 생각한 패턴이 일치한다는 것을 알 수 있다. 1. 드레그 시작 좌표를 드레그 끝 좌표를 초기화한..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이풀이(큐)현재 이 문제에서 큐를 이용한 풀이를 이용했다.1. 큐를 2개 선언해서, cards1, cards2에 대한 문자열들을 담는다.2. goals에 있는 문자열을 하나 꺼내서, 각 큐에 있는 peek 연산을 통해 문자열이 일치한지 확인한다.3. 일치하지 않으면 isPossible에 false를 넣고 for문을 빠져나간다.4. isPossible에 해당하는 문자열을 반환한다. 소스코드(큐)import java.util.ArrayDeque;class Solution { public String solution(String[] cards1, String..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이최신에 나왔던 인덱스를 기록해야한다. 최신에 나왔던 인덱스를 기록하기 위해, HashMap을 사용했다. 여기에서 보면, 디폴트 크기로 16개의 양을 생성한다고 되어있다.알파벳의 전체 갯수는 26개이지만, 26개의 key(a ~ z)를 저장한 int 배열을 모두 저장할 필요는 없다고 생각이 들어서, HashMap을 사용했다. 1. HashMap에서는 (문자, 정수) 쌍으로 현재 문자가 나온 최신 인덱스를 기록한다.2-1. HashMap key에 문자가 없을 경우, 처음 나온 것이므로, -1을 넣어준다.2-2. HashMap key에 문자가 있을 경우, 현재..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이그리디 유형의 문제이다.1. 색칠하는 횟수를 최소화하려면, 색칠된 부분을 다시 색칠할 필요가 없다는 것이라고 생각했다. 즉 그냥 skip 해버리면 된다는 생각을 했다.2. skip을 하려면 어떤 구역에서 m칸 만큼 색칠하고 그 다음 구역 번호(paintPoint)를 알아야할 필요가 있다고 생각했다. (sections[i] + m부터 덧칠해야하는 구역 번호가 있다면 덧칠한다.)3. paintPoint보다 현재 덧칠해야하는 구역 번호가 더 작으면, 이미 색칠이 된 것이므로, continue를 통해서 계속 i를 증가시킨다.4. 색칠할때, 색칠 횟수를 기록한다. ..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제 좀 어려웠다...처음에는 이 문제를 그리디와 같은 접근을 했다. B의 흔적을 최대화 하고, A의 흔적을 최소해야하니까, B가 남길 수 있는 흔적을 높게 -> A가 남길 수 있는 흔적을 낮게 하는 방식으로 정렬을 해서 문제를 해결하려고했었다. 하지만 이 문제에 테스트케이스를 보고 종이에 조금만 적어서 생각을 해보면 그 방법이 될 수 없다는 것을 알게되었다. DP라는 점을 눈치 챘는데 이유는 다음과 같다.1. 물건을 훔친다 / 훔치지 않는다? => 뭔가 2차원 배열을 사용해서 점화식을 정의할 것 같다는 생각이 든다.2. 물건을 훔쳤을때, 훔치지 않을..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이구현문제이다.처음에 friends에 인덱스에 맞는 친구에게 준 횟수를 2차원 배열로 저장해야한다는 생각을 했다.records[i][j] => i가 j에게 준 선물 횟수라고 생각했다. 근데 gifts 배열을 보면 "이름 이름"의 형태로 준사람 받은 사람을 주고 있다."그러면 이름에 해당하는 인덱스를 순회해서 찾아야할까?"라는 생각을 했다. 하지만 생각해보면 그럴 필요가 없이, 이름에 해당하는 인덱스를 저장할 수 있는 자료구조인 HashMap을 사용해서 저장하면 된다고 생각했다. 그리고 사람 대 사람으로 1대1로 준 횟수에 대한 정보도 필요하지만, 그 사람이..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제는 간단한 구현 문제이다.1. 평일을 기록해야한다.2. 출근 인정 시각을 구하는 메소드를 하나 만들어야한다.이 두가지가 떠올랐다. 풀이는 다음과 같다.1. 집합에 평일에 대한 정보를 담는다.집합을 사용한 이유는 O(1)연산으로, 평일인지 아닌지 구분하기 위해서이다.2. startDay가 1 ~ 7이 아니라 0 ~ 6이 되면 나머지 연산하기 좋으므로 1을 감소시킨다.3. 출근 시간과 출근 인정시간을 구하고 이벤트 시작 요일을 갱신한다. 그리고 상품을 받을 수 있는지 여부인 boolean 변수를 하나 둔다.4. 평일이면, 출근 인정시간보다 크면 출근 인..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이기존에 생각했던 풀이는 다음과 같다.1. 그냥 N번째에 해당하는 문자열을 찾는다.2. ban에 있는 그 문자열보다 작은 애들의 개수를 센다.3. 작은 애들 갯수 + N번째 문자열이 n번째 주문이라고 생각했다. 하지만 예외 상황이 존재했다.O : ban 당하지 않은 문자열X : ban 당한 문자열이라고 가정해보자. 모두 사전순으로 바로 인접되게 정렬되어있다고 가정한다.(ab, ac와의 관계)XXXOXXXOXXXXXXXX라고 했을때, 두번째 문자열을 구한다고 가정하면, ban이 당한 문자열이 반환이 될 수 있는 문제가 존재했다. 그리고 데이터의 순서를 보장하..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이그냥 배열을 채우고 인덱스를 찾고 이런 문제이다... 단순 구현... 1. 2차원 배열을 만들어서, 전부 -1로 채운다.2. boolean 변수를 이용해서, 높이가 변할때마다, 순방향, 역방향으로 상자의 번호를 채운다.3. 찾는 상자 번호의 높이를 구하고, 가로로 몇번째 인덱스에 있는지 찾는다.4. 제일 높은 높이에서 상자가 나올때까지 개수를 구하고 리턴한다. 시간복잡도: O(100 * 10) 소스코드import java.util.*;class Solution { public int solution(int n, int w, int num) { ..
