[prgorammers] level1
2023년 6월 24일
230624 #
시작 하루 10문제씩 풀 예정
1. 달리기 경주 #
vector 자체로 검색해서 풀면 시간초과로 풀리지 않는다.
벡터 상태의 순차탐색보다 이미 정렬된 맵의 key로 이름을 넣어서 검색하면 이분탐색으로 찾아 빠를것이라고 판단했다.
1vector<string> solution(vector<string> players, vector<string> callings) {
2 map<string,int>::iterator it, target_it;
3
4 map<string, int> m;
5 int rank;
6 string target_name;
7
8 for (int i = 0; i < players.size(); i++)
9 m.insert(make_pair(players[i], i)); // 이름과 등수를 맵에 넣음
10
11 // 얘는 줄일 수 없다.
12 for (string c : callings) {
13 it = m.find(c); // 현재 이름불린애 iterator
14 rank = it->second; // 이름불린애 순위
15
16 // players 배열에서 이름(순위) 교환
17 swap(players[rank], players[rank-1]);
18
19 // 앞등수 이름 가져오기
20 target_name = players[rank];
21 target_it = m.find(target_name);
22
23 // map에서도 순위 교환
24 swap(it->second, target_it->second);
25 }
26 return players;
27}
2. 공원산책 #
stringstream에서 데이터를 연속적으로 입 출력할때 출력버퍼의 eof에 도달하면 clear로 eof 플래그를 제거하기 전까지 입력이 불가능하다.
1 string str2, str3;
2 stringstream ss;
3 ss << "test zzz";
4 ss << "test2";
5 ss >> str2;
6 ss >> str2;
7 ss << "test3"; // 출력버퍼가 eof 상태가 되어 스트림에 입력 불가
8 ss >> str3;
9 std::cout << str2 << ", " << str3; // "zzztest2, " 출력
230625 #
1. 자동차 대여 기록에서 장기/단기 대여 구분하기 (SQL) #
- date_format 으로 날짜 포매팅
- case end로 조건에 따라 값이 정해지는 컬럼 추가
- datediff 함수로 일 수 계산 가능 (시간은 무시되며, 날짜 범위 벗어나면 NULL 리턴)
- 날짜 간격 30일이상인데 +1 해준 이유는 뭐임?
- between으로 사잇값 계산
1select
2 history_id,
3 car_id,
4 date_format(start_date, '%Y-%m-%d'),
5 date_format(end_date, '%Y-%m-%d'),
6case
7when datediff(end_date,start_date) + 1 >= 30 then '장기 대여'
8else '단기 대여'
9end as RENT_TYPE
10
11from CAR_RENTAL_COMPANY_RENTAL_HISTORY
12where start_date between '2022-09-01' and '2022-09-30'
13order by history_id desc
2. 가장 가까운 같은 글자 (배열 초기화 방법) #
다른건 아니고 배열 초기화할때 사용하는 함수때문에 정리하려 한다.
1int arr[26] = {-1, }; // 이 방법은 0일때만된다. { -1, 0, 0, 0, 0 ...}
2memset(arr, -1, 26); // memset은 char 기준으로 초기화해준다. -1은 어떤 자료형이든 FFFFFFFF 라서 초기화가능
3std::fill_n(arr, 26, -1); // c++ 타입
3. 기사단원의 무기 (약수) #
약수의 개수는 자주 나오는 문제이므로 공식화가 중요한듯 하다.
-
소인수분해 후 모든 지수에 +1 을 더한 후 곱한 값 2^2 * 3^7 인 수의 약수의 개수는
(2+1) * (7+1) = 24이다. 소인수분해의 시간복잡도는 O(sqrt(n)) 이다. -
n의 제곱근까지의 모든 약수를 직접 계산 어차피 약수는 어떤 수와 어떤 수의 곱이라 대칭형태인데, 중간값이 절반이 아닌 x*x = n 인 n의 제곱근이다.
제곱근까지의 약수 * 2 + (x*x == n ? -1 : 0)모든 약수를 직접 찾는 방법도 역시 O(sqrt(n)) 이다. 이 코드는 i * i 로 범위를 지정할때 오버플로우를 조심해야한다. (46340^2 == 2147395600, 46341^2 == 2147488281)
1while (i * i <= n) {
2 if (n % i == 0)
3 answer++;
4}
5answer = answer * 2 + (i * i == n ? -1 : 0);
- 에라토스테네스채 O(NloglogN) 으로 거의 선형에 가까운 알고리즘이지만 메모리를 많이 잡아먹는다는 단점이 있다.
일단 target 숫자 크기의 배열을 만들고 소수라고 가정하고 시작한다. 0, 1은 소수가 아니라 false로 변경한다.
현재 수가 소수면, 이후 모든 현재 수(소수)의 배수는 소수가 아니게된다.
i*i 부터 시작하는 이유는 어차피 i가 7일때, i * 2, i * 3 같은건 이미 i가 2일때, 3일때 미리 처리했기 때문이다.
소수를 여러번 찾아야되는 상황에서 사용하기 좋다.
(범위내에서 소수의 개수찾기, 배열안에있는 소수 판별 등)
1vector<bool> is_prime(n + 1, true);
2
3is_prime[0] = false;
4is_prime[1] = false;
5
6for (int i = 2; i * i <= n; ++i) {
7 if (is_prime[i]) {
8 for (int j = i * i; j <= n; j += i) {
9 is_prime[j] = false;
10 }
11 }
12}
230627 #
1. 햄버거 만들기 #
1231 패턴이 몇번 나오는지에 대한 문제이다. 12 1231 31 이런식으로 겹쳐있어도 찾아내야한다.
벡터에 1,2,3 들어올때마다 쌓아두고 짝이 맞을때 맨뒤부터 하나씩 졸업시키는 느낌으로 구현.
1int solution(vector<int> ingredient) {
2 int answer = 0;
3 vector<int> v = { -1 };
4 for(int x : ingredient){
5 if(v.back() == 1 && x == 2) v.back() = 12;
6 else if(v.back() == 12 && x == 3) v.back() = 123;
7 else if(v.back() == 123 && x == 1) answer++, v.pop_back(); // == v.resize(v.size() -1);
8 else if(x == 1) v.push_back(x);
9 else v.clear();
10 }
11 return answer;
12}
230628 #
1. 신고 결과 받기 #
카카오 블라인드 채용 1번문제(80%)였는데, 문제가 어렵진 않지만 구현할게 많다는 생각이 들었다.
신고 리스트가 중복되는 경우 무시하기 위해 set을 사용해서 필터링했는데,
신고리스트는 “ryan con” 이런식으로 “신고자 신고대상” 형식으로 들어와서 set이 바로 생각났다.
신고리스트가 만약 {“신고자”, “신고대상”} 이런식으로 들어오거나 다른 배열에 따로 들어오는 경우에는 어떻게 처리할지 고민했을지도 모른다.
문자열을 적극적으로 활용하면 될듯
대상이 k번 이상 신고당했는지 확인해야하고, 정지당한 경우 신고자가 누구인지 알아와야 하기 때문에
map<string, vector
1using namespace std;
2
3vector<int> solution(vector<string> id_list, vector<string> report, int k) {
4 vector<int> answer(id_list.size(), 0);
5 set<string> s(report.begin(), report.end());
6 stringstream ss;
7
8 map<string, vector<string>> targets;
9 vector<string> banlist;
10
11 // 유저별 누적된 신고 수를 확인하기 위해 신고대상-신고자리스트 맵
12 string r, target;
13 for (string str : s) {
14 ss << str;
15 ss >> r >> target;
16 targets[target].push_back(r);
17 ss.clear();
18 }
19
20 // 밴당한 사람 찾기
21 for (auto it = targets.begin(); it != targets.end(); ++it) {
22 if (it->second.size() >= k) {
23 banlist.push_back(it->first);
24 }
25 }
26
27 // 밴당한 유저의 신고자들에 해당하는 인덱스를 찾아서 count 증가
28 for (string str : banlist) {
29 for (string id : targets[str]) {
30 for (int i = 0; i < id_list.size(); i++) {
31 if (id_list[i] == id) {
32 answer[i]++;
33 break;
34 }
35 }
36 }
37 }
38 return answer;
39}
230629 #
1. 부족한 금액 계산하기 #
x의 배수들을 더해야할때, 가우스공식(1~n까지의 합)을 응용할 수 있다.
3의 배수를 10개 더하기
1// 1~10까지 더하기 공식
2ret = (1 + 10) * 10 / 2;
3// 의 3배
4ret *= 3;
2. 숫자 문자열과 영단어 #
이럴땐 regex_replace를 사용하면 편하다
"one4seveneight" → 1478
gcc 계열의 컴파일러에서는 일반적으로 쓸만한 모든 함수가 포함된 bits/stdc++.h 헤더가 내장되어있다.
1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(string s) {
5 s = regex_replace(s, regex("zero"), "0");
6 s = regex_replace(s, regex("one"), "1");
7 s = regex_replace(s, regex("two"), "2");
8 s = regex_replace(s, regex("three"), "3");
9 s = regex_replace(s, regex("four"), "4");
10 s = regex_replace(s, regex("five"), "5");
11 s = regex_replace(s, regex("six"), "6");
12 s = regex_replace(s, regex("seven"), "7");
13 s = regex_replace(s, regex("eight"), "8");
14 s = regex_replace(s, regex("nine"), "9");
15 return stoi(s);
16}
3. 신규 아이디 추천 #
1string solution(string new_id) {
2 string answer = new_id;
3 do {
4 new_id = answer;
5 // 1. 소문자 변환
6 transform(answer.begin(), answer.end(), answer.begin(), ::tolower);
7 // 2. a-z0-9-_. 문자제외 전부 삭제
8 answer = regex_replace(answer, regex(R"([^a-z0-9\-_\.])"), "");
9 // 3. . 여러개 압축
10 answer = regex_replace(answer, regex(R"(\.{2,})"), ".");
11 // 4. . 스트립
12 answer = regex_replace(answer, regex(R"(^(?:\.)|(?:\.)$)"), "");
13 // 5. 빈문자열인지 체크
14 answer = answer.size() ? answer : "a";
15 // 6. 16자 이상인지 체크
16 answer = answer.size() < 16 ? answer : answer.substr(0, 15);
17 // 7. 2자 이하라면 마지막문자 반복
18 answer = answer.size() > 2 ? answer : answer.append(3 - answer.size(), answer.back());
19 } while (answer != new_id);
20 return answer;
21}
4. 내적 #
a: [1,2,3,4] b: [-3,-1,0,2]
1*(-3) + 2*(-1) + 3*0 + 4*2 = 3
1inner_product(a.begin(), a.end(), b.begin(), 0);
230630 #
1. 실패율 #
vector
1vector<pair<double,int>> fail;
2sort(fail.begin(), fail.end(), [](auto a, auto b) {
3 return a.first == b.first ? a.second < b.second : a.first > b.first;
4}
키 값이 숫자이기 때문에 키에 -1을 곱하면 기본 sort로도 정렬이 된다.
2. 두 정수 사이의 합 #
a가 b보다 크면 XOR을 이용한 swap a ^= (b ^= (a ^= b))
swap으로 인해 b >= a 가 된다.
-b(b에 대한 2의 보수) = ~b + 1
-~b = b + 1
n * (n + 1) / 2 은 1부터 n까지의 수를 모두 더한 값이기 때문에 결국 1부터 b까지의 수를 더한 값과 1부터 a까지의 수를 모두 더한 값을 빼는 것이다.
1long long solution(int a, int b) {
2 long long answer = 0;
3 if (a > b) a ^= b ^= a ^= b;
4 answer = (long long)b * -~b / 2 - (long long)a * ~-a / 2;
5 return answer;
6}
3. 짝수와 홀수 #
개쉬운 문제지만, 비트연산으로도 풀수있다.
1return num & 1 ? "Odd" : "Even";
4. 행렬의 덧셈 #
vector의 operator+를 오버로딩해서 구현했다.
1vector<int> operator+(vector<int>& l, vector<int>& r) {
2 vector<int> ret(l.begin(), l.end());
3
4 if (l.size() < r.size())
5 ret.resize(r.size(), 0);
6 for (int i = 0 ; i < ret.size(); i++)
7 ret[i] = ret[i] + r[i];
8 return ret;
9}
10
11vector<vector<int>> operator+(vector<vector<int>>& l, vector<vector<int>>& r) {
12 vector<vector<int>> ret(l.begin(), l.end());
13 if (l.size() < r.size())
14 ret.resize(r.size(), {0});
15 for (int i = 0; i < ret.size(); i++)
16 ret[i] = ret[i] + r[i];
17 return ret;
18}
19
20
21vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
22 vector<vector<int>> answer = arr1 + arr2;
23 return answer;
24}
5. 최대공약수와 최소공배수 #
최대공약수 : 공약수 중에서 가장 큰값. 겹치는 소인수들만 곱한 값
최소공배수 : 공배수중에 가장 작은값. 겹치는 소인수들은 한번만 곱하고, 겹치지 않는 소인수들을 전부 곱한값.
최소공배수 = (최대공약수 * 안겹치는 값들 곱) or (두 값의 곱 / 최대공약수)
- 유클리드 호제법 두 수가 서로의 수를 나눈 나머지로 찾기
1 78696 ＝ 19332×4 ＋ 1368 // a = b * n + c
2 19332 ＝ 1368×14 ＋ 180 // b = c * n + d
3 1368 ＝ 180×7 ＋ 108
4 180 ＝ 108×1 ＋ 72
5 108 ＝ 72×1 ＋ 36
6 72 ＝ 36×2 ＋ 0
6. 벡터에서 중복제거 #
같은 숫자는 싫어
벡터에서 같은 숫자는 제거하고 한개만 남겨두기
1arr.erase(unique(arr.begin(), arr.end()),arr.end());
230701 #
1. algorithm - replace #
[1차] 비밀지도
문자열에서 어떤 값을 전부 변경하기 위해 algorithm 헤더의 replace를 사용했다.
1replace(tmp.begin(), tmp.end(), '1', '#');
250827 #
1. “HH:MM” <-> int h, m #
[PCCP 기출문제] 1번 / 동영상 재생기
WA! stringstream으로 “HH:MM” 형식을 delim 까지 따로 꺼낼수가 있다
1#include <sstream> // stringstream
2#include <iomanip> // setw, setfill
3
4// "HH:MM" to int
5int from_time_string(string time_string) {
6 stringstream ss(time_string);
7 int h, m;
8 char delim;
9 ss >> h >> delim >> m;
10 return h*100+m;
11}
12
13// int to "HH:MM"
14string to_time_string(int h, int m) {
15 stringstream ss;
16 ss << setw(2) << setfill('0') << h
17 << ":"
18 << setw(2) << setfill('0') << m;
19 return ss.str();
20}
반복문에서 사용할때 주의해야한다. 스트림을 저렇게만 빼서쓸때 초기화를 안하면 EOF가 남아서 다음 파싱때 잘못될 수 있다.
1for (const std::string& gift : gifts) {
2 std::stringstream ss(gift); // 매번 새 스트림으로 초기화
3 ss >> send >> recv;
4}