1. 나머지가 1이 되는 수 찾기
기초 반복문 문제였다.
2. 두 개 뽑아서 더하기
중복을 허락하지 않고, 정렬되어 있는 set 자료구조의 특징을 이용하면 쉽게 풀 수 있다.
3. 3진법 뒤집기
string 기본 문제였다.
4. 내적
loop 기본 문제였다.
5. 약수의 개수와 덧셈
simple for문이 아니라 조금 더 시간복잡도를 줄여보자.
6. 음양 더하기
기본 loop문이었다.
7. 없는 숫자 더하기
set으로 풀었지만... 그냥 총 합에서 빼는 방법도 있다.
8. 폰켓못
set으로 풀었다. set에 vector들의 원소를 넣고 싶을 때는 for문을 사용해서 하나하나 삽입해 주어도 되지만 초기화 하는 방법이 있으니 이를 참고하자.
9. 소수 만들기
소수 판정 및 3중 for문 사용하면 된다.
10. 예산
처음엔 two-pointer라고 생각했는데, 그게 아니라 단순한 수학적 증명이었다.
정렬해서 앞에서부터 따오는 게 optimal인가? (오름차순 정렬된) a1, a2, ... an, 그리고 b가 있다고 하자. ai + ... + aj <= b인 i, j가 문제 조건을 만족시키는 optimal value이라고 하자. (i != 1, i < j) a_i-1 <= a_i <= a_j이기 때문에 a_i-1 + a_i+1 + ... + aj <= ai + ... + aj 또, a_i-1 + a_i + ... + a_j-1 <= a_i-1 + a_i+1 + ... + aj <= ai + ... + aj이 된다. 이렇게 계속 반복해 나가면 어떤 j-i+1인 k에 대해 a1 + ... + ak <= ai + ... + aj가 되는데 그리고 제한조건에서 i != 1이라고 명시했기 때문에 a1 + ... + ak < ai + ... + aj는 자명하다. 이때 ai + ... + aj - (a1 + ... + ak)의 차를 이용해 a_k+1를 넣을 수도 있고(아닐 수도 있다) 넣는 경우 i != 1인 i, j 쌍은 존재하지 않고, 아닌 경우에는 i-j+1 = k는 또다른 optimal... 따라서 앞에서부터 세는 게 optimal이다.
11. 로또의 최고 순위와 최저 순위
간단한 구현 문제였다.
12. [1차] 다트 게임
(항상 귀찮은 문자열이 들어간)구현 문제다.
13. [1차] 비밀 지도
12번과 마찬가지로 구현 문제다. 이건 좀 인상깊다. 나중에 한 번 다시 풀어보자.
이제 5일차인가? lv 1 카카오 문제 8개만 풀면 lv1은 다 끝낸다. 감 천천히 잡아가고 있다. 힘내자.
14. 실패율
이 소스코드가 계속 seg fault 뜬다. while(idx<length && stages[idx] == i) 여기서 seg fault가 뜨는데... idx는 항상 0보다 크고, length보다 작다는 게 보장되는데 대체 왜 에러가 나는지 모르겠다...
#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; typedef pair<int, double> pid; bool comp(pair<int, double>& a, pair<int, double>& b){ if(a.second > b.second) return true; else{ return a.first < b.first; } } vector<int> solution(int N, vector<int> stages) { sort(stages.begin(), stages.end()); vector<pid> v; // pre_idx : 이전 stage까지 도달한 사람의 idx // idx : 현재 stage까지 도달한 idx int length = stages.size(), pre_idx = 0, idx = 0; int reached, unclear; for(int i = 1; i<=N; i++){ reached = length - idx; while(idx<length && stages[idx] == i){ idx++; } unclear = idx - pre_idx; pre_idx = idx; double failure_rate = (reached == 0) ? 0 : (double)unclear/(double)reached; v.push_back({i, failure_rate}); } sort(v.begin(), v.end(), comp); vector<int> answer(N); for(int i = 0;i <N; i++){ answer[i] = v[i].first; } return answer; }
'PS > PS Log' 카테고리의 다른 글
| 22.03.28. 풀었던 문제들 (0) | 2022.06.22 |
|---|---|
| 22.03.27. 풀었던 문제들 *** 정규표현식 정리하기 (0) | 2022.06.22 |
| 22.03.25. 풀었던 문제들 (0) | 2022.06.22 |
| 22.03.24. 풀었던 문제들 (0) | 2022.06.22 |
| 22.03.23. 풀었던 문제들 (0) | 2022.06.22 |