박카스러버

https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 저는 사방 탐색의 방향을 회전 방향순으로 하여 코드를 작성하였습니다. 사방 탐색을 하면서 범위를 넘어가게 되면 다음 방향으로 진행하도록 하였습니다. import java.util.*; class Solution { static int map[][]; static int dy[] = {0,1,0,-1}; static int dx[] = {1,0,..

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 저는 힙을 통해서 가장 낮은 값을 가져왔습니다. 그리고 이 값이 k보다 작다면 힙에서 하나 더 꺼내어 이를 공식에 대입하고 힙에 다시 넣었습니다. 마지막으로 -1이 되는 조건인 값이 k보다 작고 힙에 다른 값이 없을 때 입니다. import java.util.*; class Solution { public int solution(int[] scovi..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 저는 bfs를 통해 최소 몇번 움직이여야하는지를 판단하였습니다. 그리고 prev 배열을 통해 해당 숫자에 도달하기 전에 어떤 숫자를 거치는지를 확인하였습니다. 마지막으로 prev가 처음의 위치가 나올때까지 확인하고 이를 뒤집어서 출력하였습니다. package BOJ.BFS; import java.io.BufferedReader; import java.io.Inpu..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 저는 해당 문제를 DP를 적용하여 문제를 해결하였습니다. dp[y][x][현재 방향]에 대한 경로 값을 저장하였습니다. 마지막으로 대각선 방향일 때는 (y,x-1) , (y-1,x)가 0인지를 확인하였습니다. package BOJ.DP; import java.io.BufferedReader; import java.io.InputStreamReader; import java..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 처음에는 모든 노드에 대해 제일 긴 거리를 찾으려고 하여 시간초과가 나왔습니다. 저는 루트에서 가장 먼 것을 먼저 찾고 그다음에 해당 리프노드에서 가장 길이가 먼 것이 어느정도인지를 확인하였습니다. package BOJ.DFS; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arra..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 저는 먼저 전처리로 1의 값들을 각각의 섬에 따라 다른 값으로 변경하였습니다. 그리고 각각의 섬의 가장 외각에 있는 노드들을 BFS를 사용해 다른 섬에 도착할 때의 최소 값을 출력하였습니다. 각각의 섬에 대한 방문체크를 해야하기 때문에 visited[y좌표][x좌표][시작 섬의 번호]를 통해 방문체크를 하였습니다. 가장 외각의 경우는 해당 노드에서 사방탐색해서 0이 존재하는지를 판단하여 0이 존재한다면..

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 저는 666부터 큰 숫자들 중 666이 연속으로 포함된 String을 찾아서 해결하였습니다 package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ_1436 { public static void main(String[] args) throws Exception { BufferedRea..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제에서 시간 제한이 1초이기 때문에 O(n^2)이 된다면 시간 초과가 나오게 된다. 그래서 저는 각각의 인덱스마다 해당하는 값의 음수 값을 바이너리 서치를 통해 찾아서 시간복잡도를 O(n * log(n))으로 낮춰서 풀었습니다. package BOJ.BinarySearch; import java.io.BufferedReader; import java.io.Inp..

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 저는 트라이를 통해서 해당 문제를 해결하였습니다. 트라이를 통해서 해당 문자열의 prefix가 처음 나왔는지 탐색하였습니다. 저는 들어오는 순서대로 prefix가 있는지 판단하는 건 줄 알고 정렬을 하지 않고 계속 트라이를 통해 확인하여 틀렸습니다. 이를 정렬하여 트라이에 넣어서 문제를 해결하였습니다. package BOJ.Tree; import java.io.Buffere..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 저는 Priority Queue 를 통해 해당 가장 빨리 끝나는 시간을 찾았습니다. 이렇게해서 처음에 88%에서 틀렸습니다. 다시 문제를 자세히 읽어보니 '회의 시작시간과 끝나는 시간이 같을 수 있는다'라는 문구를 보게되었습니다. 3 1 1 0 1 2 2 이렇게 입력이 들어온다면 1 1 이 먼저 들어가고 0 1 이 나중에 들어가게 되면 0 1이 카운팅 되지 않습니다. 그래서 저는 Priority Queue 우선순위를 끝나는 시간이 같다면 시작 시간이 빠른 것이 먼저 오도록 주었습니다. package BOJ; im..