Algorithm/Programmers (5) 썸네일형 리스트형 [Programmers/JAVA] 05. 전화번호 목록 ※ 전화번호 목록https://school.programmers.co.kr/learn/courses/30/lessons/42577 문제 분석전화번호의 배열 phone_book 이 주어질 때, 한 번호가 다른 번호의 접두어인지 구하는 문제이다.어떤 번호가 다른 번호의 접두사인 경우가 있으면 fasle, 없으면 true 를 반환한다. 접근 방법 정렬 을 사용하여 어떤 번호가 다른 번호의 접두사인지 살펴볼 것이다.어떤 번호가 다른 번호의 접두사일 경우, 정렬된 배열 phone_book 에서 두 번호는 반드시 붙어있게 된다.따라서 배열을 정렬한 후, $i$ 번째 번호가 $i + 1$ 번째 번호의 접두사인지 확인하면 된다. 배열의 길이를 $N$, 전화번호의 길이를 $M$ 이라고 할 때, 정렬에 $O(Nlon.. [Programmers/JAVA] 04. 연속된 부분 수열의 합 ※ 연속된 부분 수열의 합https://school.programmers.co.kr/learn/courses/30/lessons/178870 문제 분석오름차순으로 정렬된 수열 sequence 와 부분 수열의 합을 나타내는 정수 k 가 매개변수로 주어진다.원소의 합이 k 인 부분 수열을 찾을 때, 부분 수열의 시작 인덱스와 마지막 인덱스를 구하는 문제이다.단, 합이 k 인 수열이 여러 개인 경우 길이가 짧은 수열을 찾고, 길이가 같은 경우 시작 인덱스가 작은 수열을 찾는다. 접근 방법 슬라이딩 윈도우 방식을 사용하여 합이 k 인 수열 중 조건에 맞는 수열을 찾을 것이다.윈도우의 시작과 마지막 인덱스를 모두 0에서 시작한다.시작 인덱스부터 마지막 인덱스 사이의 합이 k 보다 작으면 마지막 인덱스를 오른.. [Programmers/JAVA] 03. 예산 ※ 예산https://school.programmers.co.kr/learn/courses/30/lessons/12982 문제 분석부서별 신청 금액이 들어있는 배열 d 와 예산 budget 이 주어질 때, 최대 지원 가능한 부서의 수를 구하는 문제이다.단, 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 주어야 한다. 접근 방법신청 금액이 작을수록 보다 많은 부서의 물품을 지원해 줄 수 있을 것이므로 정렬 을 이용할 것이다. 부서의 개수가 $N$개 일 경우, 정렬의 시간 복잡도는 $O(NlogN)$이고 예산 분배의 시간 복잡도는 $O(N)$이다.따라서, 평균 시간 복잡도는 $O(NlogN + N) == O(NlogN)$이다. 코드 설계# 지원 가능한 부서의 개수를 저장할 변수 re.. [Programmers/JAVA] 02. 소수 만들기 📄 소수 만들기https://school.programmers.co.kr/learn/courses/30/lessons/12977 문제 분석배열 nums 안의 숫자 중 서로 다른 3개의 수를 더했을 때, 소수가 되는 경우의 개수를 구하는 문제이다. 접근 방법 완전 탐색 을 이용하여 서로 다른 3개의 숫자를 선택하고 그 합이 소수가 되는 경우의 개수를 구한다. 주어진 숫자를 $N$, 배열 nums 의 크기를 $K$라고 할 때, 시간 복잡도는 $O(NK^{3})$이다.$N = 3a$ 인 경우, $N$은 $I = 3$ 일 때와 $I = a$ 일 때 모두 $N$을 나누어 떨어지게 한다.따라서 $I$는 $I^{2} = N$이 되는 경우까지 확인하면 되므로 시간 복잡도는 $O(\sqrt{N}K^{3})$이다... [Programmers/JAVA] 01. 완주하지 못한 선수 📄 완주하지 못한 선수https://school.programmers.co.kr/learn/courses/30/lessons/42576 문제 분석마라톤에 참가한 선수의 이름이 담긴 배열 participant, 완주한 선수들의 이름이 담긴 배열 completion 이 주어진다.이 때, 완주하지 못한 선수의 이름을 리턴하는 문제이다. 접근 방법 완전 탐색 을 사용하여 두 배열의 값이 동일하면 공백으로 치환한다.for 문을 사용하여 공백으로 치환 된 participant 배열의 값 중 공백이 아닌 값을 리턴한다. 배열의 크기를 $N$이라고 할 때, 시간 복잡도는 $O(n^{2})$이다.N">$N$은 최대 $10^{5}$이므로 최대 수행 횟수는 $10^{10}$이고, 따라서 효율성 테스트에서 통과할 수 .. 이전 1 다음
