imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:05Z

New page

각 방향별로 포인터가 이동하는 회수를 세는 방법으로 만들어봄.
가령 4x5 의 array라면,
{| class="wikitable"
|-
| 1
| 2
| 3
| 4
|-
| 14
| 15
| 16
| 5
|-
| 13
| 20
| 17
| 6
|-
| 12
| 19
| 18
| 7
|-
| 11
| 10
| 9
| 8
|}

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

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

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

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

SpiralArray/임인택 - Revision history

imported>Unknown at 05:28, 7 February 2021