Level 3. 징검다리 건너기 문제 자체는 간단하다. k개의 디딤돌을 가진 모든 구간 중에서 가장 빨리 모두 0이 되는 구간을 구해, 그 구간에서 최댓값을 구하면 된다. k개의 디딤돌을 가진 각 구간의 최댓값을 구한 후, 그 중 최솟값을 구하면 된다. O(n)에 수행되는 로직이고 굳이 따지자면 kn에 수행되는 코드인데 시간 초과가 발생했다.. // 이 풀이는 시간 초과가 발생한다. #include #include #include #include using namespace std; int solution(vector stones, int k) { int answer = INT_MAX; for (auto it = stones.begin(); it != stones.end() - k + 1; ++it) a..

Level 2. 롤케이크 자르기 토핑의 번호가 특별한 의미를 갖지 않기 때문에 map 대신 unordered_map을 사용했다. C++의 맵 자료구조는 한 번 접근한 키는 값이 0이어도 size에 포함되기 때문에, erase를 해주어야 한다. #include #include #include using namespace std; int solution(vector topping) { int answer = 0; unordered_map umapA, umapB; for (int tp : topping) ++umapB[tp]; for (int tp : topping) { ++umapA[tp]; if (--umapB[tp]

Level 3. 불량 사용자 우선 banned_id의 각 패턴과 일치하는 후보들을 정규 표현식을 활용해 저장했다. 한 단어는 '.' 문자에 해당한다. regex_match() 함수는 전체 문자열에 대한 검사이고, regex_search() 함수는 부분 문자열에 대한 검사이다. 그리고는 DFS를 이용해 조합을 구했다. 중복을 제거하기 위해 set 자료형을 사용했는데, 안쪽의 set은 하나의 경우에서 중복을 방지하기 위함이고, 바깥쪽의 set은 다른 경우 간 중복을 방지하기 위함이다. unordered_set 자료형을 써도 되지만, 컴파일 오류로 실행되지 않았다. #include #include #include #include #include using namespace std; void rDFS(vecto..

Level 3. 여행경로 코드는 짧지만 푸는 데는 오래 걸렸다. tickets 배열을 직접 넘겨 순회하면서 갈 수 있는 목적지를 찾아도 되지만, 빠르게 찾기 위해 unordered_map에 미리 운항 정보를 담아 이용했다. multiset에 저장했으므로, DFS에서 가장 처음 만족하는 항공편 정보가 알파벳 순으로 가장 앞서는 경로가 된다. 중복된 같은 티켓이 있을 수 있다는 조건이 문제에 안 나와있었는데 이것을 고려해 풀어야 한다. 그래서 set 대신 multiset을 사용했다. 각 경로마다 항공편 정보, 정답 vector를 관리해야 하기 때문에 레퍼런스가 아닌 값으로 넘겨야 한다. 모든 티켓을 사용하지 못하고 여행이 끝났으면 빈 vector를, 아니면 DFS를 계속 수행한다. #include #incl..

Level 3. 가장 먼 노드 그래프 탐색에서 단순 비용 갱신이 아니라, 이 문제처럼 최댓값 개수를 구하는 등 추가 작업이 필요할 때는 DFS보다는 BFS로 진행하는 것이 좋다. 이 문제는 전형적인 다익스트라 알고리즘 문제다. 모든 거리의 초깃값을 MAX로 설정하고, 시작점만 0으로 설정하는 것이 특징이다. 거리가 작으면 갱신하고 그 지점을 탐색하도록 한다. #include #include #include #include #define UNREACHABLE INT_MAX using namespace std; int solution(int n, vector edge) { int answer = 0, max; queue que; vector graph(n + 1); vector distance(n + 1, ..

Level 2. 두 원 사이의 정수 쌍 1사분면에 해당하는 점의 개수를 구한 후 4를 곱하는 방식이다. x를 1 ~ r₂까지 증가시키면서 삼각함수를 이용해 원₁의 y₁좌표, 원₂의 y₂좌표를 구한다. 두 y좌표를 빼 계산한 값이 x = t에서의 점 개수이고 이것을 반복해 더해 정답을 구한다. 그런데 40%밖에 정답 처리되지 않았다.. 복잡한 코드도 아니라서 어디가 문제인지 도통 감이 안 잡히고, 아무래도 삼각함수 값을 구하는 과정에서 오차로 인해 문제가 발생하는 것 같다. // 이 풀이는 틀린 풀이다. #include #include #include using namespace std; long long solution(int r1, int r2) { long long answer = 0; for (do..