문제https://www.acmicpc.net/problem/1039 풀이서로 다른 인덱스 i, j 번째 있는 수들을 k번 교환해서 나오는 최댓값을 구하는 문제이다. 처음에 누구나 백트래킹을 해보고 싶다는 생각이 들 것이다.그런데, 서로 다른 인덱스 2개를 고르는 수의 최댓값은 49이다.그러면 49^10이 되는 것인데, 무조건 시간 초과가 날 것이다. 그러면 문제를 k번 바꿔서 만들 수 있는 수들을 어떻게 만들 수 있을까? 라는 것으로 다르게 생각해보면 된다.= k번째가 되었을 때 최댓값을 갱신을 해주면서, (현재 숫자,바꾼 횟수)를 가진 bfs를 수행해보는 것이다. 그러면 시간복잡도는 10 * 1,000,000 이므로 1000만 연산으로 문제를 해결할 수 있다. 1. n, k를 입력받고 입력받은 수의 ..
Problem Solving
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이N번만큼 놀이기구를 탔을 때, 남은 금액을 계산하는 문제이다. 1. N번만큼 놀이 기구를 탔을 때 이용료의 합을 구한다. 2. 금액이 부족하지 않을 때 0을 리턴한다. 3. 부족한 금액을 리턴한다. 소스코드class Solution { public long solution(int price, int money, int count) { long answer = 0; for (int i = 1; i = 0) { return 0; } return answer - money;..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이주어진 예산에서 최대한 지원해줄 수 있는 부서의 수를 구하는 문제이다. 예산에서 최대한 지원해준다는 것은 필요한 금액이 작은 부서가 많을 수록 최댓값이라고 생각했다. 1. 부서 필요한 금액을 오름차순 정렬한다. 2. 주어진 예산에서 필요한 금액을 음수가 될때까지 뺀다. 3. 지원해줄 수 있는 부서의 수를 리턴한다. 소스코드import java.util.Arrays;class Solution { public int solution(int[] d, int budget) { Arrays.sort(d); int ans..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이주어지는 문자열에서 p와 y의 개수가 동일하면 True, 아니면 False를 리턴하는 문제이다. 1. p와 y의 대문자와 소문자를 비교해서 개수를 센다. 2. 수가 동일하면 True 아니면 False를 리턴한다. 소스코드class Solution { boolean solution(String s) { int pCnt = 0; int yCnt = 0; for (char ch : s.toCharArray()) { if (ch == 'p' || ch == 'P') { ..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이전화번호 뒷 4자리를 제외한 나머지를 *로 마스킹을 처리하는 문제이다. 1. String.repeat를 사용해서 4자리를 제외한 마스킹 문자열을 만든다. 2. 뒷 자리를 substring을 사용해서 문자열을 만든다. 3. 두 문자열을 붙인다. 소스코드class Solution { public String solution(String phone_number) { String star = "*"; int length = phone_number.length(); return star.repe..
연속으로 틀린 문제를 풀다보니 "아 이래서 이런 코드가 나오는구나!!"라는 깨달음이 생겨서 다른 분들에게도 도움되었으면 해서 공유하고 싶었다. 고민?요즘 어떤 기업이든 신입 채용 공고를 보다보면 코딩테스트를 보는 경우가 많다.쉽고 편안한 문제만 풀다보니 실력이 잘 늘지 않는게 느껴져 고민이 많았다. 딱맞게 Youtube 알고리즘에 이 동영상이 떴다. 전략위 동영상에서 틀린문제 푸는 법에 대해 정말 친절하게 알려주신다.필자는 맥북을 사용하는데, 엑셀로 관리하기가 어려워서 노션으로 관리하면서 3일이 지났는지, 7일이 지났는지 체크하고 있다.백준이나 프로그래머스에서 못풀었거나 1번이라도 틀린적이 있는 문제들은 모조리 넣어서 약점을 보완하고 있다.
문제https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이어떤 캐릭터가 피로도를 이용해서 던전을 탐험하는데, 탐험할 수 있는 최대 던전의 수를 구하는 문제이다. 던전의 개수가 2~8개이므로, 백트래킹을 이용해서 탐험할 수 있는 던전이 있으면 탐험하고 다른 던전을 탐험해보는 방식으로 구현하면 된다고 생각했다. (8 팩토리얼 = 약 4만) 1. 던전을 방문할 배열을 선언한다. 2. 던전을 탐험하면서 깊이의 최댓값을 계속 갱신해준다.현재 남은 피로도가 최소 탐험 피로도 이상이면, 탐험하고 다른 던전을 탐험해..
문제 https://www.acmicpc.net/problem/1038 풀이n번째로 높은 자리에서 낮은 자리로 감소하는 수를 구하는 문제이다. 모든 경우의 수를 따져보면, 총 1023개이다.{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 집합의 부분집합을 구하면 무조건 감소하는 수를 만들 수 있다.하지만 모두 다 안 고르는 경우공집합 경우가 있으므로, 총 경우의 수는 1023개이다. 1. 10번째 이하일 때는 n을 그대로 출력한다. 2. 0 ~ 9사이에서 1자리로 시작해서 10을 나머지 연산한 값보다 작은 값들을 계속 일의 자리로 붙여 리스트에 담는다.10을 나머지 연산하면 일의 자리가 나오고 그 수보다 작은 값을 붙이면 감소하는 수가 되기 때문이다.9876543210이 최대 자리이기 때문에, 자..
문제https://www.acmicpc.net/problem/30804 풀이탕후루에 꽂는 과일이 있는데 탕후루에 과일이 2개가 되는 종류 중에 가장 긴 길이를 구하는 문제이다. N이 20만이다. 즉 이중 for문을 돌면 시간초과가 난다. 투포인터로 순회하면 O(N)연산으로 수행할 수 있다. 1. 투포인터에서는 left, right 두가지 포인터가 존재하는데, right를 한개씩 이동하면서 종류의 개수를 센다. 2. right로 이동해서 종류가 3개가 넘어버리면 left로 종류가 2개 이하가 될때까지 left를 이동한다. 3. 최대 길이를 갱신한다. 소스코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOExce..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이키패드에서 왼손, 오른손 엄지 손가락을 이동해서 번호를 누르는데, 어떤 손가락으로 눌러야하는지 구하는 문제이다. 문제에 주어진 조건대로 구현하면 되는데, 몫 연산과 나머지 연산을 이용해서 위치를 구하는 것을 생각했다.두 연산을 사용하기 위해서는 1을 빼고 연산을 수행해주면 되고, -1인 경우는 0이므로 고정된 위치를 넣어주면 된다. 1. number의 나머지가 2인 경우 오른손을 이동한다. 2. number의 나머지가 0인 경우 왼손을 이동한다. 3. 위 두가지 조건이 모두 아닐 경우, 왼손과 오른손의 거리를 구한다.(|x2 - x1| + |y2 - y1|..
