2차원 배열 index 조절하기
2차원 배열 index 조절하기 — #LeetCode #개발자의도구들 only 파이썬 목표 참고 : 여기 전략 생각하기 1차 구현 s길이가 row길이 보다...
#LeetCode#Naver Blog
#LeetCode #개발자의도구들
- only 파이썬
- 목표 참고 : 여기
전략 생각하기
LeetCode(medium 6. ZigZag Conversion) 50.8%
✅ row는 항상 정해준다.
✅ 현재 idx가 만나는 문자는
>>> idx + 2row - 2이다.
✅ idx의 양끝 (0, row-1)은 항상 끝점만을 문자로 가진다.
>>> 0 < i < len(row) - 1까지는 추가로 문자를 만난다.
>>> i, i + 2row - 2 - i, i + 2row - 2 ...
👉 예시
A I G
B H I F H N
C G A F H M
D F B E J L
E C K
>>> row = 5, i = 0 ~ 4, gap = 2row - 2 = 8
>>> i, i + 2row - 2 - i, i + 2row - , i + 2(2row - 2) - i, i + 2(2row-2) ...
>>> i = 0
> 0, 8, 16, ...
>>> i = 1
> 1, 7, 9, 15, 17 ...
✅ 패턴이 정확하게 풀렸다.
1차 구현
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if len(s) <= numRows:
return s
gap = 2 * numRows - 2
result = ""
for i in range(numRows):
n_gap = gap
while 1:
if i + n_gap - i >= len(s):
result += s[i]
break
result += s[i] + s[i + n_gap -i]
if i + n_gap >= len(s):
break
result += s[i + n_gap]
n_gap *= 2
return result
- s길이가 row길이 보다 작은 경우는 그냥 예외처리 했다.
- 오답이다.
- 거의 다온 것 같은데 어딘가에서 로직이 실패한다.
- 삽질 후 깨달은건 로직이 잘 못되었다.
2차 시도
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if len(s) <= numRows:
return s
if numRows == 1:
return s
gap = 2 * numRows - 2
result = ""
for i in range(numRows):
print("start row i", i)
n_gap = gap
result += s[i]
while 1:
# gap idx check
print("start!", n_gap)
if n_gap - i >= len(s):
print("-i over", n_gap - i)
break
if i != numRows - 1:
result += s[n_gap - i]
print("result + n_gap - i", result)
#duplicated
if i + n_gap >= len(s):
print("+i over", n_gap + i)
break
if i != 0:
result += s[i + n_gap]
print("result + i + n_gap", result)
n_gap += gap
print("result", result)
return result
- ✅🫡🙆♀️🙆♀️ 정답이다.
- 뿌듯하다
- time : 83.47% Beats를 달성했다.
- 약 1.5h 정도 걸렸다.
- 로직에서 실수한 부분을 대대적으로 개편했다.
- n\_gap 값이 2배가 아니라 gap만큼 증가시켜야한다.
- 조건을 단순화 해야하고, i가 0 또는 마지막 idx일때 예외처리를 꼭 해줘야한다.
- gap조건은 > 0 일때 만족한다.
- 2numRows - 2 > 0
- numRows > 1 일 때만 고려하여 작성된 것이므로 numRows = 1일때 예외처리를 해줘야한다.
시간을 잡아먹는 괴물
짧게 후기를 남기자면, 규칙을 찾는건 쉬운데 이것을 도식화 하여 정확하게 코드로 풀어내는건 정말 쉽지가 않다. 규칙을 단순화 하는것도 십지 않고, 그 와중에 예외도 따로 생각해야 한다 ... 정말 쉽지 않다.
그나마 print문 찌어 보면서 문제를 풀면 디버깅이 훨씬 쉬운 것 같다. 마지막에 print 를 도입해서 디버깅 했는데 훨씬 빠르게 코드 수정이 가능했다. 적극 활용하자.
핵심은 어디에 print를 찍어야 하는지 잘 아는 것에 있다.
생각했었던 다른 방법
✅ rows x col을 구해서 미리 모두 선언하기
✅ 글자를 하나씩 읽으면서 r, c(행, 열 포인터)를 조절하기
>>> 1. down: r = 0에서 시작 row값만 증가
>>> 2. up : r = 바닥 -> r감소 c값 증가 -> r이 다시 0 이면 1.dwon으로 로직을 변경
👉 이렇게 해서 행열을 row로 읽어들이면 정답이 나올 것이다.
⌚ t : O(r x c) = o(n) (r, c)