반응형 코딩테스트94 [프로그래머스] k번째수 (자바) 코드 package psg.고득점킷트.정렬;import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.List;public class PSG_K번째수 { public static void main(String[] args) { PSG_K번째수 psgK번째수 = new PSG_K번째수(); int[] solution = psgK번째수.solution(new int[]{1, 5, 2, 6, 3, 7, 4}, new int[][]{{2, 5, 3}, {4, 4, 1}, {1, 7, 3}}); System.out.println(Arrays.toString(s.. 2024. 7. 13. [프로그래머스] 폰켓몬 (자바) 프로그래머스 고득점 Kit: 해시 - 폰켓몬문제 설명당신은 폰켓몬을 최대한 많이 가지길 원합니다. 폰켓몬 종류 번호가 담긴 배열 nums가 주어졌을 때, nums의 길이의 절반을 고를 수 있는 경우 중에서 가장 많은 종류의 폰켓몬을 고르는 방법을 찾아 반환하는 문제입니다.문제 접근 방법HashSet 사용: 폰켓몬의 종류를 저장하는데 Set 자료구조를 사용하여 중복을 제거합니다.최대 폰켓몬 수 계산: 가져갈 수 있는 최대 폰켓몬 수는 nums.length / 2입니다.최종 결과 반환: Set의 크기와 최대 폰켓몬 수 중 작은 값을 반환합니다.시간 복잡도 분석nums 배열의 길이를 N이라고 할 때, 시간 복잡도는 O(N)입니다.배열을 순회하며 Set에 폰켓몬 종류를 추가하는 데 O(N)해결 방법아래는 주어진.. 2024. 7. 12. [프로그래머스] 전화번호목록 (자바) 프로그래머스 고득점 Kit: 해시 - 전화번호 목록문제 설명"전화번호 목록" 문제는 전화번호 목록이 주어졌을 때, 어떤 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다. 예를 들어, 전화번호 "119"는 "1195524421"의 접두어입니다. 전화번호 목록에 접두어 관계가 하나라도 있으면 false를 반환하고, 그렇지 않으면 true를 반환해야 합니다.문제 접근 방법HashMap 사용: 모든 전화번호를 HashMap에 저장합니다.접두어 확인: 각 전화번호의 모든 접두어를 확인하면서, 해당 접두어가 HashMap에 존재하는지 검사합니다.시간 복잡도 분석전화번호의 수를 N, 각 전화번호의 길이를 L이라고 할 때, 시간 복잡도는 O(N * L^2)입니다.전화번호 목록을 HashMap에 저장하는 .. 2024. 7. 11. [프로그래머스] 의상 (자바) 프로그래머스 고득점 Kit: 해시 - 의상문제 설명"의상" 문제는 주어진 의상 목록을 통해 서로 다른 조합으로 입을 수 있는 경우의 수를 구하는 문제입니다. 각 의상은 특정 종류(예: headgear, eyewear)로 분류되며, 한 종류의 의상은 한 번에 하나만 착용할 수 있습니다. 최소 한 개의 의상을 착용해야 합니다.문제 접근 방법HashMap 사용: 의상의 종류를 키(key)로, 해당 종류의 의상 개수를 값(value)으로 하는 HashMap을 사용합니다.의상 종류별 개수 계산: 의상 목록을 순회하며 각 의상 종류의 개수를 HashMap에 저장합니다.조합 계산: 의상 종류별로 (해당 종류의 의상 개수 + 1)을 모두 곱한 후 1을 뺍니다. 여기서 1을 더하는 이유는 해당 종류의 의상을 착용하지 않.. 2024. 7. 10. [프로그래머스] 완주하지 못한 선수 (자바) 프로그래머스 고득점 Kit: 해시 - 완주하지 못한 선수문제 설명"완주하지 못한 선수" 문제는 주어진 참가자 명단과 완주자 명단을 비교하여 완주하지 못한 선수를 찾는 문제입니다. 모든 선수들은 한 번만 참가하거나 완주합니다. 단, 완주하지 못한 선수는 단 한 명만 존재합니다.문제 접근 방법HashMap 사용: 각 선수의 이름을 키(key)로 하고, 해당 선수의 참가 횟수를 값(value)으로 하는 HashMap을 사용합니다.참가자 처리: 참가자 명단에서 각 선수의 이름을 키로 하여 참가 횟수를 카운트합니다.완주자 처리: 완주자 명단에서 각 선수의 이름을 키로 하여 참가 횟수를 감소시킵니다.완주하지 못한 선수 찾기: HashMap에서 값이 0이 아닌 선수를 찾습니다.시간 복잡도 분석참가자와 완주자 명단의 .. 2024. 7. 9. [프로그래머스] 베스트앨범 해시 (자바) 프로그래머스 고득점 Kit: 해시 - 베스트 앨범문제 설명"베스트 앨범" 문제는 주어진 노래의 장르와 각 노래의 재생 횟수를 바탕으로 베스트 앨범을 만드는 문제입니다. 베스트 앨범은 다음과 같은 규칙에 따라 구성됩니다:속한 노래가 많이 재생된 장르를 먼저 수록합니다.장르 내에서 많이 재생된 노래를 먼저 수록합니다.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.문제 접근 방법장르별 총 재생 횟수 계산: 각 장르의 총 재생 횟수를 계산하여 장르별 순위를 결정합니다.장르 내 노래 정렬: 각 장르 내의 노래들을 재생 횟수와 고유 번호를 기준으로 정렬합니다.베스트 앨범 구성: 위의 정렬된 리스트를 바탕으로 장르별로 두 곡씩 베스트 앨범에 수록합니다.시간 복잡도 분석O(N l.. 2024. 7. 8. [백준 1407] 2로 몇 번 나누어질까 (자바) 백준 1407번: 2로 몇 번 나누어질까? (팩토리얼)문제 설명팩토리얼 계산 시, 주어진 수의 팩토리얼 값에서 특정 숫자로 나눠질 수 있는 횟수를 구하는 문제입니다. 예를 들어, (10!)의 경우 2로 나누어질 수 있는 횟수를 구하는 방법을 설명합니다.문제 접근 방법팩토리얼의 정의: 팩토리얼 (N!)은 1부터 (N)까지의 모든 정수를 곱한 값입니다.팩토리얼의 소인수 분해: (N!)에서 특정 소수 (p)의 거듭제곱으로 몇 번 나눌 수 있는지를 구하는 문제입니다.나누어지는 횟수 계산: (N!)에서 (p)의 지수는 (\left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \left\lfloor \frac{N}{p^3.. 2024. 7. 7. [백준 1407] 보석도둑 (자바) 백준 1407번: 보석 도둑문제 설명주어진 범위 [a, b]에서 수의 이진수 표현에서 1의 개수를 구하는 문제입니다. 예를 들어, a=5, b=9라면 5에서 9까지의 수의 이진수 표현에서 1의 개수를 모두 더한 값을 출력합니다.문제 접근 방법각 수의 이진수 표현에서 1의 개수를 효율적으로 계산하기 위해 동적 계획법을 사용합니다.1부터 b까지의 수에 대해 이진수에서 1의 개수를 누적합으로 저장합니다.[a, b] 범위의 수에서 1의 개수를 구하기 위해 b까지의 누적합에서 a-1까지의 누적합을 뺍니다.시간 복잡도 분석O(N log N)각 수를 2로 나누어 1의 개수를 세는 과정은 log N입니다.이를 모든 수에 대해 반복하므로 시간 복잡도는 O(N log N)입니다.해결 방법아래는 주어진 범위에서 이진수 표현.. 2024. 7. 6. [백준 2960] 에라토스테네스의 체 (자바) 백준 2960번: 에라토스테네스의 체문제 설명에라토스테네스의 체 알고리즘을 사용하여 1부터 N까지의 숫자 중 소수를 찾고, S번째로 지워지는 수를 출력하는 문제입니다.공식package re_02;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class BOJ_2960_에라토스테네스의체_공식 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System... 2024. 7. 5. [백준 11653] 소인수 분해 (자바) 백준 11653번: 소인수 분해 (2트)문제 설명주어진 자연수를 소인수분해하여 각 인수를 출력하는 문제입니다. 소인수분해란 자연수를 소수들의 곱으로 나타내는 것을 의미합니다.문제 접근 방법입력받은 수 N이 1보다 큰 동안 반복합니다.2부터 시작하여 N을 나누어 떨어뜨리는 가장 작은 소수를 찾습니다.해당 소수로 N을 나눈 후, 소수를 출력합니다.이 과정을 N이 1이 될 때까지 반복합니다.시간 복잡도 분석O(N)최악의 경우, N이 소수인 경우에는 2부터 N까지의 모든 수를 나눠보아야 합니다.따라서 시간 복잡도는 O(N)입니다. 하지만 일반적으로 소수는 N의 제곱근까지만 검사하면 되므로 평균적으로는 더 빠르게 동작합니다.해결 방법아래는 주어진 자연수를 소인수분해하여 출력하는 Java 코드입니다:package .. 2024. 7. 4. [백준 1978] 소수찾기 (자바) 백준 1978번: 소수 찾기 (2트)문제 설명주어진 N개의 수 중에서 소수의 개수를 찾아 출력하는 문제입니다. 소수란 1과 자기 자신만을 약수로 가지는 수를 의미합니다.문제 접근 방법입력받은 수가 1이면 소수가 아니므로 건너뜁니다.입력받은 수가 소수인지 판단하기 위해 2부터 해당 수의 바로 앞까지의 수로 나눠봅니다.나누어 떨어지는 수가 없으면 소수로 간주하고 개수를 셉니다.시간 복잡도 분석O(N * M)N은 입력받은 수의 개수입니다.M은 각 수의 최대 크기입니다. 최악의 경우 N개의 수가 모두 최대 크기일 때, M번의 나눗셈을 수행해야 합니다.따라서 시간 복잡도는 O(N * M)입니다. 이는 입력받는 수의 범위가 작다면 효율적입니다.해결 방법아래는 주어진 수들 중 소수를 찾는 Java 코드입니다:pack.. 2024. 7. 3. [프로그래머스] 최소직사각형 (자바) 프로그래머스: 최소직사각형문제 설명다양한 크기의 명함을 담을 수 있는 최소 직사각형의 크기를 구하는 문제입니다. 주어진 명함의 크기를 담을 수 있는 가장 작은 직사각형의 크기를 구해야 합니다. 명함을 회전시켜서 수납할 수 있기 때문에 각 명함의 가로와 세로 중 더 큰 값을 직사각형의 가로, 작은 값을 세로로 배치합니다.문제 접근 방법각 명함의 가로와 세로 크기를 비교합니다.두 값 중 큰 값을 가로, 작은 값을 세로로 선택하여 최댓값을 갱신합니다.모든 명함을 확인한 후, 최종적으로 선택된 가로와 세로의 최댓값을 곱하여 최소 직사각형의 크기를 구합니다.시간 복잡도 분석O(N)이 문제는 명함의 개수 N에 대해 각 명함의 가로와 세로 크기를 한 번씩 비교하는 단순한 반복문을 사용합니다. 따라서 시간 복잡도는 O.. 2024. 7. 2. [백준 1812] 사탕 (자바) 백준 1812번: 사탕문제 설명N명의 아이들이 동그랗게 앉아 있습니다. 각 아이들은 사탕을 받고, 각 아이가 받은 사탕의 개수를 말합니다. N명의 아이들이 받은 사탕의 개수를 바탕으로 각 아이가 몇 개의 사탕을 받았는지 정확히 계산해야 합니다. 주어진 값으로부터 각 아이가 받은 사탕의 수를 구하는 문제입니다.문제 접근 방법N명의 아이들이 받은 사탕의 수를 입력받아 배열에 저장합니다.배열의 각 원소는 이전 아이와 다음 아이의 사탕 개수의 합으로 주어집니다.이를 바탕으로 첫 번째 아이가 받은 사탕의 개수를 계산합니다.첫 번째 아이의 사탕 개수를 바탕으로 나머지 아이들의 사탕 개수를 순차적으로 계산합니다.시간 복잡도 분석O(N)이 문제는 N명의 아이들에 대해 각 아이가 받은 사탕의 개수를 한 번씩 계산하는 단.. 2024. 7. 1. [백준 15736] 청기백기 (자바) 백준 15736번: 청기백기 규칙 (2트)문제 설명청기와 백기를 N개 세워놓습니다. 처음에는 모든 깃발이 청기 상태입니다. 규칙에 따라 k번째 사람은 k의 배수 위치에 있는 깃발을 뒤집습니다. 이 과정을 1번부터 N번까지 반복합니다. 이 규칙을 따른 후 백기 상태로 남아있는 깃발의 수를 구하는 문제입니다.문제 접근 방법깃발의 상태를 1번부터 N번까지 순차적으로 뒤집습니다.깃발의 상태가 변경되는 횟수는 해당 깃발의 약수의 개수와 같습니다.약수의 개수가 홀수인 경우에만 백기 상태로 남게 됩니다. 이는 약수의 개수가 홀수인 경우는 제곱수일 때만 발생합니다.따라서 1부터 N까지의 숫자 중 제곱수의 개수를 세면 됩니다.시간 복잡도 분석O(1)이 문제는 단순히 N의 제곱근을 계산하여 정수 부분만 구하면 됩니다. 제.. 2024. 6. 30. [백준 1090] 체커 (자바) 백준 1090번: 체커문제 설명체커판 위에 N개의 말이 주어집니다. 각 말은 (x, y) 좌표를 가지며, 이 말을 이동시켜서 특정 지점에 모으려고 합니다. 이때, 각 말은 맨해튼 거리로 이동하며, 특정 지점으로 모으는 데 걸리는 최소 이동 거리를 계산해야 합니다. 모든 말을 특정 지점으로 모으기 위한 최소 이동 거리를 구하는 것이 목표입니다.문제 접근 방법모든 말의 위치를 입력받아 저장합니다.특정 지점으로 모으는 경우를 전부 탐색합니다.각 지점에서 모든 말들을 모으는 데 필요한 이동 거리를 계산합니다.각 경우의 최소 이동 거리를 구해 출력합니다.시간 복잡도 분석O(N^3 * log N)모든 말을 특정 지점으로 모으는 경우의 수를 계산하는 과정에서 두 가지 방법을 고려합니다:첫 번째 방법은 말의 위치 범위.. 2024. 6. 29. 이전 1 2 3 4 ··· 7 다음 반응형
