문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이처음에 2중 for문을 사용해 substring 메소드를 이용해 모든 부분 문자열을 HashSet에 저장하고, 펠린드롬인 문자열들을 확인해서 최대 길이를 계산하려고 했으나, 효율성 테스트에서 통과되지 않았다. 부분문자열이 약 600만개가 나올 수 있다. 이것은 메모리 입장에서는 한문자를 저장한다고 해도6 000 000 => 6MB가 나오게 된다. 그리고 모든 부분 문자열에 대해 StringBuilder 객체를 만드는 것도 메모리가 많이 먹게 된다. 메모리를 많이 먹지 않으면서, 효율적으로 탐색하는 방법은1. 문자열 길이가 긴 부분 문자열부터 생각한다.2...
Problem Solving
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제에서 주의해야할 점이 있다. 테스트 케이스가 요청 시간 순서대로 들어온다는 명시가 없다.1. 요청 시간을 오름차순으로 정렬해야한다. 우선순위가 소요시간이 짧은 순, 작업 요청 시간이 빠른 순, 작업 번호가 작은 순이라고 했다.2번째 조건은 우리가 오름차순으로 정렬했으므로, 의미가 없다. 그리고 순서대로 들어오면 작업 번호가 작은 순이라는 것이 보장된다.2. 우선순위 큐에서 작업 소요시간을 오름차순으로 정렬만 하면 된다. 3. 현재 시간을 time이라고 지정해두고, time보다 같거나 작은 경우에 요청이 된 작업들을 우선순위 큐에 넣는다.4. 작업이 ..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이TreeMap을 사용한다. - TreeSet을 사용하면, 중복된 값이 나왔을 경우, 개수를 저장할 수 없는 문제가 있다.key: 값value: 값이 저장된 횟수를 저장하는 Map을 사용한다.- 일반적인 Map을 사용하면, Key가 가장 작은 값 큰 값을 찾으려고하면, 모든 key 값을 순회해서 찾을 수 있다. 하지만 key값이 최대 100만개가 올 수 있다면, 시간초과가 발생하게된다. => key값을 삽입할때마다, 정렬해주면서, Map처럼 쌍으로 저장할 수 있는 TreeMap을 사용해야한다. TreeMap이나 TreeSet은 가장 작은 값을 구할 수 있지만..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이우선 순위 큐를 사용해야하는 이유입니다.- 모든 음식의 스코빌 지수가 K 이상 == 스코빌 지수가 가장 작은 지수가 K이상이면 된다.와 동일(가장 작은 놈만 보면 되지 않을까?)- 스코빌 지수의 길이가 100만이다. 즉 선형적으로 검색을 하는 것은 시간 초과가 발생하게 된다.=> 100만개의 데이터 중에서 제일 낮은 스코빌 지수를 log 연산으로 remove, add 연산을 할 수 있는 장점이 있습니다. 1. 스코빌 지수를 꺼내서, K이상인지 확인한다.2. 스코빌 지수가 1개이면서 K이상이 되지 못하면 만들 수 없는 경우라고 생각하면 된다. (answer ..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이1. 지갑 크기와 지폐 크기를 기록한다.2. 지폐가 지갑에 들어갈 수 있는지에 대한 여부를 검사한다.3. 지폐 너비와 높이를 비교해서, 1/2 접는 처리를 한다.4. 접는 횟수를 반환한다. 소스코드class Solution { public int solution(int[] wallet, int[] bill) { int walletWidth = wallet[0]; int walletHeight = wallet[1]; int width = bill[0]; int height = bill[1]..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이1. str_list에 있는 문자열 배열을 0번째 인덱스 부터 순회해서 l, r 중 나오는 문자열에 대해 처리한다.2. l이 나왔다면, startIdx = 0, endIdx = i - 1을 기록한다.3. r이 나왔다면, startIdx = i + 1, endIdx = str_list의 길이 - 1을 기록한다.4. l, r이 나오지 않았을 경우, 빈 문자열을 리턴한다.5. 몇개의 문자열이 나올지 몰라서, 동적배열 ArrayList를 사용하고, 다시 문자열 배열(answer)에 담아서 리턴한다. 소스코드import java.util.*;class Soluti..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이1. 주어진 인용 수들을 담은 배열에서 최대 인용 수를 구한다.2. 최댓값에서 1씩 감소하는 for문을 수행하면서, 인용된 횟수와 인용이 되지 않은 횟수를 구한다.3. H-Index(h번 인용된 논문이 h편 이상 + 나머지 논문이 h번 이하 인용)이면 바로 for문을 빠져나와서 그 값을 리턴한다. 소스코드import java.util.Arrays;class Solution { public int solution(int[] citations) { int max = Integer.MIN_VALUE; for (int ..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이몬스터에게 공격을 당했을 경우와 공격을 당하지 않았을 경우를 생각하면 되는 문제이다. 1. 공격을 당한 도중에 체력이 0이하가 되면, -1을 리턴한다.2. 공격을 할 수 있는 최대 시간보다 현재 시간이 더 클 경우, 체력이 0 이하 여부에 따라서 리턴한다.3. 공격을 당했을 경우 현재 시간 값을 증가시키고, 붕대 감는 시간과 체력이 소모 처리를 해준다.4. 공격을 당하지 않았을 경우, 체력을 증가시키고, 연속된 시간 여부에 따라서 추가적인 체력을 준다. 소스코드class Solution { public int solution(int[] bandage,..
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이5와 0으로 이루어진 숫자들 중에 l이상 r이하의 수를 저장하는 문제이다.나는 "5"와 "0"의 문자열을 붙이면서, 재귀적으로 문자열을 만들고, Integer로 파싱해서 l이상 r이하라는 조건에 맞는 수를 ArrayList에 넣는 것을 생각했다.단, 수가 겹칠 수 있으므로, 집합을 사용해서 하나의 수만 저장이 되게하고, 그것을 ArrayList에 옮겨담고 정렬을 해서 int 배열에 복사했다. 소스코드import java.util.*;class Solution { public HashSet set; public int[] solut..
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이mode에 따라서 인덱스 처리를 다르게 해주면 되는 문제이다.1. 문자가 1이면 mode를 변경해준다.2. mode가 0일때, 짝수 인덱스의 문자를 붙이고, mode가 1일때, 홀수 인덱스의 문자를 붙인다.나는 문자열의 + 연산이 성능에 좋지 않은 것으로 알고있는데, 이건 추후에 알아보도록 하겠다. 소스코드class Solution { public String solution(String code) { int mode = 0; StringBuilder sb = new StringBuilder(); ..
