22.03.26. 풀었던 문제들

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;
}
​