No older revisions available
No older revisions available
각 방향별로 포인터가 이동하는 회수를 세는 방법으로 만들어봄.
가령 4x5 의 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)
