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>로 정렬하면 되겠다. 어차피 오름차순 이니까... */
'PS > PS Log' 카테고리의 다른 글
22.03.29. 풀었던 문제들 (0) | 2022.06.22 |
---|---|
22.03.28. 풀었던 문제들 (0) | 2022.06.22 |
22.03.26. 풀었던 문제들 (0) | 2022.06.22 |
22.03.25. 풀었던 문제들 (0) | 2022.06.22 |
22.03.24. 풀었던 문제들 (0) | 2022.06.22 |