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

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 문제분석 문제가 길어서 링크로 대체합니다. 배열의 길이가 같은 enroll 과 referral이 주어집니다. 이 enroll은 판매자를 나타내고, referral은 판매자와의 상속관계를 나타냅니다. 배열의 길이가같은 seller와 amount가 주어집니다. seller는 수익을 낸 판매자를 나타내고, amount는 판매자의 칫솔갯수를 나타냅니다. 목표:모든..

https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 문제분석 문제가 길어서 링크로 대체하겠습니다. 문제설명은 가로,세로 길이가 주어진 2차원배열이 주어집니다. 2차원배열은 1부터 가로X세로까지 +1씩 채워져있습니다. 이 2차원배열을 쿼리[x1,y1,x2,y2] 에 따라 회전시키고, 회전이 종료하고 움직인 숫자들중 가장 낮은숫자를 answer 배열에 추가합니다. 모든 쿼리를 순회했다면, answe..

Heap의 원리를 응용한 PriorityQueue에 대해 알아봅시다. PriorityQueue에서 Queue를 보고 "그 FIFO(First In First Out)의 큐랑 비슷한건가?" 라고 생각하시기 쉬운데 아닙니다. PQ 는 우선순위를 먼저 결정하고 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다. 말로만 설명하니 무슨소리인가 싶으니 그림을 가져오겠습니다. 예시로, PQ로 된, [2,3,5,7,9,10] 이 있다고 가정하고 생성하겠습니다. 보..

문제분석 목표: 모든 음식을 스코빌 지수 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차반복은, 단..