Engineering Note

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12980 해설 점프 : K칸 앞으로 점프, K만큼 건전지 사용 순간 이동: (현재까지 온 거리)*2의 위치로 이동, 건전지 사용 안함 0의 위치에서 n으로 이동할 때, 점프 or 순간 이동을 사용하는데 건전지 사용량을 최소로 사용해야한다. 이때 최소 건전지 사용량을 return 해라. 건전지를 최소로 사용하기 위해서는 점프를 최소로하고 순간이동을 최대로 늘려야한다. 문제의 주어진 예시를 통해 살펴보자. 순간 이동을 최대로 하기 위해서는 마지막 n으로 오기 직전일때 2배를 했을 때 가장 이동 구간이 크기 때문에 마지막에는 최대한 순간이동을 사용하는 것이 좋다. 그러나 점프는 앞으로만 이동이 가능하므로..

문제 : https://programmers.co.kr/learn/courses/30/lessons/17682 해설 다트게임 -> 다트판에 다트를 세 차례 던져 그 점수 합계로 실력을 겨루는 게임 다트 게임 점수 계산 로직 1. 총 세번의 라운드로 진행된다. 2. 점수는 0~10점 중 하나다. 3. 보너스: 점수마다 하나씩 존재하는 보너스 계산이 있다. S: 점수의 1제곱 D: 점수의 2제곱 T: 점수의 3제곱 4. 옵션: 점수마다 존재하지 않거나 존재한다면 하나씩만 존재하는 옵션 스타상(*): 해당 점수, 바로 직전 점수 각 2배 : 해당 라운드가 1라운드일 경우 직전라운드가 없으므로 해당 라운드 즉, 1라운드만 점수 2배 : 스타상은 중첩될 수 있다. ex) 1S*2D*3T 로 점수 배점이 매겨졌을 ..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/68935 해설 1. 입력값으로 주어진 수를 3진법으로 바꾼다. 2. 1에서 구한 3진법을 표기된 수를 뒤집는다. 3. 2에서 구한 수를 10진법으로 바꾼다. n진법의 수를 구할때 주어진 수를 n으로 계속 나누면서 나머지를 차례 차례 n의 i승 자리에 적어주면 된다. i는 0부터 시작하여 나눌때마다 1씩 증가한다. 하지만 지금 구해진 각각의 나머지는 한자리 숫자를 의미한다. 뒤집기 위하여 이 수를 리스트에 저장해둘수도 있다. 예를 들면 45를 n진법으로 구하는 과정에서 구해지는 나머지 수는 0,0,2,1 이고 3진법으로 적으면 1200(3)이다. 그렇다면 이 수를 거꾸로 구한 수를 [0,0,2,1]라..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64061 해설 문제의 상황을 요약하면 이렇다. 게임화면은 좌측에 "1 x 1"크기의 칸들로 이루어진 "N x N"크기의 정사각 격자의 인형뽑기함이 있고, 우측에는 바구니가 있다. 인형은 "1 x 1"크기의 칸을 차지하며 아래부터 차곡 차곡 쌓여 있고, 게임사용자가 크레인을 좌우로 이동하여 멈춘 열의 위치에서 가장 위에 있는 인형을 집어올린다. 그리고 집어올린 인형은 바구니의 아래칸부터 순서대로 쌓이게 된다. 이때 같은 모양의 인형 두개가 연속으로 바구니에 쌓이게 되면 인형은 터뜨려지면서 사라진다. 입력값으로는 인형뽑기함의 격자상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 ..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12985 해설 N명이 게임에 참가하고 12, 34, 56, ... N-1N 규칙으로 대결을 한다. 그리고 이긴 승자는 다음라운드에 진출하고 다시 번호를 부여 받는다. 이 규칙을 표현하면 다음과 같다. ''' 1 2 3 4 5 6 7 8 1 2 3 4 1 2 ''' 여기서 다음 라운드 숫자의 번호를 구하는 규칙은 현재 번호에서 2로 나눈 나머지와 몫을 더하면 다음 라운드의 번호가 된다. 그리고 다음 라운드의 예상 번호가 같다는 것은 현재 라운드에서 대결을 했다는 것이다. 예를 들면 3번과 4번 중에 3번이 이겼다면 다음라운드에 2번이 되고 4번이 이겼어도 2..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42579 해설 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 만드는 프로그램을 완성하는 것이다. 입력 값으로 노래의 장르를 나타내는 문자열 배열 genres, 노래별 재생횟수를 나타내는 정수 배열 plays가 주어진다. 이때 노래마다 고유번호가 존재하고 그 고유 번호를 i 라고 했을 때, genres[i]는 i 노래의 장르를 나타내고 plays[i]는 i 노래의 재생횟수를 나타낸다. 문제의 노래 수록 기준은 다음과 간다. 1. 속한 노래가 많이 재생된 장르를 먼저 수록한다. -> 이 기준에 따라서 장르별 총 재생횟수를 구하고 정렬해야 함을 알 수 있다. 2. 장르 내에서 많이 재생..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42577 해설 한 번호가 다른 번호의 접두어인 경우를 찾는 것이다. 그런데 구하는 방법이 한 번호가 다시 다른 번호의 접두어인지 확인하는 방법을 역으로 구한다. 역으로라는 의미는 접두어를 구하고 이 구한 접두어가 phone_book에 존재하는 지를 확인하는 것이다. 이때 한 번호의 접두어는 어려가지 경우가 있다. 한 번호의 접두어를 하나씩 구하고, 이렇게 구한 접두어가 기존 번호 리스트에 있는지 확인하면 된다. 이때 확인하는 방법을 구한 접두어 번호마다 다시 phone_book list에서 확인하면 O(n)의 시간복잡도를 갖고 n이 최대 1,000,000이므로 효율성이 좋지 않다. 예를 들면 "11..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/87946 해설 유저가 던전을 탐험한다. 각 유저는 "현재 피로도"를 갖고 있고, 던전에는 탐험을 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다. 유저가 던전을 탐험 하기 위해서는 "현재 피로도"는 던전의 "최소 필요 피로도"보다 커야 한다. 그리고 던전 탐험 후 "현재 피로도"는 탐험 전 "현재 피로도"에서 "소모 피로도"만큼 감소한다. 입력값은 현재피로도 k, 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 주어진다. 예를 들어 k=80, dungeons = [[80,20],[50,40],[30,10]]가 주어 질..