반응형 [PCCP] Lv3: 기지국 설치(12979) 해설 문제- 문제 링크: 기지국 설치 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 전체 범위- W: 전파의 세기- 최악의 경우 location이 매번 2W + 1씩 증가하므로 N / (2W + 1)번 반복문을 수행- 최종 시간 복잡도: O(N/W)더보기#include using namespace std;int solution(int N, vector stations, int W) { int answer = 0; int location = 1; // 현재 탐색하는 아파트의 위치 int .. 2024. 12. 25. [PCCP] Lv2: 귤 고르기(138476) 해설 문제- 문제 링크: 귤 고르기 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: tangerine의 길이- counter에 귤의 개수를 저장하는 시간 복잡도는 O(N)- 귤의 개수만 다시 sorted_counts에 넣고 내림차순으로 정렬: O(NlogN)- 반복문은 최악의 경우 모든 원소를 순회하므로 시간 복잡도는 O(N)- 최종 시간 복잡도: O(NlogN)더보기#include #include #include #include using namespace std;int solution(int k, v.. 2024. 12. 25. [PCCP] Lv2: 구명보트(42885) 해설 문제- 문제 링크: 구명보트 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: people의 길이- sort(): O(NlogN)- 반복문은 최악의 경우 people 배열 끝까지 반복하므로 최종 시간 복잡도: O(NlogN)더보기#include #include using namespace std;int solution(vector people, int limit) { sort(people.begin(), people.end()); // 몸무게를 오름차순으로 정렬 int count = 0; .. 2024. 12. 25. [PCCP] Lv1: 예산(12982) 해설 문제- 문제 링크: 예산 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: d의 길이- sort(): O(NlogN)- 반복문은 최악의 경우 모든 원소에 대해 반복하므로 시간 복잡도는 O(N)- 최종 시간 복잡도: O(NlogN)더보기#include #include using namespace std;int solution(vector d, int budget) { sort(d.begin(), d.end()); // 벡터 d를 오름차순으로 정렬 int count = 0; // 지원할 수 있.. 2024. 12. 25. [PCCP] Lv4: 지형 이동(62050) 해설 문제- 문제 링크: 지형 이동 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: land의 한 변의 길이- 각 지점을 방문하는데 필요한 시간 복잡도는 O(N^2)- 우선순위 큐를 활용해 너비 우선 탐색을 진행하므로 최종 시간 복잡도는 O(N^2 * log(N^2))더보기#include #include #include using namespace std;// 현재 칸의 좌표, 이전 칸에서 현재 칸으로 가는 비용struct Pos { int r; int c; int heightDiff; bool operator p.heightDiff; }};int dy[4] = {-1, 0, 1, 0};int dx[4] =.. 2024. 12. 25. [PCCP] Lv2: 튜플(64065) 해설 문제- 문제 링크: 튜플 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- updateCounts()에서 문자열 s의 길이를 N이라고 한다면, 문자열을 한번 순회하므로 시간 복잡도는 O(N)- 반복문 내부에 sort()가 있지만 각 숫자는 최대 10만이므로 6자리를 넘지 않아 무시 가능한 연산- solution()의 freqPairs를 정렬하는 부분에서 freqParis의 원소 개수를 M이라 한다면 시간 복잡도는 O(MlogM)- freqPairs를 순회할 때 시간 복잡도는 O(M)- 최종 시간 복잡도: O(N + M*logM + M) → O(N + M*logM)더보기#include #include using namespace s.. 2024. 12. 25. [PCCP] Lv2: 가장 큰 수(42746) 해설 문제- 문제 링크: 가장 큰 수 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: numbers의 길이- sort()에서 compare()을 기준으로 정렬. compare()는 두 수를 문자열로 변경한 후 조합해서 비교하는 함수- 각 수는 최댓값이 1,000이므로 문자열을 합칠 경우 최대 문자열의 길이는 7- 데이터가 N개일 때 정렬에 필요한 시간 복잡도는 O(NlogN)- 최종 시간복잡도는 O(7NlogN) → O(NlogN)더보기#include #include #include using namespace std;// 문자열로 바뀐 두 수를 조합해서 크기 비교bool.. 2024. 12. 25. [PCCP] Lv1: K번째 수(42748) 해설 문제- 문제 링크: K번째 수 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: array의 길이- M: commands의 길이- commands의 각 원소에 대해 배열을 자르는 시간 복잡도는 O(N)- 이후 정렬을 포함한 시간 복잡도는 O(NlogN)이고 이를 M번 반복하므로 최종 시간 복잡도는 O(M*(NlogN))더보기#include #include #include using namespace std;vector solution(vector array, vector> commands) { vector answer; vector subArray; for (const auto& cmd : comman.. 2024. 12. 25. [PCCP] Lv1: 정수 내림차순으로 배치하기(12933) 해설 문제- 문제 링크: 정수 내림차순으로 배치하기 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 주어진 숫자- 주어진 숫자의 자릿수는 대략 logN이고 이를 문자열로 만드는 작업에 걸리는 시간 복잡도는 O(logN)- 이후 문자열을 sort()함수로 정렬하는 시간 복잡도는 O(logN * log(logN))- 최종 시간 복잡도: O(logN * log(logN))더보기#include #include using namespace std;long long solution(long long n) { // 숫자를 문자열로 변환 string str = to_strin.. 2024. 12. 25. [PCCP] Lv1: 문자열 내 마음대로 정렬하기(12915) 해설 문제- 문제 링크: 문자열 내 마음대로 정렬하기 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: strings의 길이- S: strings의 문자열의 길이- 각 문자열을 비교하면서 정렬하므로 시간 복잡도는 O(N*S*logN)더보기#include #include #include using namespace std;int idx; // 비교 함수bool compare(string a, string b) { return a[idx] == b[idx] ? a solution(vector strings, int n) { idx = n; // 각 문자.. 2024. 12. 25. 이전 1 2 3 4 5 6 7 8 ··· 13 다음 반응형
