본문 바로가기

전체 글

(276)
Programmers - 가장 큰 정사각형 찾기 with JAVA (V) 문제 0, 1로 이루어진 2차원 배열이 주어진다. 이 때, 1로만 이루어진 정사각형의 넓이 중 가장 큰 넓이를 반환하라. 로직 해당 문제는 DP로 해결을 했다. 처음에는 DP를 항상 일차원적으로만 해석해왔기에 DP라는 아이디어를 떠올리기조차 어려웠다. 하지만 완탐을 하기에는 시간복잡도를 고려해보았을 때, 불가능하다. DP 아이디어는 "현재 x,y좌표에 맞는 최대 넓이는 (x-1, y), (x, y-1), (x-1, y-1)에 해당 하는 값의 최소값 + 1이다." 예를 들어보면, 아래와 같은 2차원 배열이 있다고 가정하자. 매번 1이 나올때마다 체크한다. 0111 1111 1111 0010 (0, 1)까지의 최대 넓이는 1이다. (0, 2)까지의 최대 넓이는 1이다. (0, 3)까지의 최대 넓이는 1이다...
Programmers - 줄 서는 방법 with JAVA 문제 1~n번 까지 번호를 갖는 사람이 있다. n은 20이하의 자연수이다. 사람을 사전순으로 나열할때, k번째 줄은 어떤 순서인가? 로직 사실 이 문제는 효율성 테스트에서 애를 많이 먹었다. 하지만 로직에 문제가 있던게 아닌 long이 아닌 int를 사용해서 오류가 낫던 것이다. 이런 실수를 줄이는 게 중요한 것 같다. 로직은 간단하다 예를 들어, 20명이 줄을 선다면, 19! 간격으로 앞자리가 바뀐다. 이 아이디어만 고려하면 된다. 항상 자료형을 신경쓰자 !! 코드 import java.util.*; class Solution { public List solution(int n, long k) { List answer = new ArrayList(); List check = new ArrayList()..
Parameter 0 of constructor in ... required a bean of type ... that could not be found. 최근한 5일간 해당 오류를 해결하기 위해 많은 노력을 기울였다. 그에 따른 나름의 고찰을 정리해보고자 한다. 1. 기본적인 의미 기본적으로 해당 오류는 연결하고자 하는 빈을 못찾겠다는 의미이다. 현재 서버를 Spring으로 작성하고 있는데, Spring의 가장 큰 특징은 제어의 역전이라고 할 수 있다. 이러한 빈들을 주입할 때, xml을 작성하지 않고도 SpringBoot에서는 자동으로 빈을 주입해준다. 하지만 이 오류는 이러한 주입을 하려고 하는데 주입하고자 하는 빈을 못찾겠다는 의미이다. 2. 해결방법 2-1. 명시해서 알려주는 방법 - 해당 방법은 약간 너가 못찾겠으면 내가 패키지명을 알려줄테니까 거기서 찾아봐라는 의미이다. 아래와 같이 작성시 해당 패키지에서 찾고자 하는 빈을 찾아준다. @Spri..
Programmers - 파괴되지 않은 건물 with JAVA (V) 문제 2차원 배열이 주어진다. 그리고 각 스킬들이 주어지는데 스킬은 공격, 회복 두 개로 나뉜다. 공격시에는 해당 범위만큼 2차원배열에서 특정 값을 빼고 회복시에는 해당 범위만큼 2차원 배열에서 특정 값을 더 해준다. 결과적으로 배열에서 1보다 큰 칸의 개수를 구하라. 로직 첫번째로 굉장히 쉬워보이는 문제지만 요구사항을 확인해보면 배열 한 행과 열의 크기는 최대 1000, skill의 개수는 최대 25000이다. 따라서 25000 * 1000 * 1000, O(KNM)의 시간복잡도로는 효율성 테스트를 통과할 수 없다. (스킬 수 K, 맵의 가로 N, 맵의 세로 M) 누적합을 통해 해결하고자 한다. 로직은 우선 아래와 같다. 1. 스킬마다 누적합을 위한 값을 구한다. O(K) 2. 구한 누적합으로 최종 누..
Programmers - 가장 긴 팰린드롬 (V) 문제 문자열 s의 부분 문자열 중 앞뒤를 뒤집어도 똑같은 문자열 중 가장 긴 문자열을 구하라. 로직 1. s의 길이를 구한다. 2. s의 초기 길이부터 1을 빼가며 진행 3. 앞뒤로 같은지 판단하고 같으면 종료 이 문제는 어렵지 않지만 효율성에서 .substring, .StringBuilder의 reverse, 등을 활용해 경우마다 부분문자열을 구하는 것보다는 인덱스를 통해 비교하는 것이 더 효율적이라는 것을 기록하기 위해서 작성한다. 코드 class Solution{ public int solution(String s){ int length = s.length(); while(true){ if(length
Programmers - 징검다리 건너기 with JAVA (V) 문제 징검다리의 칸마다 건널 수 있는 횟수가 정해져 주어지고 사람이 건너 뛸 수 있는 칸의 수가 주어진다. 이 때, 최대한 많은 사람들이 건너게 하고자 할 때, 최대 몇명이 건널 수 있는가? 로직 이 문제에 대해서 많은 고찰이 있었다. 시간 복작도를 충분히 고려해야하는 문제이다. 첫번째 생각했던 방법은 0~k, 1~k+1마다 최댓값을 구하고 이 최댓값들 사이의 최솟값이 정답이 되는 로직을 설정하였다. 이는 시간복잡도에서 큰 문제를 갖는데 매 순간 정렬을 해줘야 하기에 문제가 생긴다. 따라서, 이분탐색으로 해결을 하였다. 1. 주어진 배열 정렬해 리스트에 담는다. 2. 이분 탐색으로 숫자를 정해가며 해당 리스트에서 지금 값을 뺐을 때, k보다 작거나 같거나 크거나를 고려하여 start, end 인덱스를 변..
Programmers - 124 나라의 숫자 with JAVA 문제 124나라의 숫자는 아래와 같이 표현된다 1 - 1 2 - 2 3 - 4 4 - 11 5 - 12 6 - 14 n을 124나라의 숫자로 표현하라. 로직 설명하기 어렵지만 설명하자면.. n에서 누적합(sum)을 빼고 3의 현재 배수(now)로 나눈 값이 3의 전의 배수(before)보다 (0보다 크지만 before보단 작다, before보단 크지만 before의 2배보다 작다 , before의 2배보다 크거나 0과 같다.)에 따라 1, 2, 4가 추가되고 만약 sum+now가 n보다 크다면 종료된다. 예를 들어서 보면 아래와 같다. (n = 15, sum = 0) now = 3의 1의 배수 = 3 before = 3의 0의 배수 = 1 (n-sum)이 before의 값에 따라 1, 2, 4 중 하나로..
Programmers - 삼각 달팽이 with JAVA 문제 반시계방향으로 1층부터 n층까지 채워 피라미드를 만든다. 로직 - 재귀함수를 사용한다. - 아래로 가는경우(x+1), 위로가는 경우(x-1, y-1), 옆으로 가는 경우(y+1) 로 나누어 차례대로 돌린다. 코드1 import java.util.*; class Solution { public List solution(int n) { List answer = new ArrayList(); int[][] map = new int[n][n]; find(0, 0, 0, 1, n, map); for(int i=0; i