코딩테스트

짐 챙기는 숌

풀이 방법 책이 무조건 차례대로 들어가기 때문에 if문을 사용해서 차례대로 비교해주면서 넣어주면 된다. N이 0일땐 StringTokenizer를 생성하면 nullpointer 오류가 나기 때문에 그 점만 주의하면 된다. 내 코드 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());..

전력망을 둘로 나누기

풀이 방법 트리에서 모든 전선들을 한번씩 끊어봐야겠다고 생각했다. 하나씩 끊어 보면서 한쪽의 송전탑 갯수를 세어주었다. 송전탑 수를 세기 위해 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 ..

돌다리 건너기 - 2602번

풀이 방법 먼저 재귀적으로 완전탐색을 이용해서 풀었다. 하지만 시간초과가 나오고 말았다. 그래서 DP를 추가해 주었다. DP는 [현재 밟은 곳][찾고 있는 문자 인덱스][돌다리 종류] 로 나타내었다. 예제 입력 3번을 예로 들자면 GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG 이렇게 찾은 후 다음 G에서 GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG 똑같이 반복 될것이다. 그래서 위쪽의 돌다리에서 3번째 G를 밟은 후 현재는 아래쪽의 처음 나오는 G를 밟고 있으면 현재 밟은 곳에서 찾고 있는 문자가 인덱스와 돌다리의 종류가 같은 케이스가 나온..

괄호 제거 - 2800번

풀이 방법 각 괄호의 경우의 수를 구하기 위해 조합을 뽑아냈다. 먼저 괄호의 인덱스를 map에 저장해주고 그 인덱스르 바탕으로 조합의 경우의 수를 계산했다. 경우의 수를 바탕으로 괄호를 제거하고 출력해 주었다. 재귀 함수로 조합을 계산할 수 있다. (((0)))

듣보잡 - 1764번

풀이 방법 contains의 시간복잡도가 list보다 set이 좋아서 먼저 hashset에 듣도 못한 사람을 넣어주고 보도 못한 사람을 contains으로 확인 후 있으면 list에 넣어주었다. 출력할 때는 sort를 이용해서 사전순으로 정렬 후 출력했다. 내 코드 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 StringToken..

징검다리 건너기 - 21317번

풀이 방법 다이나믹 프로그래밍을 사용해서 풀이했다. 중요한 게 매우 큰 점프를 한번만 사용할 수 있다는 것이다. 그래서 매우 큰 점프를 사용할 수 있는 모든 경우의 수에 넣어주었다. 나머지는 DP의 Bottom-Up 방식으로 풀이하면 된다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String..

스티커 - 9465번

풀이 방법 DP의 Bottom-Up 방식을 이용해서 풀이했다. 맨앞의 스티커 두개를 먼저 넣어주고 다음 스티커부터 대각선방향으로 더한 값과 서로 변을 공유하는 스티커 중 더 큰값을 찾아주었다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTo..

말이 되고픈 원숭이 - 1600번

풀이 방법 BFS를 이용해서 최단경로를 구하는 방법을 이용했다. 이동할 수 있는 동작마다 if문을 이용해서 우선순위 큐에 넣어주었다. 여기서 방문을 체크하는 visited를 조심해야 했다. 그냥 테이블과 동일하게 visited를 구현하게 되면 말처럼 움직이는 동작과 그냥 인접한 칸으로 움직이는 동작을 구분하지 않게 된다. 그래서 말처럼 움직이는 동작을 한 횟수별로 따로 visited 테이블을 만들어주어야 한다. 나머지는 기본 BFS 동일하게 풀이하면 된다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { private int x; private int y; private int..

뒤집기 II - 1455번

풀이 방법 a, b칸을 뒤집으면 하위 모든 칸들이 뒤집히기 때문에 맨 위에서부터 확인해서 뒤집어 주었다. 세로와 가로 둘다 줄여 나가는것이 아닌 한쪽만 기준으로 잡고 줄여나가도 된다. 내 코드 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.pars..