Spiral Array/임인택

각 방향별로 포인터가 이동하는 회수를 세는 방법으로 만들어봄.
가령 4x5 의 array라면,

1	2	3	4
14	15	16	5
13	20	17	6
12	19	18	7
11	10	9	8

이런 순으로 배열이 되게 되는데, (시작점과 끝점을 제외하고) 포인터의 이동방향을 나열해보면 →→→ ↓↓↓↓↓ ←←← ↑↑↑ →→ ↓↓ ← ↑ 순으로 된다. 여기에는 간단한 규칙성이 생기는데 (첫줄의 움직임을 제외) 다음과 같은 수식으로 포현될 수 있다.

현재 방향으로 진행횟수 = 반대 방향의 진행회수+1

이 식으로 간단한 수열을 만들 수 있고, 이 수열로 배열의 인덱스를 바꿔가며 값을 채워나간다.

처음에는 다른 디자인으로 접근을 했는데, 일단은 문제를 풀어보자는 취지 하에 제일 쉽게 풀릴것 같은 방법을 사용하였다.

~cpp 
# -*- coding: UTF-8 -*
import unittest

def makeRotList(row, col):
	rotList = []
	row -= 1
	col -= 1

	rotList.append(row)
	while True:
		#cols
		rotList.append(col)
		if col == 1:
			rotList.append(row)
			break

		#rows
		rotList.append(row)
		if row == 1:
			rotList.append(col-1)	# 제일 첫줄을 (루프전에 )이미 리스트에 넣었기 때문에 1을 빼야 함
			break
		
		row-=1
		col-=1
	return rotList

def makeSpirialArray(rows, cols):
	s = Sequence()

	SpirialArray = []
	for i in range(rows):
		SpirialArray += [[0]*cols]

	index = [0,0]
	value = 0

	SpirialArray[index[0]][index[1]] = value + 1
	value += 1
	
	rotList = makeRotList(rows, cols)
	
	for i in rotList:
		dir = s.next()
		for j in range(i):
			index[0] += dir[0]
			index[1] += dir[1]
			SpirialArray[index[0]][index[1]] = value + 1
			value += 1

			print index

	return SpirialArray


class Sequence:
	def __init__(self):
		self.sequence = [[1,0],[0,1],[-1,0],[0,-1]]
		self.idx = 3
	def next(self):
		if self.idx == 3:
			self.idx = 0
		else:
			self.idx += 1
		return self.sequence[self.idx]

class MyTest(unittest.TestCase):
	def testNextSeqence(self):
		s = Sequence()
		self.assertEquals([1,0], s.next())
		self.assertEquals([0,1], s.next())
		self.assertEquals([-1,0], s.next())
		self.assertEquals([0,-1], s.next())
		self.assertEquals([1,0], s.next())

	def testRotList(self):
		expected = [5,3,5,2,4,1,3]
		self.assertEquals(expected, makeRotList(6,4))
		expected = [3,5,3,4,2,3,1,2]
		self.assertEquals(expected, makeRotList(4,6))
		expected = [2,2,2,1,1]
		self.assertEquals(expected, makeRotList(3,3))
		expected = [3,3,3,2,2,1,1]
		self.assertEquals(expected, makeRotList(4,4))

	def testArrayCreation(self):
		testArr = [[0]*3]*3
		expected = [[0,0,0],[0,0,0],[0,0,0]]
		self.assertEquals(expected, testArr)

if __name__=='__main__':
	#unittest.main(argv=('','-v'))
	print makeSpirialArray(3,3)
	print makeSpirialArray(6,4)

문제분류, SpiralArray