코딩브론즈

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 1) PriorityQueue 를 2개 사용한다. (최대힙, 최소힙) 2) 입력받은 숫자를 하나씩 넣는다. 2-1) 맨 처음 maxHeap이 비어있을경우 maxHeap에 우선적으로 넣는다. 2-2) 들어올 숫자가 maxHeap의 peek 값보다 작으면 무조건 maxHeap에 넣는다. 만약 maxHeap의 크기가 minHeap의 크기 + 2 보다 커지면 maxHeap의 peek..

https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 풀이 1) 주어진 수영장 벽의 최대 높이 maxHeight 구하기 2) 1부터 maxHeight 까지 for문을 돌려서 수영장 벽의 높이와 같은 노드를 찾아낸다. 3) 해당 노드의 좌표에서 bfs 탐색을 한다. 3-1) 물은 위에서 아래로만 흐른다. 따라서 현재 높이 h 보다 작거나 같은 노드를 탐색한다. 3-2) 이때 지나간 경로를 Queue를 통해 저장해 놓는다. (pa..

https://www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 풀이 0) 주어진 조각의 총 개수를 구한다. 1) 조각의 총 개수로 만들수 있는 모든 경우를 구한다.(DFS) 2) 위의 경우 중 모든 조각들이 이어져 있는 경우를 구한다. 2-1) 임의의 조각 하나에서 BFS. (이어진 조각들의 개수 == 총 조각의 개수) 인 경우 모든 조각이 이어져있는 것이다. 3) 원본에서 2)의 경우로 옮기는 최소 비용을 구한다. 3-1) 이때 이동의 기준은 가장가까운..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 첫번째 풀이 - 매우 비효율 0) 준비물 class( 채널번호, 키 입력 회수, 방향키를 눌렀는지 여부 ) boolean isVisited[1000000][2] (방향키를 눌렀을경우와 안눌렀을 경우) bfs() 1) 방향키를 누르는 순간 더이상 숫자키를 누를수 없다. 2) bfs() 의 Queue에 (100, 0, true) 와 (살아있는 숫자키, 1, false)를 넣는다. 3)..

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 1) ArrayList에 입력을 다 담는다. 2) list를 정렬한다. 3) list를 출력한다. 주의사항 1) Arrays.sort() 시 시간초과이다. 2) print 로 출력하면 시간초과이다. package com.baekJoon; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOEx..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 1) 마법사 상어가 시전한 단계 L 에 따라 배열을 구간별로 나눈다. 2) 나눌 수 있는 모든 케이스에서 다음 과정을 할 것이다. 2-1) 나눠진 원본 배열을 temp[][]배열에 복사한다. 3) temp[][] 배열을 시계방향으로 90도 회전한 후 원본 배열에 집어넣는다. 4) bfs를 돌아 4방에 얼음이 없거나 장외인 경우가 3칸 이상일 경우 A[r][c] 1 감소 5..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 풀이 1) 4중 for문으로 모든 경우의 r, c, d1, d2 를 구한다. 2) 5번 선거구를 구한다. -> 먼저 4각형을 5로 채운 후 4개의 모서리를 깎는 방식으로 했다. 3) 나머지 선거구를 구한다. 4) 모든 선거구의 인구수를 populration 배열에 저장한 후 최대값과 최소값의 차이의 최소값을 갱신한다. 5) 최소값의 차이의 최소값을 출력한다. 주의사항 1) 5번 선거구를 구할때 어렵게 ..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 0) 준비물 최소 차이를 저장할 int 형 변수 minChai = Integer.MAX_VALUE 인접리스트 graph[] 1) 조합으로 N개중 1개~N/2 개 뽑는 모든 경우를 구한다. 2) 1)에서 나온 조합으로 팀을 가른다. 3) 갈라진 팀이 연결되어있지 않다면 다음 조합으로 넘어간다. 4) 갈라진 팀이 연결되어 있다면 각 팀의 인구수 차이를 구하여 최소 차를 갱신한다. 5) 모든 경우에서 가장 작은 최소차..