코딩 테스트/프로그래머스
프로그래머스 - 풍선 터트리기 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 풍선이 끝까지 살아남기 위해서는 해당 풍선을 기준으로 오른쪽과 왼쪽에서 가장 작은 값 둘 중 하나보다 작아야 합니다. 왼쪽에서 작은 값만 살려서 오고 오른쪽에서 작은 값만 살려서 온 뒤 현재 풍선이 둘다 보다 작으면 더큰것을 살릴수 있는 기회를 사용하지않고 남길수 있고. 둘중 하나보다만 크다면 기회를 사용하여 남길수있습니다. 그러나 둘다보다 크다면 기회가 한번이기 때문에 불가능합니다. 주의점 매번 오른쪽과 왼쪽을 계산하니까 시간초과가 발생하여 DP를 통해서 해결하였습니다. class..
프로그래머스 - 2 x n 타일링 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 타일 채우기 문제로 dp를 이용해서 풀었다. n = 1 이면 1개 (세로 1) n = 2 이면 2개 (세로 2, 가로 2) n - 3 이면 3개 (세로 3, 세로 1 가로 2, 가로2 세로 1) n = 3 인 경우를 보면 n = 1일때 가로2개와 세로 2개 더 세우는 경우 n = 2일때 세로 타일을 하나더 세우는 경우 두 경우의 합에 겹치는 경우를 빼면 된다. c..
프로그래머스 - 추석 트래픽 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/17676 = 고 하게 되면 안됩니다. - 1부터 10개를 가진다고하면 1, 2, 3, 4, ,5, 6, 7, 8, 9, 10인데 1 + 10 은 11이기 때문이죠. - 위와 동일하게 1초부터 1초의 범위를 가진다면 1,000 ~ 1.999 까지 라는 겁니다. import java.text.SimpleDateFormat; import java.util.*; class Solution { public static int solution(String[] lines) throws Exception { SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss.SSS"); int[] count..
프로그래머스 - 카카오프렌즈 컬러링북 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr dfs로 동일 색상을 방문해가면서 영역의 크기를 구하면 된다. 주의할점은 영역으 값이 0인 경우는 색상이 없는 경우로 배제 해야한다는 점이다. import java.util.LinkedList; import java.util.Queue; // 프로그래머스 카카오프렌즈 컬러링북 문제 class ColoringBook { static boolean[][] visited; static..
프로그래머스 - 전화번호 목록 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 정렬을 한 뒤 바로 뒤에 것 만 확인해서 같은지 체크하면된다. 19 193 195 라고한다면 첫번째와 두번째를 비교하자마자 false이 되기 때문에 그 뒤는 체크할 필요가 없다. 문자열이기 때문에 19 184 111 194 배열이라면 졍렬은 111 184 19 194 으로 된다. import java.util.Arrays; // 프로그래머스 전화번호 목록 문제 class ..
프로그래머스 - 순위 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 보통 순위 문제는 위상정렬을 이용한 순위 출력문제와 이번문제와 같은 확실한 순위를 묻는 방식이 있는데 문제도 안보고 대충 순위여서 위상정렬로 풀려고하다가 피똥을싸고 플로이드 워샬 알로리즘을 통해서 해결하였다. import java.util.Arrays; // 프로그래머스 순위 문제 class Ranking { static final int MAx = 10000; public int solution(int n, int[][] results) { int answer = 0; int[][..
프로그래머스 - 3진법 뒤집기 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 자바에서 진법을 Integer의 메서드를 이용하면 쉽게 가능하다 . Integer.toString(숫자, 진법)을 이용하면 숫자를 진법으로 변경된 문자로 얻을수 있다. Integer.parseInt(문자, 진법)을 이용하면 문자를 진업으로 변경된 숫자를 얻을수 있다. int n = 3; String str3 = Integer.to..
프로그래머스 - 가장 먼 노드 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 그래프 이론에 bfs을 통해서 1노드에서 부터의 거리를 구하여 해결 // 프로그래머스 가장 먼 노드 문제 class FurthermostNode { public int solution(int n, int[][] edge) { // 방문 여부 초기화 boolean[] visited = new boolean[n+1]; // dp를 최대값으로 초기화 int[] dp = new int[n+1]; Arrays.fill(dp, Integer.MAX_VALU..