오늘 풀어볼 문제는 ⭐XYZ 문자열(1663) 이라는 문제이다.
1. 문제요약
- 1단계 "XYZ 문자열"은 X로 시작한다.
- 다음 단계의 "XYZ 문자열"은 바로 이전 단계의 "XYZ 문자열"에서 아래와 같은 규칙에 따라 변형되어 만들어진다.
- X는 YZ로 변형된다.
- Y는 Z로 변형된다.
- Z는 X로 변형된다.
[문제 유형]
1 -> N단계의 XYZ 문자열 길이
2 -> N단계의 XYZ에서 K번째 문자
3 -> N단계의 XYZ에서 특정 문자가 몇 번 나타나는가?
2. 입출력
[입력]
- 문제 번호(1,2,3)
- 자연수 N (1<=N<=100)
- 자연수 k(문제 2, k<=N) or x,y,z 셋 중 하나(문제 3)
[출력]
1 -> N단계의 XYZ 문자열 길이
2 -> N단계의 XYZ에서 K번째 문자
3 -> N단계의 XYZ에서 특정 문자가 몇 번 나타나는가?
3. 문제 접근
이렇게 규칙이 딱 정해져있다면, 필시 예시케이스에 규칙이 숨겨져 있단 의미이다.
그래서 무작정 XYZ 문자열을 1단계부터 나열해보았다.
[테스트케이스]
X : 1
YZ (X->YZ) : 2
ZX (Y->Z, Z->X) : 3
⭐여기서부터 주목!⭐
XYZ (Z->X, X->YZ) : 1+2 => 4
YZZX (X->YZ, Y->Z, Z->X) 2+3 => 5
ZXXYZ (Z->X, X->YZ, X->YZ, Y->Z, Z->X) 3+4 => 6
XYZYZZX (X->YZ, Y->Z, Z->X, Y->Z, Z->X, Z->X, X->YZ) 4+5 => 7
....
이렇게 알 수 있듯이, 현재 본인인덱스-3번째 문자열 + 본인인덱스-2번째 문자열이 합쳐지는 규칙을 알 수 있다.
이 문제에서 주의할 점은 2가지가 있다.
⚠️주의점1 : StringBuilder 또는 String 문자열 사용 금지
메모리가 터진다. 위 규칙만 알고 있다면, 문자열을 직접 만들어줄 필요가 전혀 없다.
⚠️ 3.2 int가 아닌 long 자료형 사용
만약 N이 100인 XYZ 문자열의 길이와 각 x,y,z의 카운트는 int형의 범위를 벗어난다.
그렇기 때문에 x,y,z의 카운팅 자료형, 전체 문자열의 자료형은 long을 사용해줘야 한다.
1번 유형 풀이법
1번 유형
1번 유형은 각 단계의 문자열 길이를 출력하는 것이다.
이를 위해서는 현재 단계에서 x,y,z의 카운트 정보를 저장하는 class만 있으면 된다.
class Info {
long X, Y, Z;
public Info(long X, long Y, long Z)
{
this.X=X;
this.Y=Y;
this.Z=Z;
}
}우리는 이미 XYZ의 규칙을 알기 때문에, 초반에 규칙없이 주어지는 기본 문자열
"X", "YZ", "ZX"
의 각 x,y,z 수를 더해주면서, N만큼 반복문을 돌아주면 된다.
2번 유형 풀이법
2번 유형은 K번째 위치의 문자를 구하는 것이었다.
⭐⭐⭐ 가장 중요한 풀이법이다!!
이는 주의점에서도 말했듯, 규칙을 이용해 N에서부터 역산하면서 풀어야한다.
static String [] base = {"", "X", "YZ", "ZX"};
.....
static char findK (int nowIndex, long nowK) {
if(nowIndex<=3) return base[nowIndex].charAt((int) nowK-1);
long firstXYZLength = XYZ[nowIndex-3].X+XYZ[nowIndex-3].Y+XYZ[nowIndex-3].Z;
if(nowK <= firstXYZLength) return findK(nowIndex-3, nowK);
else return findK(nowIndex-2, nowK - firstXYZLength);
}XYZ 문자열 = 현재인덱스-3 XYZ (1) + 현재인덱스-2 XYZ (2)
라고 했었다.
현재 주어지는 K(위치)가, (1)의 XYZ의 길이보다 작거나 같다면?
-> 우리는 (2)를 볼 필요가 없다.
그러나 K(위치)가 (1)의 XYZ의 길이보다 크다면?
-> K 위치는 (2)에 속하는 것이니, K-(1)길이 로 새로운 K를 정의 후 (2)만 보면 된다.
3번 유형 풀이법
3번 유형은 현재 N단계에서 X, Y, Z가 몇 번 등장했는지 구하는 문제이다.
우리는 이미 해당 정보를 Info class에서 저장하고 있으니, 바로 반환만 해주면 끝난다.
4. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Info {
long X, Y, Z;
public Info(long X, long Y, long Z)
{
this.X=X;
this.Y=Y;
this.Z=Z;
}
public long findCnt(String target){
if ("X".equals(target)) return X;
return "Y".equals(target) ? Y : Z;
}
}
public class Main {
static int type;
static int N;
static long K = 0;
static String target="";
static Info [] XYZ;
static String [] base = {"", "X", "YZ", "ZX"};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
type = Integer.parseInt(br.readLine());
N = Integer.parseInt(br.readLine());
K = 0;
target="";
if (type == 2) {
K = Long.parseLong(br.readLine().trim());
} else if (type == 3) {
target = br.readLine().trim();
}
XYZ = new Info[N+1];
XYZ[1] = new Info(1,0,0); //X;
if(N>=2)XYZ[2] = new Info(0,1,1); //YZ;
if(N>=3)XYZ[3] = new Info(1,0,1); //XZ;
int firstCnt = 1;
int secondCnt = 2;
for(int i=4; i<=N; i++) {
Info first = XYZ[firstCnt++];
Info second = XYZ[secondCnt++];
XYZ[i] = new Info(first.X+second.X, first.Y+second.Y, first.Z+second.Z);
}
if(type==1) {
System.out.println(XYZ[N].X+XYZ[N].Y+XYZ[N].Z);
}else if(type==2) {
System.out.println(findK(N, K));
} else {
System.out.println(XYZ[N].findCnt(target));
}
}
//firstNum = 본인인덱스-3, secondNum = 본인인덱스-2
static char findK (int nowIndex, long nowK) {
if(nowIndex<=3) return base[nowIndex].charAt((int) nowK-1);
long firstXYZLength = XYZ[nowIndex-3].X+XYZ[nowIndex-3].Y+XYZ[nowIndex-3].Z;
if(nowK <= firstXYZLength) return findK(nowIndex-3, nowK);
else return findK(nowIndex-2, nowK - firstXYZLength);
}
}
