문제 -
칸토어 먼지는 다음 방법으로 만들어지는 평면 프랙탈입니다.
초기 형태에서 프랙탈은 검은 정사각형입니다.
반복마다 정사각형은 3x3으로 분할됩니다.
이 때 중앙의 가로 선과 세로 선은 흰색으로 칠합니다.
String[] pattern이 주어집니다.
이 배열은 흑백의 정사각형으로 구성된 직사각형을 표현합니다 ('X'가 흑색, '.'가 백색으로 표현됩니다)
반복 횟수 TIME의 칸토어 먼지에서의 패턴 발생 횟수를 리턴하세요.
//////////
예시
pattern = {"X...X"}
time = 2
return = 4
예시 설명
time이 2일 때, 칸토어 먼지 생김새
X . X . . . X . X
. . . . . . . . .
X . X . . . X . X
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
X . X . . . X . X
. . . . . . . . .
X . X . . . X . X
X...X 모양이 가운데 부분에 2열 부터 6열까지 일치하고 그게 0, 3, 5, 7 행에 존재하니까
1 X 4 해서 답은 4
/////////////////
풀이 과정
2차원 배열의 칸토어 먼지를 생성하기엔 메모리 부담이 크다.
대칭성을 이용해 1차원 배열을 통해 문제를 풀어보자
매개변수 t에 따라서
t == 0, return x
t == 1, return x x
t == 2, return x x x x
t == 3, return x x x x x x x x
이런 식으로 칸토어 먼지의 첫 행을 가져올 수 있다. (1차원 배열이라 가정하겠음)
그리고 칸토어 먼지는 가로 세로 대칭성이 있다!
따라서 가로축과 세로축으로 사용해서 2차원 배열 칸토어 먼지의 정보를 얻을 수 있다.
ex) time = 2의 칸토어 먼지와 가로축 세로축을 적용한 모습
파랑 - 가로축
노랑 - 세로축
빨강 - 칸토어 먼지
X . X . . . X . X
X X . X . . . X . X
. . . . . . . . . .
X X . X . . . X . X
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
X X . X . . . X . X
. . . . . . . . . .
X X . X . . . X . X
칸토어 먼지의 좌표 (X,Y)가 칠해져 있는지 판별하는 방법은,
1차원 배열의 X 번째 원소와 Y번째 원소가 'X'이면 칠해져 있으면 칠해져있는 거고,
둘 중 하나라도 '.'이면 안 칠해진 거임! 직접 그려서 규칙을 찾아보면 더 이해가 잘됨.
// 병신 패턴이 매개변수로 들어올 경우
EX)
X . X . X
. . . . .
X . . . X
. . . . .
X . X . X
이런 패턴이 들어온다 가정.
프렉탈 패턴은 가로축 세로축이 대칭이라서 아무리 TIME 수를 늘려도 저런 병신 패턴은 안나옴.
저런 패턴은 일찍이 걸러주자!
///////
전체 코드를 보면서 마지막 리뷰
탐색하는 로직과 'x' 를 포함할 때 p*q를 return 하는 건 별로 어렵지 않음.
근데 'x'를 포함하지 않을 때 return하는 저 식은 처음볼 때 '오잉?' 이런 반응이 나올 거임.
하지만 예시를 들어서 좀만 생각해보면 간단한 식이다.
ex)
time이 2일 때, 칸토어 먼지 생김새
X . X . . . X . X
. . . . . . . . .
X . X . . . X . X
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
X . X . . . X . X
. . . . . . . . .
X . X . . . X . X
찾고자 하는 pattern = ". ."
먼저 앞의 식 p*(l-n+1) 의 의미는
가로 패턴 일치수 x (가로축의 길이 - 패턴의 가로길이 + 1) 이다.
위 예시의 1행을 가져와 보면 (0행부터 시작)
. . . . . . . . .
이렇게 돼있고, ". ." 는 총 8개(9-2+1)임.
1행 모양의 패턴이 3,4,5,7 행에도 있다.
그 정보가 p에 담겨져 있음. (위 예에선 p는 5 (1, 3, 4, 5, 7 행 때 ++됨) )
고로 8개가 p(5)개 있으므로 8 x 5 = 40
중간의 식 (l-m+1) *q 의 의미는
X . X . . . X . X
위에 패턴을 세로축이라 생각해주삼.
". ." 은 2번 생김. (3,4)행 (4,5)행
그게 q에 담겨 있다. q = 2
그리고 그게 총 8행만큼 있음 (0~8행)
(l-m+1) -> (9-1+1) = 9
고로 9 x 2 = 18
뒤의 식 (- p*q)의 의미는 앞, 중간의 식에서 겹친 패턴을 빼주잔 얘기임.
가로축의 패턴 일치수가 q 이고 그게 p만큼 겹친다는 뜻.
그림 그려보면 쉽게 이해간다.
고로 (p*(l-n+1) + (l-m+1) *q-p*q) -> 40 + 18 - 10 = 48
댓글 0