공부의 발자취를 남기는 블로그

문제분석 목표: 1 ,10 ,100, 1000 ... 같은 오르내리락 할수있는 버튼을 사용하여, 최소값으로 0층가기 문제를 이해하셧다면, 각 자릿수마다 엘리베이터를 올릴지, 내릴지를 판단해야합니다. 올리면 무조건 이득보는 숫자는 6,7,8,9 이며, 내리면 무조건 이득보는 숫자는 0,1,2,3,4 입니다. 문제는 숫자 5입니다. 숫자 5일때 경우에따라서 올리는게 더 좋을때도잇고, 내릴때 더 좋을때가있습니다. EX) 45 : 45인경우는 첫째자리 5를 내리는게 더 빨리 도착합니다 = 9 5555: 첫째자리 5를 올리는게 더 빨리 도착합니다 = 18 5555> 5560->5600->6000->10000->0 : 5+4+4+4+1=18 55: 55인 경우는 첫째자리를 올리든, 내리든 값이 똑같습니다 =10 5..

문제분석 오랜만에 레벨 3 문제를 풀어보았다. 문제를 요약해보자면 1.적당한수 e 가 주어지고, e보다 작은 여러개의 start지점이 주어집니다. 2.서로다른 start지점에서 e부터 최대 출몰하는 숫자를 입력합니다. 3. 최대 출몰하는 숫자가 여러개라면 작은숫자를 우선 First Try: 1.먼저, 최대 출몰하는 숫자를 알려면, 그 숫자가 몇번 출몰하려는지 알아야 합니다. 억억단에서 그 숫자가 출몰하는횟수는 약수의 갯수 라는걸 알았고, 약수의 갯수를구합니다. 2.약수의 갯수를 구하여 약수 배열에 저장합니다. 매번 그 약수를 다시 구하는건 비효율적이니 dp 방식처럼 배열에 저장을 해놓았습니다. 약수의 갯수를 구하는 로직이 여러개 있지만, 해당문제는 여러개의 약수를 동시에 구해야하기때문에 다음 로직을 사용..

문제분석 테이블 해시 함수 로직을 구현하는 문제이다. 다르게 생각할필요는없다. 문제에서 하라는대로만 하면 끝이다. 이 문제를 들고온 이유는 새롭게 배운 두가지 테크닉을 작성하는겸 소개해드리고싶어서다. 먼저, 2번부터 로직을 시행할것이다. 2번의 요건은 col번째 요소로 정렬을하고, 동일하면 기본키(첫번째)로 정렬하는 문제다. 즉, 이중 정렬을 원하신다. 보통, 필자는 이중정렬을 거의 Comparator을 구현해서 표현했다. 이렇게다. 왜냐하면, 이중정렬을 람다식으로 불가능한거 아닌가? 싶엇다. 하지만, 웬걸 이중정렬도 람다식이 된다. 이걸 이제알았다니 .. 삼항 연산자로 가능하다. 3번과 4번을 동시에 처리하겠다. 각 컬럼을 mod idx하고 나온 값들을 XOR 한 최종값을 출력하는것이다. 자바에선 XO..

문제분석 정해진 레시피가있습니다. 빵 - 야채 -고기 - 빵 상수는 재료가 떨어지는걸 보고, 빵 - 야채 -고기 -빵 패턴이 보이면 바로 제작합니다. -> 이걸 구현만 해내시면됩니다. 하지만 최적화를 시켜야하는게 문제죠 First Try: replaceFirst 문법 사용하여 풀기 우선 ingredient의 원소를 모두 문자열로 받아씁니다. EX) 211231231 그리고 빵 - 야채 - 고기 - 빵 인 "1231" 패턴을 찾아서 빈칸으로 만들고(지우기) 햄버거 1개를 추가합니다. replaceFirst는 맨 처음 '1231'패턴을 찾기만 하는 문법입니다. 이걸 햄버거가 더이상 안만들어질때까지 반복시킵니다. ---> But, 효율성 오류 추측되는 이유, replaceFirst 내부에서 O(n)만큼 계속 ..

문제분석: 주어진 병사, 라운드마다 정해진 적들, 주어진 무적권 이 3가지의 정보를 사용하여 라운드를 최대 어디까지 도달할수 있는가를 구하는 문제다. 시작하기전에 , 제한사항을 보면 라운드는 100만 라운드며, 병사는 10억까지 다룰수 있다. First Try: 이분탐색을 사용해보자. 아무리 큰 수라도 시간복잡도 log(n) 앞에선 엄청난 효율성을 보여준다. 이분탐색의 기준은 당연히 우리가 구하고싶은 "최대 라운드" 이다. 최소 라운드 = 1 최대 라운드 = 주어진 적 배치 배열의 길이 그 후, 중간값을 구한뒤 최소라운드 ~ 중간값 라운드 까지, "내 군사들로 막을수 있는가?" 를 판별한다. 막을 수 있다면 더 높은라운드 까지 막을수있는 가능성이 있으니, Up 막을 수 없다면 더 낮은 라운드를 탐색하기위..

