코린이의 소소한 공부노트

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 한다. (1) 먼저 첫 글자를 읽는다. 이 글자를 x라고 하자. (2) 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 센다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리한다. (3) s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복한다. 남은 부분이 없다면 종료한다. (4) 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료한다. 1. Input, Output, Example - 문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 ..

수많은 마라톤 선수들이 마라톤에 참여하였다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다. 1. Input, Output, Example - 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 반환 2. Constraint 1) 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하 2) completion의 길이는 participant의 길이보다 1 작다. 3) 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있다. 4) 참가자 중에는 동명이인이 있을 수 있다. 3. Code 1) 첫 코드 import java.util.*; class Soluti..

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 한다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용한다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1이고, X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0이다. 1. Input, Output, Example - X, Y의 짝꿍을 문자열로 반환 2. Constraint 1) 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000 2) X, Y는 0으로 시작하지 않는다. 3. Code 1) 첫 코드 class Solution { public String solution(String X, String Y) { int[] x = new in..

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있다. 기사들은 무기점에서 무기를 구매하려고 한다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 한다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다. 무기를 만들 때 무기의 공격력 1당 1kg의 철이 필요하기 때문에 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 한다. 1. Input, Output, Example - 기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를..

다트 게임의 점수 계산 로직은 아래와 같다. (1) 다트 게임은 총 3번의 기회로 구성된다. (2) 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다. (3) 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수^1 , 점수^2 , 점수^3 )으로 계산된다. (4) 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다. (5) 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고) (6) 스타상(*)의 효과는 다른 스타상(*..

1. Input, Output, Example - 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 반환 - 실패율 계산: 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 2. Constraint 1) 스테이지의 개수 N은 1 이상 500 이하의 자연수 2) stages의 길이는 1 이상 200,000 이하 3) stages에는 1 이상 N + 1 이하의 자연수가 담겨있다. 4) 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다. 단, N + 1 은 마지막 스테이지(N 번째 스테이지)까지 클리어..

1. Input, Output, Example - 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환 - 소수는 약수의 개수가 2개인 자연수를 뜻한다. 2. Constraint 1) n은 2이상 1,000,000이하의 자연수 3. Code import java.util.*; class Solution { public int solution(int n) { boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true); for(int i=2 ; i

1. 개념 정리 1) 여러 개의 데이터가 연속적으로 존재할 때 특정 구간의 데이터의 합을 담은 이진 트리 2) 실제 구현은 트리가 아닌 배열로 하게 된다. - 배열은 인덱스가 있어 접근성이 좋기 때문이다. 3) 세그먼트 트리를 이용한 구간 합 처리의 시간 복잡도는 O(lgn)이다. 2. 예시 1) 구간 합의 데이터가 될 배열을 준비한다. int[] arr = {1,2,3,4,5,6,7,8}; 2) 구간 합 트리가 될 배열도 준비한다. int[] tree = new int[32]; // arr.length * 4 // 데이터의 개수가 N개일 때 필요한 부분 합 트리의 공간은 // N 이상의 2의 거듭제곱수 중 가장 작은 것 * 2이다. // 여기서 N=8이므로 8 이상의 2의 거듭제곱수 중 가장 작은 것은..

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. (1) 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (2) (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 1. 입력 - 첫째 줄에 N(1 ≤ N ≤ 3^7, N은 3^k 꼴)이 주어진다. - 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 2. 출력 - 첫째 줄에 -1로만 채워진 종..

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다. 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드..