프로그래머스
가장 먼 노드
풀이 방법 노드 별 최단 경로를 구하기 위해 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
추석 트래픽
풀이 방법 먼저 주어진 문자열을 나눠서 시간을 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..
아이템 줍기
풀이 방법 문제를 풀기 위해 테두리를 먼저 구해주었다. 하지만 그냥 테두리를 구하게 되면 ㄷ으로 꺽이는 경로는 컴퓨터 상 경로를 찾기 힘들어서 지형자체를 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..
교점에 별 만들기
풀이 방법 모든 직선들을 비교해서 교점을 찾아주었다. 교점을 찾아서 list에 넣어줄때 정수로 된 좌표가 아니면 넣지 않고 제거 했다. 교점을 찾을때 그릴 좌표평면의 크기를 찾기 위해 x,y 별로 Max, Min 값을 구해서 크기를 구해주었다. 좌표 평면을 모두 .으로 그리고 찾은 좌표의 값을 * 로 바꿔주었다. 이 문제에서는 정수의 범위를 생각하는 것이 중요하다. 직선 식에 있는 정수들을 -100000 이상 100000 이하이기 때문에 계산하게 되면 최악의 경우 100000 * 100000 이 되서 Long 타입으로 바꿔서 계산해 주었다. 내 코드 import java.awt.*; import java.io.*; import java.util.*; class Solution { static int mi..
뉴스 클러스터링
풀이 방법 두 문자열을 2글자씩 나눠서 list에 넣어주었다. 넣을 때 영어로만 구성되어 있는지 확인해서 다른 문자가 포함되어 있으면 넣지 않았다. (matches가 떠오르지 않아 그냥 비교했다.) 그 후 list에 들어있는 원소들끼리 비교해서 동일하면 교집합 갯수를 늘려주었다. 비교할 두 집합이 모두 공집합일 경우엔 1이 되고 그렇지 않고 교집합이 0 일 땐 1이 되지 않는다는 것을 주의해야 한다. 내 코드 import java.util.*; class Solution { public int solution(String str1, String str2) { int answer = 0; ArrayList list1 = new ArrayList(); ArrayList list2 = new ArrayList..
단체 사진 찍기
풀이 방법 dfs로 모든 경우의 수를 구해서 각 경우의 수마다 조건에 만족하면 count를 증가시켜줬다. 내 코드 class Solution { static boolean[] check; static String[] array = {"A", "C", "F", "J", "M", "N", "R", "T"}; static int count; public int solution(int n, String[] data) { check = new boolean[8]; count = 0; dfs(0, "", 0, data); return count; } static boolean comfirm(String str, String[] data){ for(int i = 0 ;i < data.length; i++){ Stri..
카카오프렌즈 컬러링북
풀이 방법 dfs를 이용해서 연결되어 있는 영역의 갯수를 세어주었다. way배열로 상하좌우 방향을 이동하도록 하고 check로 체크한 부분인지 확인해주었다. 그림 배열의 처음부터 돌면서 check 되지 않은 부분을 dfs 돌려서 영역 크기를 구하고 최댓값을 구해주었다. 내 코드 class Solution { static int[][] way = {{1,0}, {-1,0}, {0,1}, {0,-1}}; static boolean[][] check; public int[] solution(int m, int n, int[][] picture) { int numberOfArea = 0; int maxSizeOfOneArea = 0; check = new boolean[m][n]; for(int i = 0; i..
전력망을 둘로 나누기
풀이 방법 트리에서 모든 전선들을 한번씩 끊어봐야겠다고 생각했다. 하나씩 끊어 보면서 한쪽의 송전탑 갯수를 세어주었다. 송전탑 수를 세기 위해 dfs를 이용한 완전탐색을 사용했다. (n - 한쪽 송전탑 갯수) = 나머지 한쪽 송전탑 갯수 (나머지 한쪽 송전탑 갯수 - 한쪽 송전탑 갯수) 를 절댓값 처리해준 뒤 가장 작은 값을 찾아주었다. 내 코드 import java.util.*; class Solution { static ArrayList graph; static boolean[] check; public int solution(int n, int[][] wires) { int answer = 100; for(int j = 0; j< wires.length;j++){ graph = new ArrayLi..
최소직사각형
풀이 방법 위클리 챌린지 8주차 문제로 보니까 간단한 문제길래 빠르게 풀었다. 명함들을 차례대로 지갑에 넣어줄때마다 회전시키면서 작은 쪽으로 넣어주었다. 내 코드 import java.util.*; class Solution { public int solution(int[][] sizes) { int array[] = {0, 0}; for(int i = 0;i< sizes.length; i++){ int w1 = Math.max(array[0], sizes[i][0]); int h1 = Math.max(array[1], sizes[i][1]); int w2 = Math.max(array[0], sizes[i][1]); int h2 = Math.max(array[1], sizes[i][0]); if(w1 ..