문제 설명
- 횟수가 주어진다.
- 문자열이 주어진다.
- 횟수만큼 문자열이 섞인다.
- 섞이는 규칙은 K번째 글자는 K+1번째 글자 사이로 이동한다.
문제 풀이
이번엔 그냥 구현하는 문제이다.
규칙을 우선 찾아보자.
섞는 규칙을 복원하는 규칙을 찾는 것이다.
짝수 길이의 문자열의 예시
우선 문제에서 순환 주기와 순환 문자열을 준다.
abcdef, afbecd, adfcbe, aedbfc, acefdb
순서로 순환한다.
그렇다면 1번 깜빡거린걸 찾을 때 afbecd가 다시 abcdef가 되게하는 규칙을 찾아보자.
우선 순환 문자열을 보면 맨 첫 문자를 변하지 않는 것을 볼 수 있다.
따라서 반복문에서 첫번째 문자열은 제외해도 된다.
이후 afbecd에서 f를 끝으로 이동시키자.
1번 인덱스를 5번 인덱스로 이동시킨것이다.
그러면 abecdf가 된다.
다음으로는 abecdf에서 e를 d와 f 사이로 이동시키자.
2번 인덱스를 4번 인덱스로 이동시킨 것이다.
그러면 abcdef가 된다.
다 된 것 같지만 아직 c를 옮기지 않았다.
abcdef를 c와 d 사이로 이동시키자.
3번 인덱스를 3번 인덱스로 이동시킨 것이다.
홀수 문자열의 예시
위 c를 옮기는 과정을 예시에 넣은 이유는 문자열의 길이가 홀수일 경우 때문이다.
abcdef가 아닌 abcdefg로 예시를 들어보자
abcdefg는 변환할 때 agbfced로 변환이 될 것이다.
이걸 다시 복원해보겠다.
이후 agbfced 에서 g를 끝으로 이동시키자.
1번 인덱스를 6번 인덱스로 이동시킨것이다.
그러면 abfcedg가 된다.
다음으로는 abfcedg에서 f를 d와 g 사이로 이동시키자.
2번 인덱스를 5번 인덱스로 이동시킨 것이다.
그러면 abcedfg가 된다.
그 다음으로는 abcedfg에서 e를 d와 f 사이로 이동시키자.
3번 인덱스를 4번 인덱스로 이동시킨 것이다.
그러면 abcdefg가 된다.
따라서 짝수와 홀수 문자열이 같이 작동하기 위해서는 짝수에서도 한 번 더 작동해야한다.
그리고 문자열 길이가 6인 경우 3번, 7인 경우도 3번 반복하였다.
따라서 반복은 문자열 길이 / 2를 한 값만큼 반복할 것이다.
필요 없는 반복 제거
문제에서는 시간을 1초로 설정해두고 섞는 횟수를 10억 번으로 설정하였다.
만약 브루트포스를 통해 모든 경우의 수를 확인한다면 시간초과가 무조건 날 것이다.
따라서 필요없는 반복을 제거해야한다.
극한의 예시로 문제의 입력 예시에는 다음 문자열이 있다.
1000
aaaaaa위와 같이 입력하게 된다면 같은 aaaaaa가 반복되는데 쓸데없이 1000번을 반복해야한다.
10억 번으로 설정해도 10억 번을 반복할 것이다.
따라서 문자열이 순환되는 부분을 확인해야한다.
문자열이 반복되는 것을 체크해서 순환되는 문자열을 전부 저장을 해볼까도 생각했지만 단순히 a~z와 1~0까지 이어진 문자열로 구성된다면 메모리를 많이 잡아먹을 것 같고 그렇게까진 필요 없다고 생각이 들었다.
따라서 문자열이 반복되는 주기를 찾는 방식으로 생각을 바꾸었다.
입력받은 문자열이 다시 나오게 된다면 한 번 반복할 때마다 +1 시켜주던 변수의 값을 가져와 카운트 + (섞는 횟수 % 카운트)로 계산하였다.
카운트를 더해주는 이유는 반복되는 섞는 횟수가 나머지로만 계산된다면 바로 반복문이 끝날 것이기 때문이다.
따라서 반복되는 주기 + 내가 찾는 문자열이 나올 앞으로 섞을 횟수로 계산한 것이다.
코드 풀이
using System;
using System.Collections.Generic;
using System.Linq;
namespace StudyCS
{
class Program
{
public static void Main(string[] args)
{
//글자가 섞임
//마지막 글자가 첫번째 글자와 두번째 글자 사이로 이동
//다시 말해 Length-1번 인덱스 값이 1번 인덱스로 이동
//뒤에서 두번째 글자가 두번째 글자와 세번째 글자 사이로 이동
//다시 말해 Length-2번 인덱스 값이 2번 인덱스로 이동
//식은 Length - K번째 글자는 K인덱스로 이동
//깜빡인 횟수
int X = int.Parse(Console.ReadLine());
//깜빡이고 난 후의 글자(입력 글자)
List<char> wordList = new List<char>();
//글자 계산용 리스트
List<char> tempList = new List<char>();
string word = Console.ReadLine();
//순환 주기 기록용
int count = 0;
for(int i = 0; i < word.Length; i++)
{
wordList.Add(word[i]);
}
tempList = wordList.ToList();
for(int i = 0; i < X; i++)
{
for(int j = 0; j < wordList.Count / 2; j++)
{
SwapCharacter(ref tempList, j + 1, tempList.Count - (j + 1));
}
string tempResult = string.Join("", tempList.ToArray());
count++;
if(tempResult == word)
{
X = count + (X % count);
}
}
string result = string.Join("", tempList.ToArray());
Console.WriteLine(result);
}
public static void SwapCharacter(ref List<char> inWordList, int fromIndex, int toIndex)
{
char temp = inWordList[fromIndex];
inWordList.RemoveAt(fromIndex);
inWordList.Insert(toIndex, temp);
return;
}
}
}위에서 설명한 내용을 코드로 풀었다. 위에서 전부 설명하였기 때문에 추가 설명은 필요 없을 것 같다.