문제 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 풀이 순열과 Set 자료구조를 통해 해결했습니다. 우선 N개의 카드 중 K개의 카드를 순서를 고려하여 뽑아야하기 때문에, 순열 백트래킹을 통해 selected[] 배열에 인덱스를 저장합니다. 그리고 card[] 배열에 대입하여 해당하는 카드 번호들을 뽑아냅니다. 이때 번호의 나열은 StringBuilder를 이용해 합치고 그 결과를 Set에 집어넣습니다. Set은 중복을 허용하지 않는 자료구조입니다. 그렇기 때문에 Set의 size를 구하면 중복되지 않은 경우의 수가 나오게 됩니다. 아..
Java/BOJ
문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 풀이 스택 자료구조를 활용한 문제입니다. stack에는 순서대로 들어오는 각 층을 쌓습니다. 여기서 조건을 잘 정리해야합니다. 우선, 스택이 비어있거나 stack의 peek이 들어올 y좌표보다 작을 때는 push를 합니다. 만약 peek이 크다면, peek이 y좌표보다 작을때마다 pop을 수행하고 pop 개수는 건물의 개수가 됩니다. 그리..
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 우선 순위 큐를 이용해 문제를 해결했습니다. 단순히 반복문 두 개로도 해결할 수는 있지만, 시간 복잡도가 300,000*300,000으로 제한 범위를 훨씬 넘어가게 됩니다. 풀이 방법은 다음과 같습니다. 1. 우선 보석을 무게에 대해 오름차순으로 정렬합니다. 그리고 무게가 같다면 가격에 대해 내림차순 정렬합니다. 2. 가방은 ..
문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 최소 공통 조상을 찾는 문제입니다. 위 문제는 sparse table이나 세그먼트 트리를 사용하지 않고, dfs로도 구현이 가능합니다. 우선 입력 값을 Arraylist[] 배열에 넣어 트리 상의 연결된 두 정점을 표현합니다. 그리고 parents[] 배열과 depth[] 배열을 통해 각 정점의 부모와 깊이를 저장합니다. (findDepthAndParents 메서드) 그럼 pare..
문제 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 가장 가까운 공통 조상을 찾는 문제입니다. LCA의 풀이법인, 세그먼트 트리나, Sparse table을 사용하지 않고, parents, check 배열을 통해 해결했습니다. 우선 입력이 부모와 자식이 구분되기 때문에, 입력을 받으며 해당 정점의 부모를 parents 배열에 입력합니다. 그리고 공통 조상을 구할 노드 중 하나를 pare..
문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 풀이 순열이 포함된 구현 문제입니다. 처음에는, 점수를 계산하는 과정을 큐로 구현을 했습니다. Base를 돌고 홈으로 오는 선수들을 큐 자료형을 표현했는데 시간 초과가 나서, 점수를 산정하는 과정을 boolean[] 배열을 통해 경우를 따져가는 식으로 변경했습니다. 그리고 순열 시에 1번 타자는 항상 4번 째에 위치하는 것을 고려해, 해당 depth일 때는 배정을 한 칸씩 뒤로 미루었습니다. 아래..
