자바

색종이와 가위 - 20444번

풀이 방법 n 번의 가위질로 만들 수 있는 조각의 개수는 (가로 + 1) * (세로 + 1) 개 이다. 이 문제는 경우의 수가 많아 이분탐색을 사용해서 풀이했다. 가로, 세로 갯수가 같을 때 조각의 개수가 가장 많이 나오게 되어서 이분탐색의 right 값을 N/2로 시작했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new ..

가장 먼 노드

풀이 방법 노드 별 최단 경로를 구하기 위해 Node 클래스를 만들어서 노드 번호와 1번에서 해당 노드까지의 길이를 가지도록 했다. bfs 를 이용해서 노드까지의 길이를 비교해서 최댓값일 경우 cnt를 증가시켜주었다. 내 코드 import java.util.*; class Solution { public int solution(int n, int[][] edge) { ArrayList list = new ArrayList(); boolean[] visited = new boolean[n + 1]; for(int i = 0; i

순위

풀이 방법 플로이드 워셜 방법을 이용해서 다른 선수들과 비교가 가능한지 알아보았다. 이길경우 1 로, 질 경우 -1 로 해서 [1,2]이고 [2,3] 이면 [1,3]이 가능하도록 했다. 내 코드 class Solution { public int solution(int n, int[][] results) { int answer = n; int[][] array = new int[n + 1][n + 1]; for(int i = 0; i < results.length; i++){ array[results[i][0]][results[i][1]] = 1; array[results[i][1]][results[i][0]] = -1; } for(int k = 1; k

네트워트 연결 - 1922번

풀이 방법 최소 비용 신장 트리를 만드는 문제이다. 그리디 방법을 사용해서 트리를 만들었는데 각 경로를 나타내는 Node 클래스를 만들어서 priorityQueue를 이용했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int N = Integer.parseInt(br.readLine()); int M = Integ..

오리 - 12933번

풀이 방법 입력이 어떻게 주어지는지 생각하는 데 시간이 좀 걸렸다. 입력은 무조건 5의 배수의 길이로 주어지지 않고 5의 배수의 길이로 주어졌더라도 오리의 울음소리를 만들 수 있게 딱 나누어 떨어지지 않았다. 녹음한 소리가 올바르지 않은 경우 입력이 5의 배수의 길이로 주어지지 않은 경우 울음 소리를 만들 수 있게 딱 나누어 떨어지지 않은 경우 이 세가지를 생각해서 풀이했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..

추석 트래픽

풀이 방법 먼저 주어진 문자열을 나눠서 시간을 int로 나타내서 계산해주었다. 각 범위를 계산해 주기 위해 변화가 있는 로그가 시작하고 끝나는 모든 지점에서 1초 범위로 속하는 로그들의 개수를 세어주었다. 범위에 속하기 위해 시작점이 범위 안에 들어 있는 경우 끝나는 지점이 범위 안에 들어 있는 경우 시작점과 끝나는 지점이 범위보다 클 경우 이 세가지 경우를 생각해서 count해 주었다. 내 코드 import java.util.*; class Solution { public int solution(String[] lines) { int[][] array = new int[lines.length][2]; for(int i = 0 ; i < lines.length; i++){ double x = 60 * 6..

운동 - 1956번

풀이 방법 플로이드 와샬 방법을 이용해서 모든 경로를 구해주었다. 자기 자신으로 가는 경로가 있는 경우 사이클이 있는 거라서 그 중 최소 값을 찾아 주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int V, E; static int[][] array; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(..

아이템 줍기

풀이 방법 문제를 풀기 위해 테두리를 먼저 구해주었다. 하지만 그냥 테두리를 구하게 되면 ㄷ으로 꺽이는 경로는 컴퓨터 상 경로를 찾기 힘들어서 지형자체를 2배 해서 풀어주었다. 2배 해서 테두리를 구해준 뒤 dfs를 통해 최단 경로를 구해주었다. 아이템 위치를 찾게 되면 아이템은 visited를 다시 false 처리 해줘서 다시 탐색할 수 있도록 하였다. 내 코드 import java.util.*; class Solution { static int[][] array; static int[][] way = {{1,0}, {-1,0}, {0,1}, {0,-1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; static boolean[][] visited; static int answer..

이동하기 - 11048번

DP 를 이용해서 입력 받을 때 바로 그 위치의 최댓값을 구해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, M; static int[][] array; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Int..

교점에 별 만들기

풀이 방법 모든 직선들을 비교해서 교점을 찾아주었다. 교점을 찾아서 list에 넣어줄때 정수로 된 좌표가 아니면 넣지 않고 제거 했다. 교점을 찾을때 그릴 좌표평면의 크기를 찾기 위해 x,y 별로 Max, Min 값을 구해서 크기를 구해주었다. 좌표 평면을 모두 .으로 그리고 찾은 좌표의 값을 * 로 바꿔주었다. 이 문제에서는 정수의 범위를 생각하는 것이 중요하다. 직선 식에 있는 정수들을 -100000 이상 100000 이하이기 때문에 계산하게 되면 최악의 경우 100000 * 100000 이 되서 Long 타입으로 바꿔서 계산해 주었다. 내 코드 import java.awt.*; import java.io.*; import java.util.*; class Solution { static int mi..