24060번 알고리즘 수업 병합 정렬 -1 , 4779번 칸토어 집합
코딩테스트 : 24060번 알고리즘 수업 병합 정렬 -1
문제
오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.
크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.
merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
if (p < r) then {
q <- ⌊(p + r) / 2⌋; # q는 p, r의 중간 지점
merge_sort(A, p, q); # 전반부 정렬
merge_sort(A, q + 1, r); # 후반부 정렬
merge(A, p, q, r); # 병합
}
}
# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
i <- p; j <- q + 1; t <- 1;
while (i ≤ q and j ≤ r) {
if (A[i] ≤ A[j])
then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
}
while (i ≤ q) # 왼쪽 배열 부분이 남은 경우
tmp[t++] <- A[i++];
while (j ≤ r) # 오른쪽 배열 부분이 남은 경우
tmp[t++] <- A[j++];
i <- p; t <- 1;
while (i ≤ r) # 결과를 A[p..r]에 저장
A[i++] <- tmp[t++];
}입력
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.
다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
출력
배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.
using System.Text;
public class Solution
{
private static int saveIndex = 0;
public static void Main()
{
int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int targetIndex = input[1];
int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int answer = MergeSort(arr, 0, arr.Length - 1, targetIndex);
Console.WriteLine(answer);
}
public static int MergeSort(int[] arr, int left, int right, int targetIndex)
{
if (left < right)
{
int middle = (left + right) / 2;
MergeSort(arr, left, middle, targetIndex);
MergeSort(arr, middle + 1, right, targetIndex);
var answer = Merge(arr, left, middle, right, targetIndex);
if (answer != -1) return answer;
}
return -1;
}
public static int Merge(int[] arr, int left, int middle, int right, int targetIndex)
{
int[] temp = new int[right - left + 1];
// 복사해서 새로운 배열을 만든다.
int s = left;
int m = middle + 1;
int index = 0;
while (s <= middle && m <= right)
{
if (arr[s] < arr[m])
{
temp[index] = arr[s];
s++;
}
else
{
temp[index] = arr[m];
m++;
}
saveIndex++;
if (saveIndex == targetIndex) return temp[index];
index++;
}
for (int i = s; i <= middle; i++)
{
temp[index] = arr[i];
saveIndex++;
if (saveIndex == targetIndex) return temp[index];
index++;
}
for (int i = m; i <= right; i++)
{
temp[index] = arr[i];
saveIndex++;
if (saveIndex == targetIndex) return temp[index];
index++;
}
for (int i = left; i <= right; i++)
{
arr[i] = temp[i - left]; // 원래 배열에 다시 복사해야 함
}
return -1;
}
}
왜 안되는지 한참 고민했다.
내가 생각했던건 결국 '저장'은 병합 과정에서만 하니까 병합 과정에서만 값을 저장하고, 그 값을 비교하고 리턴하면 되지 않을까 ? 라고 생각했다.
그런데, 병합 과정에서 올바른 값을 찾아서 리턴해도, 그 리턴값이 상위 호출로 이어지지 않았다.
그래서 진짜 삼십분 고민하다가 새로운 답으로 찾았다.
using System.Text;
public class Solution
{
private static int saveIndex = 0;
public static void Main()
{
int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int targetIndex = input[1];
int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int answer = MergeSort(arr, 0, arr.Length - 1, targetIndex);
Console.WriteLine(answer);
}
public static int MergeSort(int[] arr, int left, int right, int targetIndex)
{
if (left < right)
{
int middle = (left + right) / 2;
var answer1 = MergeSort(arr, left, middle, targetIndex);
if (answer1 != -1) return answer1;
var answer2= MergeSort(arr, middle + 1, right, targetIndex);
if (answer2 != -1) return answer2;
var answer = Merge(arr, left, middle, right, targetIndex);
if (answer != -1) return answer;
}
return -1;
}
public static int Merge(int[] arr, int left, int middle, int right, int targetIndex)
{
int[] temp = new int[right - left + 1];
// 복사해서 새로운 배열을 만든다.
int s = left;
int m = middle + 1;
int index = 0;
while (s <= middle && m <= right)
{
if (arr[s] < arr[m])
{
temp[index] = arr[s];
s++;
}
else
{
temp[index] = arr[m];
m++;
}
saveIndex++;
if (saveIndex == targetIndex) return temp[index];
index++;
}
for (int i = s; i <= middle; i++)
{
temp[index] = arr[i];
saveIndex++;
if (saveIndex == targetIndex) return temp[index];
index++;
}
for (int i = m; i <= right; i++)
{
temp[index] = arr[i];
saveIndex++;
if (saveIndex == targetIndex) return temp[index];
index++;
}
for (int i = left; i <= right; i++)
{
arr[i] = temp[i - left]; // 원래 배열에 다시 복사해야 함
}
return -1;
}
}
이 문제는 예전에 봤던 병합 정렬을 다시 공부하게 해 준 고마운 문제다.
곧 새롭게 포스팅해서 올릴지도.. . . ?
더해서, 재귀에 속성에 대해 다시 한 버 생각해보게 되었다. 하위 호출에서 상위 호출로 값을 전달할 때 어떻게 해야 하는지..
코딩테스트 : 4779번 칸토어 집합
문제
칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.
전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.
1. -가 3N개 있는 문자열에서 시작한다.
2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.
3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.
예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.
---------------------------여기서 가운데 문자열을 공백으로 바꾼다.
--------- ---------남은 두 선의 가운데 문자열을 공백으로 바꾼다.
--- --- --- ---한번 더
- - - - - - - -모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.
입력
입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.
출력
입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.
using System.Data;
using System.Text;
public class BaekJoon
{
public void Main()
{
int n = int.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
{
int s = int.Parse(Console.ReadLine());
int z = 1;
for (int j = 0; j < s; j++)
{
z *= 3;
}
List<int> numbers = new List<int>();
Cantor(0,z);
void Cantor(int start, int end)
{
if (start == end) numbers.Add(start);
else
{
Cantor(start, end / 3);
Cantor((end * 2) / 3, end);
}
}
}
}
}
이런 식으로 리스트에 담아서 해 보려 했지만, 사실은 더더욱 효율적인 코드가 있었다.
using System.Data;
using System.Text;
public class BaekJoon
{
public static void Main()
{
StringBuilder sb = new StringBuilder();
string input;
while ((input = Console.ReadLine()) != null)
{
if (string.IsNullOrEmpty(input)) // 빈 줄 또는 null 입력시 종료
{
break;
}
int s = int.Parse(input);
int N = (int)Math.Pow(3, s);
char[] chars = new char[N];
for (int j = 0; j < N; j++)
{
chars[j] = '-';
}
Cantor(chars, 0, N);
sb.AppendLine(new string(chars));
}
Console.Write(sb);
}
public static void Cantor(char[] chars, int start, int end)
{
if (end - start < 2) return;
int gap = end - start;
int count = gap / 3;
for (int i = start + count; i < end - count; i++)
{
chars[i] = ' ';
}
Cantor(chars, start, start + count );
Cantor(chars, start + 2 * count , end);
}
}저기서 input = Console.ReadLin() ! = null 이 조건을 처음 사용해 보는데 무한 루프를 돌아서
뭐가 문제인지 한참 찾았다. 백준이나 라이더 같은 IDE에서는 종료를 명시적으로 시켜줘야 한다는 것을 알게 되었다.