문제 링크 1. 아이디어 두 수의 안전 거리는 각 수를 2진수로 나타냈을 때 서로 다른 자리의 개수로 정의됐다. 이는 두 수를 XOR 연산한 결과에서 1의 개수와 동일하다. 해당 문제는 이 XOR 연산과 BFS를 활용하면 해결할 수 있는데 특정 수에서 임의의 한 자리의 비트를 바꿀 경우 기존 수와의 안전 거리가 1이 된다는 점을 활용하면 ...

문제 링크 1. 아이디어 소셜 네트워킹 어플리케이션에서는 두 사람이 친구 관계일 경우 친구 관계 그래프에서 경로가 존재한다. 사람을 노드, 관계를 간선으로 생각한 그래프에서 두 노드가 같은 그래프에 속했는지 판단하는 문제로 생각할 수 있고 유니온 파인드 알고리즘을 활용해서 두 사람이 같은 노드에 있는지 판단해줬다. 2. 코드 1....

문제 링크 1. 아이디어 주어진 입력으로 비밀번호를 알아내야하는 문제로 현재 커서의 앞 쪽에 위치한 문자들을 저장하는 덱과 커서 뒤 쪽에 위치한 문자들을 저장하는 덱 두 개를 활용해서 해결했다. 주어진 입력의 문자들을 순회하며 해당 문자가 -이면 앞 덱의 rear의 원소를 제거하는 것으로 동일한 효과를 볼 수 있다. 화살표 입력의 경우 각...

문제 링크 1. 아이디어 탑의 레이저 신호는 탑의 꼭대기에서 왼쪽 방향으로 발사되며 이를 가장 먼저 수신하는 탑을 찾아야 하는 문제다. 간단하게는 각 탑에 왼쪽 방향으로 자신보다 큰 탑이 나올 때까지 탐색하면 되지만 탑이 최대 500,000개가 주어져서 O(N²)의 시간 복잡도로는 해결할 수 없다. 포인트는 각 탑은 자신보다 큰 탑이 오른...

문제 링크 1. 아이디어 N개의 도시들이 있고 도시간 길이 있는지 여부가 주어졌을 때 여행 계획에 속한 도시들을 모두 방문할 수 있는지 판단하는 문제다. 모든 도시들이 하나의 그래프 안에 존재하면 어떻게든 방문할 수 있으므로 유니온 파인드 알고리즘을 활용해서 도시들을 그룹핑한 후 모두 같은 그룹에 속했는지 판단하는 방식으로 해결했다. ...

문제 링크 1. 아이디어 전형적인 스택 순열 문제로 1부터 N까지 순서대로 삽입할 수 있으므로 현재 삽입할 수를 나타내는 변수 cur를 활용하면 해결할 수 있다. 수열의 각 수 x에 대해 cur가 x보다 작다면 일단 cur가 x가 될 때까지 1씩 증가시키며 삽입해야 한다. 삽입을 한 후 top을 제거하면 되는데 삽입에 실패할 경우에는 이미 ...

문제 링크 1. 아이디어 체스판에서 각 칸에 비숍을 놓을 수 있는지 없는지 정보가 주어졌을 때 가장 많이 배치할 수 있는 비숍의 개수를 구하는 문제다. 체스를 해본 적이 있다면 감을 잡을 수 있는데 체스판은 가장 왼쪽 위 칸이 하얀색이며 하얀색과 검은색이 반복되어 나타나는 구조이고 비숍은 처음 놓인 칸의 색에서 다른 색을 공격할 수 없다. ...

문제 링크 1. 아이디어 집합들에 대한 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 반복적으로 수행해야 하는 문제로 유니온 파인드 알고리즘을 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class ...

문제 링크 1. 아이디어 주어진 명령을 수행하는 에디터를 구현하는 문제로 에디터에서 문자들은 커서의 앞 또는 뒤 둘 중 한 곳에 위치해야 한다. 커서 앞 쪽에 위치한 문자들을 저장하는 덱과 커서 뒤 쪽에 위치한 문자들을 저장하는 덱 두 개를 만들어서 구현했다. L 명령을 수행하면 커서를 왼쪽으로 한 칸 옮기는데 이는 앞 덱의 rear에 있...

문제 링크 1. 아이디어 오큰수는 해당 수보다 오른쪽에 위치하면서 해당 수보다 큰 수 중에서 가장 왼쪽에 위치한 수이다. 간단하게는 해당 수를 기준으로 오른쪽으로 한 칸씩 탐색하며 해당 수보다 큰 수가 나오면 이를 출력하는 과정을 반복하면 되지만 수열의 크기가 최대 1,000,000이어서 O(N²)의 시간 복잡도로는 해결할 수 없다. 해당...