코딩테스트

교점에 별 만들기

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

벽 부수고 이동하고 - 2206번

풀이 방법 처음에는 그냥 bfs로 풀이했다가 고생했다. 이 문제는 벽을 부수고 이동할때와 그냥 이동했을 경우 따로 visited를 구분해줘야 한다. 부수고 이동했을때 이전 이동한 경로를 다시 가면 안되지만 부수지 않았으면 부수고 이동했을때 갔던 노드를 가도 된다. 방문체크를 구분해서 해주는 것만 생각해주면 되는 문제이다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { int x, y, distance; boolean check; Node(int x, int y, int distance, boolean check) { this.x = x; this.y = y; this.dist..

무기 공학 - 18430번

풀이 방법 부메랑을 만들기 위해 배열을 상하좌우로 1칸씩 늘려서 만들어서 사용했다. 부메랑을 만들 수 있는 부분은 visited를 false로 하고 주변부분은 true로 해주었다. 그리고 dfs를 이용해서 모든 경우의 수를 확인해보았다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int max = 0; static int N, M; static int[][] array; static int[][] way = {{0, -1, 1, 0}, {0, -1, -1, 0}, {0, 1, -1, 0}, {0, 1, 1, 0}}; static boolean[][] visited; public stat..

어두운 건 무서워 - 16507번

풀이 방법 처음에 반복문을 통해 풀이했는데 시간초과가 나왔다. 사진크기가 1000*1000이고 Q가 10000이 된다면 1000 * 1000 * 10000번 연산하게 되어 제한시간이 초과되는 것으로 보인다. prefix sum 방법을 사용해서 풀이 했다. 배열의 (0,0) 부터 (x,y) 까지의 합을 우선 구해두고 계산할 때 꺼내 쓰는 방식이다. 내 코드 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 InputStreamReade..

뉴스 클러스터링

풀이 방법 두 문자열을 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..

에너지 모으기 - 16198번

내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static boolean[] visited; static int N; static ArrayList W; static int max = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; N = Integer.parseInt(br.readLine()); W = new ArrayList(); st = new String..

빙산 - 2573번

풀이 방법 dfs를 사용한 방법을 생각했다. 모두 다 이어져 있으면 다시 1년 지나게 하고 이어져 있지 않으면 종료하기 위해 먼저 빙산을 녹이는 함수를 작성했다. 주변을 비교해서 녹이면 되는 함수이다. dfs는 check 배열을 만들어서 위치를 갔었는지 체크하고 0이 아닌 아무 곳에서 시작했다. 동서남북으로 확인하면서 가능한 경로인지 확인하고 연결되어 있는 갯수를 반환하게 했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N; static int M; static int[][] array; static int x, y; static boolean[][] check; public ..

크게 만들기 - 2812번

풀이 방법 스택을 사용해서 앞에서부터 넣어주면서 지금 넣는 자릿수가 앞의 자릿수보다 크면 제거하는 방법을 사용했다. 출력할땐 N-K개 까지만 출력해서 자릿수를 맞춰서 출력해주었다. 내 코드 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 StringTokenizer(br.readLine()); int N = Integer.parseI..