Spiral Array

문제는 다음과 같다:

6 6

  0   1   2   3   4   5
 19  20  21  22  23   6
 18  31  32  33  24   7
 17  30  35  34  25   8
 16  29  28  27  26   9
 15  14  13  12  11  10

위처럼 6 6이라는 입력을 주면 6 X 6 매트릭스에 나선형 회전을 한 값을 출력해야 한다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

3개의 풀이가 있습니다.

Scala로 풀었습니다. 생각보다 시간이 많이 걸렸네요.

def spiral(row: Int, column: Int): Array[Array[Int]] = {

    def fn(n: Int, m: Int, dir: Int, count: Int, result: Array[Array[Int]]): Array[Array[Int]] = {

        def next(n: Int, m: Int, dir: Int, count: Int, result: Array[Array[Int]]) = {
            if(dir % 4 == 0) {
                fn(n, m + 1, dir, count, result)
            } else if(dir % 4 == 1) {
                fn(n + 1, m, dir, count, result)
            } else if(dir % 4 == 2) {
                fn(n, m - 1, dir, count, result)
            } else {
                fn(n - 1, m, dir, count, result)
            }
        }

        val isFail: Boolean = {
            n < 0 || m < 0 || n >= row || m >= column || result(n)(m) != -1
        }

        if(count >= row * column) {
            result
        } else if (isFail) {
            if(dir % 4 == 0) {
                next(n, m - 1, dir + 1, count, result)
            } else if(dir % 4 == 1) {
                next(n - 1, m, dir + 1, count, result)
            } else if(dir % 4 == 2) {
                next(n, m + 1, dir + 1, count, result)
            } else {
                next(n + 1, m, dir + 1, count, result)
            } 
        } else {
            result(n)(m) = count
            next(n, m, dir, count + 1, result)
        }
    }

    fn(0, 0, 0, 0, Array.fill[Int](row, column)(-1))
}

println(
    spiral(6,6).map(_.mkString("\t")).mkString("\n")
)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Scala로 풀었습니다.

object Direction extends Enumeration {
  type Direction = Value
  val RIGHT, DOWN, LEFT, UP = Value
}

import Direction._

class SpiralArray(x: Int, y: Int) {
  val array = Array.fill[Int](x, y)(-1)  // 2차원 배열, 초기값은 -1
  var direction = RIGHT
  init()

  def init() = {
    val lastNumber = x * y - 1 // 배열에 넣을 마지막 숫자
    var pos = (0, 0) // 시작 위치
    for (num <- (0 to lastNumber)) {
      array(pos._1).update(pos._2, num)
      if (num != lastNumber) pos = nextPosition(pos._1, pos._2)
    }
  }

  /**
   * 현재 위치가 (i,j) 일때 다음 위치 알아내기
   */
  def nextPosition(i: Int, j: Int): (Int, Int) = {
    // 방향에 따라 다음 위치 선정
    val position = direction match {
      case RIGHT => (i, j + 1)
      case DOWN => (i + 1, j)
      case LEFT => (i, j - 1)
      case UP => (i - 1, j)
    }

    if (position._1 != -1 && position._1 != x && position._2 != -1 && position._2 != y
      && array(position._1)(position._2) == -1) {
      position // 다음 위치가 끝이 아니고 다음 위치의 숫자가 바뀌지 않은 경우 다음 위치 리턴
    }
    else {
      changeDirection() // 방향을 바꾸고, 다음 위치 다시 확인
      nextPosition(i, j)
    }
  }

  /**
   * right => down => left => up
   */
  def changeDirection() = {
    direction = direction match {
      case RIGHT => DOWN
      case DOWN => LEFT
      case LEFT => UP
      case UP => RIGHT
    }
  }
}

object Boot extends App {
  val sa = new SpiralArray(6, 6)
  for (row <- sa.array) println(row.mkString("\t"))
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
object Main extends App {

  object Direction extends Enumeration {
    type Direction = Value
    val UP, DOWN, RIGHT, LEFT= Value
  }

  import Direction._

  class SpiralArray(width: Int, height: Int) {
    val array = Array.fill[Int](width, height)(-1)
    var direction = Direction.RIGHT

    def process(): Array[Array[Int]] = {
      processRun(0, 0, 0)
    }

    def processRun(x: Int, y: Int, num: Int): Array[Array[Int]] = {

      array(x).update(y, num)
      if (width * height -1 == num) array
      else {
        val nextPos = nextPosition(x, y, num)
        processRun(nextPos._1, nextPos._2, nextPos._3)
      }
    }

    def nextPosition(x: Int, y: Int, num: Int): (Int, Int, Int) = {
      val position = direction match {
        case RIGHT => (x, y+1, num+1)
        case DOWN => (x+1, y, num+1)
        case LEFT => (x, y-1, num+1)
        case UP => (x-1, y, num+1)
      }

      if (position._1 != -1 &&
        position._1 != width &&
        position._2 != -1 &&
        position._2 != height &&
        array(position._1)(position._2) == -1) {
        position
      } else {
        changeDirection()
        nextPosition(x, y, num)
      }

    }

    def changeDirection() = {
      direction = direction match {
        case RIGHT => DOWN
        case DOWN => LEFT
        case LEFT => UP
        case UP => RIGHT
      }
    }

  }

  def printArray(args: Array[Array[Int]]) {
    for (row <- args) println(row.mkString("\t"))
  }

  val array = new SpiralArray(6, 6);
  val resultArray = array.process()
  printArray(resultArray)
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 123
java x 25
scala x 3
python x 40
delphi x 1
javascript x 1
lisp x 2
기 타 x 11
go x 1
cpp x 30
objectivec x 1
clojure x 1
ruby x 2
cs x 5