📑 문제🌱 아이디어스위핑 유형의 문제, 일단 무엇을 기준으로 정렬할지 생각해 보자 위 문제에 핵심은 좌표의 범위 L이 주어질 때  end - start 이 만족해야 한다, 즉 구간마다 L범위에 해당하는선분의 개수를 세야 한다. 좌표 구간마다 선분이 해당하는지 판단하고, 범위체크까지 한다면 자칫 O(N^2) 시간복잡도를 가지게 구현할 수 있다.하지만 N의 범위가 100,000까지 이며 O(N) 이하로 구현해야 한다. 먼저 데이터를 정렬하는 과정이 필요하다. y축을 기준으로 정렬하고 한쪽 방향으로 쭉 스캔하면서 계산을 하면 된다즉 한쪽 -> 반대쪽으로 쭉 스캔을 하는 스위핑 방식으로 구현하면 O(N)의 시간복잡도로 빠르게 구현 가능하다.   정렬 후 가장 아래 (10, 20)부터 last에 x를 넣고 계..

📑 문제🌱 아이디어버블소트의 특징을 활용하자! 위 문제는 C++ 버블 소트 코드를 제공한다. 전형적인 버블 소트 알고리즘이며 O(N^2)의 시간복잡도를 가진다입력으로 1  즉 , 위 문제는 버블 소트를 구현하는 문제가 아닌 버블 소트의 특징을 이용하는 문제이다.  결국 정렬하는 문제이다 버블 소트의 정렬 특징을 생각해 보자 오른쪽 -> 왼쪽으로 숫자가 이동할 때, 한 턴에 연속적으로 다수의 칸을 이동한다.왼쪽 으로 숫자가 이동할 때, 한 턴에 단 한 번만 이동한다. 위 특징을 봤을 때, 결국 버블 소트의 실행 횟수는 왼쪽  그렇다면 어떻게 구현할까? 해당 숫자와  입력된 위치(인덱스)를 저장하고, 한 번에 정렬 후 현재 숫자 위치(인덱스) - 원래 위치(인덱스)의 차를 구한다그중 가장 큰 차가 바로 ..

📑 문제🌱 아이디어낮, 밤 관련 BFS를 각각 구현하고, "영구적인 저체온증 환자"가 생기는 조건을 찾아보자. 위 문제의 키포인트는 볼드체로 잘 강조되어 있다. 낮, 밤을 나눠서 생각해 보자 - 낮"체온 회복 과정은 낮 사이 충분히 많이 반복될 수 있다."이 뜻은 다른 사람이 체온이 회복이 된다면, 그 주변 사람도 연쇄적으로 체온 회복이 가능하다는 뜻이다즉, 낮 BFS를 통해 단 한 번으로 가능한 모든 사람을 회복시켜야 한다. - 밤K명만큼 밤에는 저체온증 환자가 발생한다 단 "최악의 경우"로 발생한다.이 문제에서 최악의 경우란 낮이 되어도 회복이 불가능한 저체온증 환자이다. 그렇다면 어떤 조건에서 정상체온 환자가영구적인 저체온증으로 변경되는지 캐치해야 한다. 가장 먼저, 낮에서 체온을 회복할 때 정..

📑 문제 🌱 아이디어위 문제에서 친구가 된 순서의 정보를 차례차례 제공한다.그렇다면 단계마다 해당 친구가 속한 네트워크(집합)의 크기를 구하는 문제이다! 크게 생각해야 하는 점은 두 가지가 있다.1. 친구의 정보가 이름(문자열)으로 제공되는 점2. 친구 네트워크(집합)에 속한 크기를 구하는 방법. 1번의 경우는HashMap을 사용하여 key : 이름 -> value : 번호로 치환해서 유니온파인드 알고리즘을 실행하면 된다.당연히 해쉬맵에 이름이 있는지 판단해야 하고. 없다면 번호를 부여한다. 2번의 경우는유니온 파인드 알고리즘을 사용하고 그중 union 함수에서 두 노드의 부모노드가 다르다면? -> 서로 다른 노드임 -> 친구가 되었기 때문에 ans [부모노드] += ans [자식노드]로 업데이트 후..

📑 문제🌱 아이디어BFS탐색을 통해 맵밖으로 나가게 된 경우를 모듈러 연산으로 처리하자! 만약 도넛행성에 있다고 상상해 보자! 어떤 방향으로 쭉 직진하게 되었을 때 결국 제자리로 돌아올 것이다.즉 좌표  xy (0,0)에서 한 칸 더 위로 직진한다면 (0, N-1)이 되어야 한다. 이 조건은 동서남북 어디서나 동일하게 적용한다. 위 문제는 기존에 범위체크에서 배열밖 좌표로 이동하는 것을 막아주는 BFS가 아닌맵밖으로 나간다면 반대 방향으로 탐색하게 만들어야 한다. 모듈러 연산을 통해 위와 같은 효과를 얻을 수 있다. 예를 들어 N = 5 일 때 배열의 인덱스는 0, 1, 2, 3, 4 일 것이다 인덱스 5를 탐색하려고 할 때 5 %= N을 통해 다시 인덱스 0을 탐색하게 만들면 된다.🌱 코드 및 풀..