Algorithm
Solved - Silver 1
[Swift] 2447 별 찍기 - 10
[Swift] 2447 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
***
* *
***
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다
Example
입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
출력
첫째 줄부터 N번째 줄까지 별을 출력한다.
예제 입력 1
27
예제 출력 1
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
문제 이해
코드
func blank(i: Int,
j: Int,
num: Int,
input: Int,
array: inout [[Character]],
dp: inout [[Bool]]) {
if dp[i][j] {
return
}
dp[i][j] = true
for k in i ..< i + num {
for o in j ..< j + num {
array[k][o] = Character(" ")
}
}
if i + num * 3 < input {
blank(i: i + num * 3,
j: j, num: num,
input: input,
array: &array,
dp: &dp)
}
if j + num * 3 < input {
blank(i: i,
j: j + num * 3,
num: num,
input: input,
array: &array,
dp: &dp)
}
}
let input = Int(readLine()!)!
var array = [[Character]](repeating: [Character](repeating: Character("*"), count: input), count: input)
var dp = [[Bool]](repeating: [Bool](repeating: false, count: input), count: input)
var power = 3
while power < input {
blank(i: power,
j: power,
num: power,
input: input,
array: &array,
dp: &dp)
power = power * 3
}
for i in stride(from: 0, to: input, by: 3) {
for j in stride(from: 0, to: input, by: 3) where dp[i][j] == false {
array[i + 1][j + 1] = Character(" ")
}
print(String(array[i]))
print(String(array[i+1]))
print(String(array[i+2]))
}
풀이
별을 찍는 것이 아닌 배열을 별로 초기화 하고 공백을 찍는 형태로 접근했다. 계속 시도하다 보니 패턴이 보였고, 큰 네모부터 없애면서 작은 공백을 찍도록 했다. 시간 초과가 발생해 dp 배열을 이용해 체크하는 형태로 접근했다.
dp 배열은 없어도 될 것 같다.
다른 분의 멋진 코드
func getPatter (_ n: UInt16) -> [String] {
var returnStr = [String].init(repeating: "", count: Int(n))
if (n / 3) > 1 {
let beforeStr = getPatter(n / 3)
for i in 0..<n {
switch (i + 1) {
case (n / 3 + 1)...(2 * (n / 3)):
returnStr[Int(i)].append(beforeStr[Int(i % (n / 3))])
returnStr[Int(i)].append(String.init(repeating: " ", count: Int(n) / 3))
returnStr[Int(i)].append(beforeStr[Int(i % (n / 3))])
default:
returnStr[Int(i)].append(beforeStr[Int(i % (n / 3))])
returnStr[Int(i)].append(beforeStr[Int(i % (n / 3))])
returnStr[Int(i)].append(beforeStr[Int(i % (n / 3))])
}
}
return returnStr
} else if (n / 3) == 1 {
return ["***", "* *", "***"]
}
return []
}
let n = UInt16(readLine() ?? "") ?? 0
print(getPatter(n).joined(separator: "\n"))
잘 배웠습니다.
- nupic7 님의 풀이는 정말 예술이다.. 추후 분석 해보자.
댓글남기기