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

문제분석 목표: 모든 음식을 스코빌 지수 K이상으로 만들기 만드는법 : 가장낮은 음식 스코빌 +(두번째로 낮은 음식 스코빌)*2 문제는 정말 쉽다. 공식을 이용하여 모든 음식을 K이상으로만 만들면된다. 하지만, 제한사항을보면 어마어마한 길이의 스코빌이 주어진다. 만약, 별 생각없이 리스트 생성하고 매번 정렬 하면서 최솟값과 2번째 최소값을 구한다면 효율성 오류가난다. 문제를 풀기위해선, 가장 낮은 음식과 두번째로 낮은 음식을 섞은뒤 배열에 넣은뒤, 다시 오름차순 정렬해서 낮은 음식과 두번째 음식을 찾아야한다. 어찌됏건, 매번 반복할때마다 숫자를 넣고 정렬을 해야한다. 그런데 이 정렬을 매우빠르게 해주는 스마트한 녀석이있는데. 바로 자료구조의 Heap(힙)이다. 자바는 Heap을 응용한 PriorityQu..

문제분석 작업진도를 나타내는 progresses 배열 작업 스피드를 나타내는 speeds 배열이 주어진다. 문제를 풀기위해서 필요한 정보는 100%작업완료까지 걸리는 시간이다. 작업완료까지 걸리는 시간은 100-작업진도/작업스피드로(나머지가있으면 +1) 구할수있다. 작업완료까지 걸리는 시간을 모두구했다면, Current_Time을 선언한다. Currrent_Time이 작업까지 걸리는시간보다 적으면 갱신하고, 그렇지 않다면 작업갯수를 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 26 27 28 29 30 31 32 33 34 35 import java.util.*; class Solution { public int..

문제분석 124 나라는 1,2,4 로만 사용하여 수를셉니다. 우리가 일상생활에서 쓰는 10진법은 숫자 0~9인 숫자 10개를사용하여 수를 나타내니 '10진법'입니다. 124나라는 1,2,4인 숫자 3개로만 사용하여 수를 나타내니, '3진법'과 같은원리로 움직입니다. 근데, 보통 3진법은 0부터세는데, 이 문제는 1부터셉니다. 그냥 3진법을 갖다 붙히면 오류가 발생합니다. 예시로, 6 : 14 , 9: 24 를 실행하면, 6=42 9=44 로 출력이됩니다. 4,5,7,8,같은 숫자들은 의도대로 잘나오지만, 3의배수만 의도대로 나오지않습니다. 이 문제를 해결하기위해선, 3의배수를 확인한뒤, -1를 하면 문제의 의도대로 출력이가능합니다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

문제분석: 이 문제는 Level3정도 줘도 대는문제다. 로직설계도 어려운데다가, 구현난이도도 어렵다. 격자마다 빛을쏘는 통로가 4개 존재한다. 격자마다 그림을 보고, 빛을받는통로까지 8개를 구현할 필요가없다. 이 문제의 빛은 범위를 넘어간다면, 반대편쪽으로 빛이 돌아오므로, 빛을 쏘는 통로만 확인한다면, 빛을 받는통로는 확인할필요가 없다. 목표는 빛의 사이클이 나오는 모든경우를 반환하는것이다. 빛의 사이클이 되는건 어느 한 통로로 빛을쏜뒤, 이미 방문한 통로를 만나면 하나의 사이클이다. 빛의 사이클을 찾으러면 모든 통로를 한번쯤은 쏴봐야한다. 즉 3차반복을돌려야한다.[모든행,모든 격자, 4개의 통로] 로직이 돌아가는 형태다. 자세한 구현은 문제 풀이에서 해설하겠다. 문제풀이: 격자마다, 4개의 통로(위,..

문제분석 문제를 이해하기는 매우쉽다. 대각선으로 선을 그은뒤, 잘라진 사각형을 제외한다. 그런데, 잘라진 사각형을 어떻게 계산해야하는지 정말 막막하다. 무슨 특수한규칙이 있을텐데, 제로베이스로 그 규칙을 떠올리긴 매우 힘들다. 작성자는, 규칙을 발견하지못해서 참고자료를 검색하고 보면서 풀었다. 8X12 사각형을 잘려나간 사각형의 모양을 자세히보면, 같은모양이 4번 반복된다. 이 반복되는 횟수가, 가로와 세로의 최소공배수의 횟수만큼 반복한다. (최소공배수 구하는 로직은 유클리드 호제법을 참고하세요!) 반복되는 모양의 갯수는 (가로/최소공배수)+(세로/최소공배수)-1 만큼의 갯수다. 전체 갯수- (최소공배수)*((가로/최소공배수)+(세로/최소공배수)-1)가 답이다. 문제풀이 1 2 3 4 5 6 7 8 9 ..

https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 문제분석 문제가 긴 이유로 링크로 대체합니다. 누군가 들어오면 [닉네임]이 들어왔습니다. 를 출력합니다. 누군가 나가면 [닉네임] 나갔습니다. 를 출력합니다. 누군가가 채팅방에서 닉네임을 바뀌거나 , 나간후 새로운 닉네임으로 들어오면 닉네임이 변경됩니다. 닉네임은 중복이 가능하며, 중복된 닉네임은 입력 Record로 주어진 id로 구분합니다. 결과는 모든 Rec..

문제분석 규칙에따라 압축을해줘서 문자열의 길이를 반환하는 문제입니다. 규칙이 1개 2개 3개...단위로 잘라서 압축합니다. 1개 2개 3개..단위로 자른 문자열중 가장 짧은 경우의 길이를 구합니다. 구현난이도가 조금 낮은게, abcabcdede의 압축결과가 2abcdede가 답이듯이, 3개 단위로 잘라도, dede를 압축할 필요가없습니다.(3개단위는 무조건 3개단위) 문제풀이 1개 2개 3개..단위마다 압축한 문자열의 길이를 저장하는 result배열 선언과 1개 2개 3개..단위마다 자른 문자열을 담아내기위한 str리스트를 저장합니다. str리스트를통해서, 자른문자열이 압축이 가능한지를 판별합니다. 첫번째 큰 반복은 1~ 문자열s의 절반만큼 반복합니다. (X개 단위 반복) 13~20라인의 2차반복은, 단..

문제분석: 처음 읽고 이게 뭘 구현하란거지? 5번은읽어봤다. 정리하자면, 입실시간기록과 퇴실시간기록이 없는 그냥 "순서" 만 있는 배열 Enter와 Leave가 주어졌다. 순서를 보고 각 사람이 반드시 만나는 사람의 수를 구하는문제다. 근데 순서만보고 각 사람이 반드시 만나는 경우가 도대체 무슨소리며, 도대체 어떤 경우인가? 바로, 모두가 들어오자마자 바로 나갔을경우다. 모두가 들어오자마자 나갔는데도, 만난경우가 있다면 기록에 상관없이 무조건 만난다 예시로 입실순서 [1,4,2,3] 퇴실순서 [2,1,3,4]를 예시로 보겠다. 1. 1번이 입실했다. 하지만 퇴실순서가 2번이 먼저니 방에 남는다. room[1] 2. 4번이 입실했다. 하지만 퇴실순서가 2번이 먼저니 방에 남는다. room[1,4] (두 사..

문제분석 문제는 A , E, I, O, U 로만 쓰여있는 사전낱말중에서 특정 단어가 몇번째 위치하는지 구하는 문제다. 무엇을 구해야하는지는 명확하니 구현으로 넘어가겠다. 문제풀이 딱 이문제를 보고 생각한게, 단어를 이루는 문자가 5개니깐 5중반복문이나, 완전탐색(DFS,BFS)으로 전부 탐색하면 되는거 아닌가? 모든 경우를 도는 횟수는 계산해보면 연산을 각 단어만다 최대 3905번을 탐색한다. {UUUUU=3905} 하지만 ,매번 들어오는 단어마다 최대 3905번 반복하는건 너무 비효율적이지 않나? 그래서 규칙을 곰곰히 생각해봤다. 먼저 3번째 예시인 "I" 의 위치값을 보자, 1563이다. 그렇다면, "I" 이전에 지나온 낱말수는 1562개란뜻이다. 지나온 낱말수는 총 2개 즉, 맨 앞자리의 문자가 바..