코딩테스트/[백준] 코딩테스트 연습

무기 공학 - 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..

에너지 모으기 - 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..

짐 챙기는 숌

풀이 방법 책이 무조건 차례대로 들어가기 때문에 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());..

돌다리 건너기 - 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..

평범한 배낭 - 12865번

풀이 방법 이번 다이나믹 프로그래밍 문제에선 배낭안에 물건이 한번씩만 들어간다는 것이 중요한 조건이였다. 순서대로 넣어서 최댓값을 찾으려고 하니 중복으로 들어가게 되었다. 반복문을 반대로 돌려서 한번씩만 들어가도록 했다. 내 코드 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());..