22.03.27. 풀었던 문제들 *** 정규표현식 정리하기

1. 크레인 인형뽑기 게임

문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자 문제를 잘 읽자

​

​

2. 키패드 누르기

간단한 구현 문제였다.

​

​

3. 숫자 문자열과 영단어

string 문제였다. 침착하게 잘 풀어보자. 특히 string parsing을 할 때 index가 잘 저장되는지 기억하자.

그리고 정규표현식으로 이 문제를 쉽게 풀 수 있다. 정규표현식도 정리해 보자.

​

​

4. 신규 아이디 추천

시키는 대로 잘 풀면 되는 문제다. 마찬가지로 문자열..이 귀찮다.

​

​

5. 신고 결과 받기

map을 이용해 풀 수 있는 구현 문제였다.

​

​

6. 실패율

seg fault의 이유를 정말정말 모르겠다.... 내 풀이는 맞는 것 같고 이유가 없는데...

*알았다. c++에서 sort 함수를 weak하게 설정할 경우 간혹 seg fault가 난다고 합니다. 진짜 충격적입니다... 정렬함수를 아래와 같이 바꾸니까 정상작동 한다.... 진짜 seg fault가 stages[cur_idx]에서밖에 나오지 않을 거라 생각해 몇일을 붙들고 있었는데.. 허망하다.... 이건 진짜 "맞왜틀"이다.

​

<풀이>

stages를 오름차순으로 sort 한 후 2개의 idx를 둔다.

- cur_idx는 현재 stage까지 도달한 사람의 idx,

- pre_idx는 이전 stage까지 도달한 사람의 idx이다.

​

for문으로 stage 1부터 N까지 돌린다.

stage i에 도달한 사람은 전체 length - cur_idx이다.

이어서 해당 stages를 돌파한 사람의 idx까지 cur_idx를 전진시킨다.(이게 while문이며, stages[cur_idx] <= stage면 cur_idx ++를 하는 이유다.)

while문을 빠져나오면 cur_idx는 현 stage를 돌파한 사람의 idx까지 전진되어 있고, pre_idx는 현 stage를 돌파하지 못한 사람들의 idx에 있다. 따라서 cur_idx - pre_idx를 하면 unclear한 사람들의 size이다.

만약 reached가 0이면 0으로 나눠지므로 예외처리를 한 후 v에 넣는다.

​

vector v를 내 입맛대로 sort한 후 print하면 된다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, double> pid;

// .first : 층수, .second : 실패율
bool comp(pair<int, double>& a, pair<int, double>& b){
    if(a.second > b.second) return true;
    else if(a.second == b.second){
        return a.first < b.first;
    } else{
        return false;
    }
}

vector<int> solution(int N, vector<int> stages) {
    sort(stages.begin(), stages.end());
    vector<pid> v;
    // pre_idx : 이전 stage까지 도달한 사람의 idx
    // cur_idx : 현재 stage까지 도달한 idx
    int length = stages.size(), pre_idx = 0, cur_idx = 0;
    int reached = 0, unclear = 0;
    double rate;
    
    for(int stage = 1; stage <= N; stage++){
        reached = length - cur_idx;
        while(cur_idx < length && stages[cur_idx] <= stage) cur_idx++;
        unclear = cur_idx - pre_idx;
        pre_idx = cur_idx;
        rate = (reached==0) ? 0 : (double)unclear / (double)reached;
        
        v.push_back({stage, 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;
}

/*

오름차순 정렬 시
1 2 2 2 3 3 4 6
이전 stage까지 간 사람들 : pre_idx (= 0)라고 하자.
1번 스테이지
    도달한 플레이어 수 : 전체 length - idx = 8명 도달
    클리어하지 못한 플레이어 수 : 1이 아닐때까지 idx 전진 -> idx 1에서 정지
    idx 1 - pre_idx 0 = 1
    실패욜 1/8
    pre_idx = idx = 1
2번 스테이지
    도달한 플레이어 수 : 전체 length - idx(1) = 7명 도달
    클리어하지 못한 플레이어 수 : 2가 아닐 때까지 idx 전진 -> idx 4에서 정지
    idx 4 - pre_idx 1 = 3
    실패율 3/7
    pre_idx = idx = 4
3번 스테이지
    도달한 플레이어 수 : 전체 length - idx(4) = 4명 도달
    클리어하지 못한 플레이어 수 : 3이 아닐 떄까지 idx 전진 : idx 6에서 정지
    idx 6 - pre_idx 4 = 2
    실패율 2/4
    pre_idx = idx = 6
4번 스테이지
    도달한 플레이어 수 : 전체 length - idx(6) = 2명 도달
    클리어하지 못한 플레이어 수 : 4이 아닐 떄까지 idx 전진 : idx 7에서 정지
    idx 7 - pre_idx 6 = 1
    실패율 1/2
    pre_idx = idx = 7
5번 스테이지
    도달한 플레이어 수 : 전체 length - idx(7) = 1명 도달
    클리어하지 못한 플레이어 수 : 5가 아닐 때까지 idx 전진 : idx 7에서 정지
    idx 7 - pre_idx 7 = 0
    실패율 0/1

stage 개수 5개임.
1 2 2 2 3 3 4 4
1번 스테이지
    도달한 플레이어 수 : 전체 length - idx = 8명 도달
    클리어하지 못한 플레이어 수 : 1이 아닐때까지 idx 전진 -> idx 1에서 정지
    idx 1 - pre_idx 0 = 1
    실패욜 1/8
    pre_idx = idx = 1
2번 스테이지
    도달한 플레이어 수 : 전체 length - idx(1) = 7명 도달
    클리어하지 못한 플레이어 수 : 2가 아닐 때까지 idx 전진 -> idx 4에서 정지
    idx 4 - pre_idx 1 = 3
    실패율 3/7
    pre_idx = idx = 4
3번 스테이지
    도달한 플레이어 수 : 전체 length - idx(4) = 4명 도달
    클리어하지 못한 플레이어 수 : 3이 아닐 떄까지 idx 전진 : idx 6에서 정지
    idx 6 - pre_idx 4 = 2
    실패율 2/4
    pre_idx = idx = 6
4번 스테이지
    도달한 플레이어 수 : 전체 length - idx(6) = 2명 도달
    클리어하지 못한 플레이어 수 : 4이 아닐 떄까지 idx 전진 : idx 8에서 정지
    idx 8 - pre_idx 6 = 2
    실패율 2/2
    pre_idx = idx = 8
5번 스테이지
    도달한 플레이어 수 : 전체 length - idx(8) = 0명 도달
    -> 실패율 0으로 둠.
    
실패율 구한 다음에는 어떻게 할까....
"실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다."
스테이지-실패율 key-value로 vector 만들어서 정렬 ? 
pair<int, double>로 정렬하면 되겠다. 어차피 오름차순 이니까...


*/