Level0 이지만, 학습할 점이 많은 문제라서 가져왔습니다. 문제분석: 목표: [start,end] 로 구분이된 선분들의 겹치는 선분의 길이 구하기 First Try: 모든 선분 [Start ~ End] 까지 +1을 한뒤, 2가 넘으면 answer++ 증가 -> 보자마자 이 전략이 떠올랏습니다. 하지만, 윗 그림과 같은 케이스에서 문제가 일어납니다. [[0, 2], [-3, -1], [-2, 1]] 와 같이 중간이 파여버린 부분은 해당로직이 인식을 못하여 4를반환합니다. 2를 반환해야 하는데 말이죠, 그렇다고 정확히 파악할수있는 0.5점을 파악하기도 힘듭니다. Second Try: Start가 낮은 선분부터 선분을그려 +1을한뒤, 실시간으로 2가 넘으면 answer++ 증가 (단, 이미 체크한 점 (방..

문제 분석 : 매우 간단한 문제지만, 아이디어가 없으면 풀수 없는 문제다. (참 이런문제가 창의력 기르기 좋은 문제인것같다.) 문제를 요약하자면, 원의 반지름을 의미하는 d 값을 주어진다. 원점을 기준으로 d값만큼 원을그려서, 양수의 점을 최대 몇점까지 찍을수 있는가를 구하는문제다. 점을찍는건 K만큼 차이가난다. 단순하게, x좌표 길이, y좌표 길이만큼 이중 for문을 작성하여 점을찍을 수있는가를 판별할수 있다. 하지만 이렇게 작성하면 효울성 에러가 뜬다. 역시 최적화 과정을 거쳐야한다. 우리가, 점을 찍을수 있는지를 판별하는건 x^2+y^2

문제분석: 문제가 꽤나 난해한 문제다. 해야할일 3줄요약: 1. 콜라츠 추측으로 수열 만들기 2. 수열의 구간마다 넓이 구하기 3. 주어진 ranges로 정적분 구하기 1. 콜라츠 추측으로 수열만들기 + 2. 수열의 구간마다 넓이구하기 콜라츠 추측으로 점을 하나찍고, 이전의 점 current와 비교하여 넓이를 찍어 저장한다. 3. 주어진 ranges로 정적분구하기 여기서 정적분은 쉽게 말하자면 구간의 넓이다. EX) [1,-3] -> 1부터 마지막수열 -3까지의 넓이 [3,-2] -> 3부터 마지막수열 -2까지의 넓이 단, 시작점이 끝점보다 크면, 고정적으로 -1를 반환해야한다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..

문제분석: 목표: 여러가지 크기의 귤을 골라서 종류의수가 최소화가 되면 된다. 정해진 귤의 갯수를 골라서 종류의수가 최소화가 되길 원하니, 가장 많은 갯수를가진 종류뷰터 먼저 골라가면 된다. 종류마다 갯수를 체크하기위해, Map을 사용하였다. Map으로 귤을 모두 종류마다 담았으면, 가장 높은갯수로 정렬한뒤, 갯수를 빼며 종류수를 체크하자. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.util.*; class Solution { public int solution(int k, int[] tangerine) { int answer = 0; //Key: 크기 , value: 갯수 Map map ..

문제분석 문제 이해가 좀 난해한 문제다. 3줄요약: 1.조건 1에선 철수는 모두 나눌수있고, 영희는 모두 못나누는 최대값 A 2.조건 2에선 영희는 모두 나눌수 있고, 철수는 모두 나눌수있는 최대값 B 3.A와 B중 가장큰 수를 반환 제한사항을 보면 알겟지만, 원소의 크기와 길이가 좀..크다.. 그래서 제일 쉽게 푸는게 반복문이지만 반복문으로 풀다가 효율성 오류 걱정부터햇다. 근데 반복문으로해도 효율성 통과가 되더라.. 메소드를 2개 만들었다. 첫번째로, 철수나 영희의 배열을 모두 나눌수있는 숫자들을 판별해서 배열로 반환하는 메소드 두번째 메소드로, 첫번째로 구한 숫자들로 상대방의 숫자들을 나눌수 없는지를 판별한뒤, 가장큰값을 반환한다. 그 뒤, 앞서 정리한 세줄요약대로 로직을 작성한다. 문제풀이 1 2..