문제 이해
1은 오른쪽, 2는 위쪽, 3은 왼쪽, 4는 아래쪽으로 한 칸씩 이동하는 것을 의미한다.
1,2,3,4를 활용해서 우리는 어떤 도형을 그릴 수 있다.
이 때 처음 Input으로 내가 그릴 도형 그리는 방법(모양수열)이 숫자 리스트로 주어질 것이다.
이후 몇 개의 모양수열이 나올 것인데, 내가 그릴 도형과 "똑같은" 도형을 그리는 모양 수열의 개수와, 해당 모양 수열을 출력하는 것이 문제이다.
(똑같다 : 회전된 것이나 뒤집어진 도형은 똑같은 다각형이 아님)
문제 풀이
이전에 풀었던 시계수의 확장된 버전이다.
어느 점에서 시작했든 결국 활용하는 모양 수열의 형태가 "완전히 같아야지만" 똑같은 도형을 그리게 되는 것이다.
예를 들어보자.
1 2 3 4로 도형을 그렸다고 가정하자.
이 방법과 동일하게 그리려면 2 3 4 1, 3 4 1 2, 4 1 2 3의 모양 수열이 존재한다.
즉, 시계수와 동일하게 생각하면 1이라는 방향으로 시작하지 않고 2라는 방향으로 시작했다 하더라도, 그 이후의 3 4 1이라는 순서는 "완전히 같아야 한다"
따라서 시계수에서 활용한 로직을 활용하여, 원래 주어진 수열을 활용해 만들 수 있는 모든 숫자를 리스트에 저장하고, 해당 리스트에 일치하는 수열이 존재하면 Count를 1 증가시키면 될 것이다.
라고 생각하면 틀릴 것이다.
방향성은 물론 중요하다. 하지만, 완전히 반대 방향으로 이동하더라도 결론적으로는 똑같은 모형을 만들게 될 것이다.
위 예시에서는 볼 수 없지만, 문제 예시로 주어진 (2)과 (4)을 생각해보면 된다.
완전히 똑같은 모양을 가지지만, 처음 이동하는 방향성부터 완전히 반대 방향으로 이동한다.
즉, 처음 주어진 수열에 대해 "완전히 반대로 이동하여 만든 도형"의 모양수열도 만들어야 한다.
1 <-> 3, 2 <-> 4로 모두 값을 변화시켜 새로운 모양수열을 만들고, 이 수열과도 일치하는 값이 있는지 확인해야 진정한 답을 얻을 수있다.
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int size;
static String answer_str;
static String reverse_answer_str;
public static void main(String[] args) {
FastReader sc = new FastReader();
size = sc.nextInt();
StringBuilder answer = new StringBuilder();
StringBuilder reverse_answer = new StringBuilder();
String[][] ans = new String[size+1][2];
// ans[T][0] : 원래 주어진 모양 수열로 만들 수 있는 모든 경우의 수
// ans[T][1] : 원래 주어진 모양 수열과 완전히 반대 방향으로 이루어진
// 모양수열로 만들 수 있는 모든 경우의 수
for(int i =0;i<size;i++) {
int t = sc.nextInt();
int reverse_t = (t + 2)%4;
if(reverse_t==0) reverse_t = 4;
// 1<->3, 2<->4로 바꾸는 연산
// 단, (2+2)%4 = 0이므로 0인 Case는 따로 처리해줘야 한다.
answer.append(t);
reverse_answer.append(reverse_t);
}
answer_str = answer.toString();
reverse_answer_str = reverse_answer.reverse().toString();
ans[0][0] = answer_str;
ans[0][1] = reverse_answer_str;
for(int i =0;i<size;i++) {
/*
모양 수열과 완전 반대 방향의 모양 수열로 만들 수 있는
모든 경우의 수를 구하는 과정
.substring(i) : i ~ 문자열 끝까지의 부분 문자열
.substring(0,i) : 처음부터 (i-1) index까지의 문자열
즉, 왼쪽에 있는 부분 문자열을 잘라서 오른쪽에 붙이고,
이 때 자르는 기준 index를 0 ~ (size-1)까지로 지정하여 모든
경우의 수를 구하는 것이다.
*/
ans[i+1][0] = answer_str.substring(i) +answer_str.substring(0,i);
ans[i+1][1] = reverse_answer_str.substring(i)
+ reverse_answer_str.substring(0,i);
}
int T = sc.nextInt();
int casing = 0;
for(int i =0;i<T;i++) {
StringBuilder input = new StringBuilder();
for(int j = 0;j<size;j++) {
input.append(sc.nextInt()).append(" ");
}
String in = input.toString().replaceAll(" ", "");
for(int j=0;j<size+1;j++) {
if(ans[j][0].equals(in)) {
sb.append(input).append("\n");
casing++;
break;
}
if(ans[j][1].equals(in)) {
sb.append(input).append("\n");
casing++;
break;
}
}
}
System.out.println(casing);
System.out.println(sb.toString());
}
static class FastReader // 빠른 입력을 위한 클래스
}결과
- 두번째 줄 틀렸습니다 : startsWith과 endsWith을 활용해봤다. 그런데 이 경우 어디서 index를 잘라야 할지 애매해지는 Case가 생기고, 이런 경우 때문에 채점에서 틀린 Case가 나왔다.
