네발로 코딩하는 포메라니안

문제 https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 풀이과정 stack을 활용하여 왼->오, 오->왼으로 각각 순회하면서 자신의 왼쪽 혹은 오른쪽으로 옆면을 볼 수 있는 건물을 찾는다.stack에는 데이터가 내림차순으로 남게 하여, 자신보다 큰 건물의 수는 stack의 크기와 동일하게 하면 된다.따라서, 자신보다 작은 값은 모두 pop시키고, 남은 stack크기를 자신이 볼 수 있는 건물 수에 더해주면 된다. 이때, stack의 top에 ..

문제 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이과정 풀이 방법이 2가지가 있는데, 우선 구현하는 로직은 같고 정렬할 때 사용하는 방법만 다르다. [방법1]에서는 공의 정보를 모두 받은 후, Arrays.sort를 통해 O(nlogn)이 걸리는 정렬을 수행했고, [방법2]에서는 크기 별로 ArrayList를 만들어서 크기 별로 공을 모아서 사용했다. 공의 최대 가능한 개수에 비해, 크기의 종류가 훨씬 적었기..

문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 과정 전체에서 계속 4등분으로 자르다보면 크기가 1인 사각형까지 도달하게 된다. 크기가 1인 사각형은 자신이 흰색인지, 파란색인지 정보를 반환한다. 이를 호출한 곳에서 크기가 1인 사각형 4개의 결과를 확인하고, 모두 0이거나 1이면 그 숫자 그대로 반환하고 하나라도 일치하지 않으면 색종이 개수에 더하고 2를 반환하도록 했다. 이 방법 말고도 자르기 전에, 이..

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 과정 가장 왼쪽, 위쪽에서 출발해서 일반 블럭일 때만 DFS 탐색을 하면, 일반블럭이 무조건 1개 이상인 조건을 만족한다. 탐색 후, (블럭 사이즈가 최대) || (이전 블럭 사이즈와 같고 rainbow블럭의 개수가 같거나 큼)일 때, 가장 큰 블럭 값을 갱신해준다. 가장 큰 블럭은 삭제하면서 -2로 표시한다. import java.io.BufferedReader; import ja..

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 과정 입력된 수를 최대힙과 최소힙에 나눠 저장해서 중간 값이 최대힙의 top에 있도록 했다. 최대힙은 값을 넣을 때, 음수로 넣어서 최소힙을 활용한 최대힙을 만들었다. 최대힙의 크기 >= 최소힙의 크기로 밸런스를 맞춰서 최대힙.peek()를 출력해주면 된다. 1. mid값보다 크면, 최소힙에 삽입 1-1. 최소힙의 크기 > 최대힙의 크기면, 최대힙.offer(최소힙.po..

문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 과정 왼쪽, 왼쪽의 대각선, 위쪽에서 제일 작은 정사각형 크기 + 1이 현재 노드에서의 정사각형의 크기로 한다. 자신보다 아래에 위치한 1들은 나중에 고려하므로 생각하지 않는다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args)..

문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 과정 처음엔, 3방향 다 Math.max로 고려해줬었다. 하지만, 최단 거리가 아니기 때문에, 대각선에서 오는 것보다 위 혹은 왼쪽을 거쳐 오는 것이 총 사탕 개수가 같거나 큰 경로이므로 대각선은 고려하지 않는 것이 효율적이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 과정 BFS를 떠올리기는 쉬웠는데 K까지 도달하는 개수를 어떻게 셀 지에 대해서 생각하기가 어려웠다. 방문체크를 q에서 꺼낼 때함으로써, 현재 step에서는 중복을 허용하되 다음 step에서는 이전에 방문한 것을 제외하고 방문하도록 할 수 있었다. import java.io.BufferedReader; import java.io.InputStream..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 1. BFS 탐색으로 퍼즐(remove를 쓰기 위해 LinkedList를 사용)과 빈 칸을 각각 분석한다. 1-1. 블럭의 가장 위쪽에서 가장 왼쪽에 있는 블럭을 (0, 0)으로 맞추어 블럭들의 좌표를 변경한다. - setCenter메서드 2. 각 빈칸에 퍼즐을 넣을 수 있는 지 검사한다. 2-1. 개수가 다르면 return false; 2-2. 개수가 같으면 회전시켜가면서 넣을 ..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 과정 처음에, 어차피 왼쪽에서 오른쪽, 위에서 아래로만 움직일 수 있기 때문에 2중 반복문으로 풀 수 있을 것 같았다. 하지만, 방향까지 고려해야 돼서 생각하다가 DFS로 풀었다. 다 풀고나서, 고민하다가 방향마다 따라 결과를 저장해가면 2중 반복문으로 풀 수 있을 것 같아서 다시 풀었다. 결과적으로 속도가 2배 향상되었다. 이전 코드 : DFS import j..