BOJ 11067 모노톤길 [Java]

BOJ 11067 모노톤길 1. 문제 링크 https://www.acmicpc.net/problem/11067 2. 문제 해설 문제에서 설명한 모노톤길의 정의에 의해 x 좌표 방향으로는 무조건 증가한다. 다만, y 좌표의 경우에는 길의 모양에 따라 증가할 수도 있고 감소할 수도 있다. 그렇기 때문에, y축 방향으로 어떻게 정렬을 해주는 지가 이 문제의 핵심이다. 문제 풀이의 흐름을 아래에서 설명하겠다. 1. 일단 입력 받은 좌표들을 x 좌표 오름차순으로 정렬하고, x 좌표가 같다면 y 좌표 오름차순으로 정렬한다. 2. 현재 정렬된 좌표 순서에 따라 모노톤길을 처음부터 따라간다고 생각해보자. 6번 (3, 3) 좌표에서 7번 좌표를 갈 때 (5, 3)으로 가는 것을 기대하지만, 현재 정렬된 순서에 따르면 (..

→2022.09.13

BOJ 15685 드래곤 커브 [Java]

BOJ 15685 드래곤 커브 1. 문제 보기 https://www.acmicpc.net/problem/15685 2. 문제 해설 구현 문제다. 구현 문제는 내가 구현해야할 기능이 무엇인가를 파악하면 풀이의 방향이 보인다. 이 문제는 2가지 기능을 구현해주면 된다. 첫번째는 드래곤 커브를 그리는 기능, 두번째는 그린 후 크기가 1×1 인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 파악하는 기능이다. 두 기능을 구현해보자. 1. 드래곤 커브를 그리는 메서드 - drawDragonCurve 메서드 이 메서드를 구현하는 것이 상당히 어려웠다. 정확히 말하자면 구현이 어려웠다기보다는 드래곤 커브가 세대가 늘어날 때 추가되는 선의 규칙을 찾는 과정이 쉽지가 않았다. 세대가 늘어날때 드래곤 커브..

→2022.04.06

BOJ 14499 주사위 굴리기 [Java]

BOJ 14499 주사위 굴리기 1. 문제 링크 https://www.acmicpc.net/problem/14499 2. 문제 해설 구현 문제에서는 크게 어떤 기능을 구현해야할지를 우선적으로 생각하는 편이다. 하나의 명령의 흐름은 명령을 받으면 주사위를 굴리고 주어진 조건에 따라 값을 업데이트 해주는 것이다. 그러므로 구현해야할 기능은 크게 2가지이다. 첫번째는 주사위를 굴리는 메서드, 두번째는 주사위를 굴린 후 값을 업데이트 하는 메서드이다. 1. 주사위를 굴리는 메서드 - roll 메서드 주사위를 굴리는 건 노가다 방식으로 해결했다. 주사위 정보를 담고 있는 배열과 똑같은 배열을 하나 만들어준다. 그 후 이동하는 방향에 따라 바뀌는 주사위 정보를 바꿔준다. 2. 주사위를 굴린 후 값을 업데이트 하는 ..

→2022.03.19

BOJ 14891 톱니바퀴 [Java]

BOJ 14891 톱니바퀴 1. 문제 링크 https://www.acmicpc.net/problem/14891 2. 문제 해설 구현 문제이다. 문제를 본 후 든 생각은 톱니바퀴 1개를 돌리는 메서드와, 돌린 1개의 톱니바퀴를 기준으로 전체 톱니바퀴를 돌리는 메서드를 구현해주면 해결할 수 있겠다는 것이었다. 2가지 메서드를 구현하면서 생각했던 점을 적어보겠다. 1. 톱니바퀴 1개를 돌리는 메서드 아래 코드에서 72~88번째 줄의 코드이다. 몇 번째 톱니바퀴를 돌릴지, 어떤 방향으로 돌릴지 알아야하므로 인자로 받는다. 시계 방향이든 반시계 방향이든 결국 한칸씩 옆으로 옮기는 것이다. 그러므로 기존 톱니바퀴와 정보가 똑같은 임시 톱니바퀴 배열을 만들어 이용해준다. 시계 방향일때와 반시계 방향일때 처리해주는 방..

→2022.03.14

BOJ 11559 Puyo Puyo [Java]

BOJ 11559 Puyo Puyo 1. 문제 링크 https://www.acmicpc.net/problem/11559 2. 문제 해설 문제에서 요구하는 구현해야할 기능을 크게 3가지로 나누어보겠다. 1. 터트릴 뿌요를 파악하기 - bfs 메서드 : 같은 색 뿌요가 4개 이상 연속되는 경우를 찾아야한다. bfs, dfs를 이용하면 되겠다는 생각이 들었는데 dfs를 이용하면 ㅗ, ㅜ 같은 모양으로 연속되있는 경우를 처리하기가 까다롭기에 bfs를 이용하기로 결정하였다. 같은 색 뿌요가 연속되는 경우 list에 담아 list의 크기가 4 이상이면 터트릴 수 있고 아닌 경우는 터트릴 수 없는 방식으로 처리하고자 하였다. 2. 뿌요를 터트리기 - explode 메서드 : list에 담겨 있는 뿌요를 빈 칸으로 만..

→2022.02.09