๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Programming/Algorithm

[Algoritm] ํ–‰๋ ฌ ํšŒ์ „ (Python ๊ตฌํ˜„)

728x90
๋ฐ˜์‘ํ˜•

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์—์„œ ์ œ๊ณตํ•˜๋Š” ์นด์นด์˜ค 2020๋…„ ์‹ ์ž… ๊ฐœ๋ฐœ์ž ๋ธ”๋ผ์ธ๋“œ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ 1์ฐจ ๋ฌธ์ œ 3๋ฒˆ์„ ํ’€์–ด ๋ณด์•˜๋‹ค.

https://programmers.co.kr/learn/courses/30/lessons/60059

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ž๋ฌผ์‡ ์™€ ์—ด์‡ 

[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true

programmers.co.kr

 

ํ•ด๋‹น ๋ฌธ์ œ๋Š” ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•  ๊ฒƒ์ธ๊ฐ€๋ฅผ ์•Œ์•„๋‚ด๋Š” ๊ฒƒ๋ณด๋‹ค ๊ตฌํ˜„๋ ฅ์ด ํ•„์š”ํ•œ ๋ฌธ์ œ์˜€๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค.

 

ํ•ด๋‹น ๋ฌธ์ œ์˜ ๊ฒฝ์šฐ ์ œํ•œ ์‚ฌํ•ญ์˜ ํฌ๊ธฐ๊ฐ€ ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ํ™•์ธํ•˜๋Š” ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ•œ๋ฐ, ํ–‰๋ ฌ์˜ ํšŒ์ „๊ณผ ๋ฒ”์œ„๋ฅผ ์„ค์ •ํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ–ˆ๋‹ค.

 

๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 2์ฐจ์› ํ–‰๋ ฌ์˜ ํšŒ์ „์„ ๊ตฌํ˜„ํ•ด์•ผ ํ–ˆ๋‹ค.

ํšŒ์ „๊ตฌํ˜„์€ ๊ฐ„๋‹จ ํ•˜์ง€๋งŒ, ์ต์ˆ™ํ•˜์ง€ ์•Š๋‹ค๋ฉด, ๋ฐ”๋กœ ์ƒ๊ฐ๋‚˜์ง€ ์•Š์„ ์ˆ˜ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค. ํ•œ ๋ฒˆ์ฏค ์ •๋ฆฌํ•ด ๋†“์œผ๋ฉด ๋„์›€์ด ๋  ๋“ฏํ•˜๋‹ค.

๐Ÿ— 2์ฐจ์› ํ–‰๋ ฌ ํšŒ์ „

ํ•ด๋‹น ๋ฌธ์ œ์—์„œ๋Š” ํ–‰๊ณผ ์—ด์ด ๋™์ผํ•œ ์ •์‚ฌ๊ฐํ˜•์ด ๋ฌธ์ œ๋กœ ์ฃผ์–ด์กŒ์ง€๋งŒ, ์ผ๋ฐ˜์ ์ธ ์ƒํ™ฉ์„ ๊ณ ๋ คํ•ด์„œ ํ–‰๊ณผ ์—ด์ด ๋‹ค๋ฅธ n x m ํ–‰๋ ฌ์„ ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „์‹œ์ผœ ๋ณด์•˜๋‹ค.

 

์œ„์˜ ๊ทธ๋ฆผ์ฒ˜๋Ÿผ 3 x 4 ํ–‰๋ ฌ์€ ํšŒ์ „ ํ›„ 4 x 3 ํ–‰๋ ฌ์ด ๋˜์–ด์•ผ ํ•œ๋‹ค. (n x m -> m x n)

๊ธฐ์กด ํ–‰๋ ฌ์˜ ์—ด(column)์˜ ์ด๋™์€ ๋ณ€ํ™”๋  ํ–‰๋ ฌ์˜ ํ–‰(row)์˜ ์ด๋™์œผ๋กœ

๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰(row)์˜ ์ด๋™์€ ๋ณ€ํ™”๋  ํ–‰๋ ฌ์˜ ์—ด(column)์˜ ์—ญ ์ด๋™์œผ๋กœ ์›€์ง์ธ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

def rotate(arr):
    n = len(arr)		# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰์˜ ๊ธธ์ด
    m = len(arr[0])		# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ์—ด์˜ ๊ธธ์ด
    
    new_arr = [[0] * n for _ in range(m)]	# ์ƒˆ๋กœ์šด ํ–‰๋ ฌ ์ƒ์„ฑ(0์œผ๋กœ ์ดˆ๊ธฐํ™”), ๊ธฐ์กด ํ–‰๋ ฌ๊ณผ ํ–‰, ์—ด์ด ๋’ค๋ฐ”๋€œ

    for i in range(n):		# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰ ์ด๋™
        for j in range(m):	# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ์—ด ์ด๋™
            new_arr[j][n - 1 - i] = arr[i][j]
    return new_arr

์œ„ ๊ทธ๋ฆผ์„ ์ฝ”๋“œ๋กœ ํ‘œํ˜„ํ•˜๋ฉด ์œ„์™€ ๊ฐ™๋‹ค.

 

์ƒˆ๋กœ์šด ํ–‰๋ ฌ(new_arr)์˜ ํ–‰์€ ๊ธฐ์กด ํ–‰๋ ฌ์˜ ์—ด(j)๊ณผ ๊ฐ™๋‹ค.

์ƒˆ๋กœ์šด ํ–‰๋ ฌ์˜ ์—ด์€ ๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰(i)์˜ ์—ญ๊ณผ ๊ฐ™๋‹ค. ๋‹ค๋ฅด๊ฒŒ ํ‘œํ˜„ํ•˜๋ฉด ๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰(row)์˜ ์œ„์น˜๋ฅผ ์ƒˆ๋กœ์šด ํ–‰๋ ฌ์˜ ์—ด(column) ๊ฐ€์žฅ ๋’ค์—์„œ๋ถ€ํ„ฐ ๋Œ€์ž…ํ•ด์ฃผ๋ฉด ๋œ๋‹ค. (n -1 - i)

 

์ƒˆ๋กœ์šด ํ–‰๋ ฌ์˜ ์—ด(column)์˜ ๊ธธ์ด๋Š” ๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰(row)์˜ ๊ธธ์ด์™€ ๊ฐ™๊ณ  ๋ฐฐ์—ด์—์„œ index ์ ‘๊ทผ์„ ์œ„ํ•ด์„œ n - 1๋ถ€ํ„ฐ ์ ‘๊ทผํ•œ๋‹ค.

 

๋ฐ˜์‹œ๊ณ„ ํšŒ์ „

def rotate(arr):
    n = len(arr)		# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰์˜ ๊ธธ์ด
    m = len(arr[0])		# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ์—ด์˜ ๊ธธ์ด
    
    new_arr = [[0] * n for _ in range(m)]	# ์ƒˆ๋กœ์šด ํ–‰๋ ฌ ์ƒ์„ฑ(0์œผ๋กœ ์ดˆ๊ธฐํ™”), ๊ธฐ์กด ํ–‰๋ ฌ๊ณผ ํ–‰, ์—ด์ด ๋’ค๋ฐ”๋€œ

    for i in range(n):		# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ํ–‰ ์ด๋™
        for j in range(m):	# ๊ธฐ์กด ํ–‰๋ ฌ์˜ ์—ด ์ด๋™
            new_arr[m - 1 - j][i] = arr[i][j]
    return new_arr

๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์˜ ํšŒ์ „์€ ๋™์ผํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์œ„์™€ ๊ฐ™์ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

728x90
๋ฐ˜์‘ํ˜•