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 배열은 없어도 될 것 같다.

Image

다른 분의 멋진 코드

nupic7

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 님의 풀이는 정말 예술이다.. 추후 분석 해보자.

댓글남기기