16139번 인간-컴퓨터 상호 작용 , 10986번 나머지 합 , 11660번 구간 합 구하기 5
코딩테스트 : 16139번 인간-컴퓨터 상호 작용
| 1 초 (추가 시간 없음) | 256 MB | 29225 | 8164 | 6505 | 29.324% |
문제
승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.
'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'
승재를 도와 특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q번 할 것이다.
입력
첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 q가 주어지며, 문제의 수는 1≤q≤200,000을 만족한다. 세 번째 줄부터 (q+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 αi와 0≤li≤ri<|S|를 만족하는 정수 li,ri가 공백으로 구분되어 주어진다.
출력
각 질문마다 줄을 구분해 순서대로 답변한다. i번째 줄에 S의 li번째 문자부터 ri번째 문자 사이에 αi가 나타나는 횟수를 출력한다.
서브태스크 1 (50점)
문자열의 길이는 2,000자 이하, 질문의 수는 2,000개 이하이다.
서브태스크 2 (50점)
추가 제한 조건이 없다.
using System.Text;
public class BackJoon
{
public static void Main()
{
string input = Console.ReadLine();
string abc = "abcdefghijklmnopqrstuvwxyz";
char[] ABC = abc.ToCharArray();
Dictionary<char, int[]> alphabetArrays = new Dictionary<char, int[]>();
for (int i = 0; i < ABC.Length; i++)
{
alphabetArrays.Add(ABC[i], new int[input.Length]); // 딕셔너리에 추가
}
for (int i = 0; i < input.Length; i++)
{
char currentChar = input[i];
// 현재 문자의 개수 증가
if (i > 0)
{
foreach (char c in abc)
{
alphabetArrays[c][i] = alphabetArrays[c][i - 1];
}
}
alphabetArrays[currentChar][i]++;
}
int n = Int32.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
{
string[] inputs = Console.ReadLine().Split(' ');
char temp = inputs[0][0];
int startIndex = int.Parse(inputs[1].ToString());
int endIndex = int.Parse(inputs[2].ToString());
sb.AppendLine(( startIndex == 0 ? alphabetArrays[temp][endIndex] : alphabetArrays[temp][endIndex]-alphabetArrays[temp][startIndex-1]).ToString());
}
Console.WriteLine(sb.ToString());
}
}
코딩테스트 : 10986번 나머지 합
문제
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
특정 수로 나눴을 때 , 나누어 지는 것을 한 블럭으로 생각하고 그 블럭의 수를 알면 구간의 개수를 알 수 있을 것 같았다.
흠.. .그런데 지금 내가 구현한 방식은 순차적으로 가면서 더해지는것이기 때문에 순서가 얽히거나, 중복된 계산은 하지 못한다. 처음부터 다시 해 봐야한다.
using System.Text;
public class BackJoon
{
public static void Main()
{
// 아이디어 : 전부 다 나누고 나머지로 해보자.
int[] NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int N = NM[0];
int M = NM[1];
// 각각의 칸은 이제 나머지만 남음.
for (int i = 0; i < numbers.Length; i++)
{
numbers[i] = (numbers[i] % M);
}
// 나머지가 0이 되는 블럭끼리 묶음
int zeroCount = 0;
int count = 0;
int temp = 0;
for (int i = 0; i < numbers.Length; i++)
{
if (numbers[i] == 0)
{
zeroCount++;
}
else
{
temp += numbers[i];
if (temp % M == 0)
{
temp = 0;
}
}
}
int answer = 0;
for (int i = count; i >= 0; i--)
{
answer += i;
}
Console.WriteLine(answer + zeroCount);
}
}
using System.Text;
public class BackJoon
{
public static void Main()
{
// 아이디어 : 전부 다 나누고 나머지로 해보자.
long[] NM = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
long[] numbers = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
long N = NM[0];
long M = NM[1];
long[] remainderCount = new long[M];
long answer = 0;
long prevSum = 0;
for (long i = 0; i < N; i++)
{
prevSum += numbers[i];
long remainder = prevSum % M;
if (remainder == 0) answer++;
//와 ㅏ.... 그 전까지의 remainderCount[remainder] 즉, 그 전까지의 누적합이 같은 곳부터 지금까지는 무조건 더해지면
// m으로 나눴을 때 0이 나온다.
answer += remainderCount[remainder];
remainderCount[remainder]++;
}
Console.WriteLine(answer);
}
}
와... 이건 진짜 생각 못했다.. 한참걸렸네...
같은 나머지를 갖고 있는 ( 그 전까지 배열에서 ) count를 더해주면 된다.
왜 ? 같은 나머지를 갖고 있는 그 인덱스 ( 정확히 알 필요는 없다 횟수만 알면 된다 ) 부터 현재 인덱스까지 더하게 된다면
무조건 m으로 나눴을 때 나머지가 0이 나오게 된다.
코딩테스트 : 11660번 구간 합 구하기 5
문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
| 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 5 |
| 3 | 4 | 5 | 6 |
| 4 | 5 | 6 | 7 |
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
using System.Text;
public class BackJoon
{
public static void Main()
{
int[] NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int N = NM[0];
int M = NM[1];
int[,] matrix = new int[N, N];
for (int i = 0; i < N; i++)
{
int[] row = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int j = 0; j < N; j++)
{
matrix[i, j] = row[j];
}
}
int[,] sum = new int[N+1, N+1];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
sum[i, j] = matrix[i-1, j-1] + sum[i - 1, j] + sum[i, j - 1] - sum[i - 1, j - 1];
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++)
{
int[] row = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int x1 = row[0];
int x2 = row[2];
int y1 = row[1];
int y2 = row[3];
int answer = sum[x2, y2] - sum[x1 - 1, y2] - sum[x2, y1 - 1] + sum[x1-1, y1-1];
sb.AppendLine(answer.ToString());
}
Console.WriteLine(sb.ToString());
}
}
연습장으로 두 장을 써서 그림그려가면서 부분합을 구했다.
확실히 2차원이 되니까 어지럽다. 다만, 이차원 정도는 할 줄 알아야 한다.