돌고 돌아 기본

프로그래머스 12938번 - 최고의 집합 요구사항 1. 자연수 n 개로 이루어진 중복 집합 중 최고의 집합을 오름차순으로 정렬하여 반환하라. 2. 자연수 n 개로 이루어진 중복 집합은 다음과 같다. 각 원소의 합이 S를 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 중복 집합 중 최고의 집합이라고 한다. 요구사항 분석 및 풀이과정 1. 자연수 n이 s보다 클 경우, 자연수 n개로 이루어진 중복 집합의 합은 무조건 s를 넘기 때문에 최고의 집합이 존재하지 않는다. 2. 자연수 n개로 이루어진 중복 집합의 합이 s로 일정할 때, 중복 집합의 각 원소의 곱이 최대가 되기 위해서는 각 원소 간의 편차가 적어야 한다. 왜 그런지 궁금하다면 싶다면 산술-기하 평균 부등식을 알아보자. s가 n으로 나누어떨어지..

프로그래머스 17687번 - [3차]n진수 게임 요구사항 1. 숫자를 0부터 시작해서 차례대로 말하며, 10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 2. 난이도를 올려 숫자를 n진수로 변환하여 한 숫자씩 말할 때, 튜브가 p번째 순서에 말해야 하는 숫자 t개를 공백 없이 차례대로 나타낸 문자열을 반환하라. (단, 10~15는 각각 대문자 A~F로 출력하라.) 요구사항 분석 및 풀이과정 1. 튜브가 p번째 순서부터 말해야 하는 숫자 t개를 미리 구하기 위하여, 그냥 전원(m명)이 t개씩 말할 때의 수들을 미리 모두 구합니다. 2. 1번에서 구한 경우에서 p번째 수(인덱스로는 p-1)부터, 다음 턴(전원 m명이 모두 말한 후)에 말할 수를 순차적으로 문자열로 출력하여주면 됩니다. 정수를 n진법으로 표현..

프로그래머스 12981번 - 영어 끝말잇기 요구사항 1. 영어 끝말잇기에서 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 배열에 담아 반환하라. 2. 사람의 번호는 1번부터 시작합니다. 요구사항 분석 및 풀이과정 1. 정상적으로 끝말이 이어지는 지를 확인하기 위하여 이전 사람이 말한 영단어의 끝 문자를 기록합니다. 2-1. i번째 사람이 영단어를 말했을 경우 i-1번째 사람이 말한 영단어의 끝 문자와 내가 말한 영단어의 첫 문자가 같은지를 확인합니다. 2-2. 만약 다르다면 탈락이며, 가장 먼저 탈락하는 사람의 번호(i % n + 1), 자신의 몇 번째 차례(i / n + 1)를 배열에 담아 반환합니다. 2-3. 그렇지 않은 경우는 정상적인 끝말잇기이므로 다음 차례로 넘..

프로그래머스 62048번 - 멀쩡한 사각형 요구사항 1. 종이를 대각선 꼭짓점 2개를 잇는 방향으로 잘랐을 때 사용할 수 있는 정사각형의 개수를 반환하라. 2. 정사각형은 1cm x 1cm 크기입니다. 요구사항 분석 및 풀이과정 1. 위 예를 살펴보면 사용할 수 없는 영역인 흰 영역에 다음과 같이 일정한 패턴이 존재한다는 것을요. 그러면 이렇게 생긴 영역의 수는 몇 개인지 어떻게 알 수 있을까요? 간단합니다. 높이/너비의 비율을 보면 됩니다. 위 문제에서 높이는 12, 너비는 8 따라, 비율은 12/8 = (3*4) / (2*4)입니다. 너비와 높이가 2:3 비율로 가지는 사각형이 가로로 4개, 세로로 4개 총 16개가 존재한다는 사실을 알 수 있고, 우리가 필요한 대각선 영역에는 4개 존재한다는 사실을..

프로그래머스 77885번 - 2개 이하로 다른 비트 요구사항 1. 정수들이 담긴 배열 numbers의 양수 x에 대하여 f(x)의 값을 배열에 차례대로 담아 반환하라. f(x) = x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 요구사항 분석 및 풀이과정 1. 양수 x가 짝수인 경우 최하위 비트는 항상 0입니다. 그러므로 양수 x+1은 최하위 비트만 0에서 1로 바뀌게 됩니다. 따라 양수 x와 비트가 1개(최하위 비트)가 다르게 되고, f(x) = x + 1 이 성립합니다. 여기서 끝을 낼 수 있는 이유는, 양수 x+1은 x보다 큰 양수 중 제일 작은 수이기때문입니다. f(x) = x + 1 ( x가 짝수 ) 2. 양수 x가 홀수인 경우, 비트 1개 다르게 하는 직관적인 방법은 최하위 ..