멍청한 나는 for문에 너무 집착한 나머지 1시간 동안 머리를 싸매다가 결국 Discuss를 보고 말았다.
while문이 무한루프를 도는 경우가 싫어서 왠만해선 for문을 써왔었는데 최근 Leetcode 문제들을 풀어보면 while이 그렇게 나쁜것도 아니고, 오히려 굉장히 실용적이라는 느낌도 들었다. 코딩문제를 풀때 while도 많이 애용해 봐야겠다고 생각했다.
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
MAX = 0
x = len(height) - 1
y = 0
while x != y:
if height[x] > height[y]:
area = height[y] * (x - y)
y += 1
else:
area = height[x] * (x - y)
x -= 1
MAX = max(MAX, area)
return MAX
이걸 for문으로 하려면 아주 난리를 쳐야했는데 만들면서도 굉장히 잘못됐다고 느꼈었다ㅋㅋㅋㅋ,,, while... 애용합시다!
대부분의 사람들이 그렇겠지만, 개인적으로 굉장히 어려워하는게 Node인데 하필이면 2번부터 Node가 나왔다ㅋㅋㅋ 번호 순서대로 풀지 말아야겠다는 생각이 강력하게 들었지만 의외로 또 문제가 쉬워보여서 도전해봤다. 어렵진 않았지만 Node의 개념을 모른다면 절대 못푸는 그런 문제... return값도 node라는게 아주 키포인트임!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 내 풀이
class Solution:
def addTwoNumbers(self, l1, l2):
# print(l1.next.next) # ListNode{val: 3, next: None}
# ListNode는 길이가 없다. 생각해보면 당연하지만 일단 len충인 나는 해봤다 봉변당함ㅋㅋ
# print(len(l1)) # 'ListNode' has no len()
result = 0
i = 0
# 우선 l1과 l2에 있는 데이터로 연산을 완료 (result)
while l1 or l2 :
if l1 != None :
result += l1.val*(10**i)
l1 = l1.next
if l2 != None :
result += l2.val*(10**i)
l2 = l2.next
i += 1
# for문을 돌리기 위해 int인 result를 str로 변경한 모습 (별로 좋다고 생각은 안함)
result = str(result)
# 여기서 진짜 웃긴게 cur을 사용하지 않으면 node가 제대로 이어지지 않는다.
answer = cur = ListNode(0)
# answer = cur = ListNode(0)이 아니고
# answer = ListNode(0)으로 해서 아래 for문을 cur 대신 answer쓰면 제대로 node 형성이 안됨
for i in range(len(result)-1,-1,-1) :
cur.next = ListNode(result[i])
cur = cur.next
# return도 제법 웃겨
return answer.next
속도 암담하다.. 아마 node 만들때 for문 쓴게 크지 않을까 하는 마음근데 같은 코드인데 제출할때마다 바뀌는거 보면 크게 신경 안써도 될것도 같고...
# Discuss에서 추천 수 많았던 코드
class Solution:
def addTwoNumbers(self, l1, l2):
carry = 0
root = n = ListNode(0)
while l1 or l2 or carry:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
# print(carry)
# print("v1 :",v1,"v2 :",v2)
carry, val = divmod(v1+v2+carry, 10)
# print(carry,val)
n.next = ListNode(val)
n = n.next
return root.next
위의 코드를 보면 결국에 나랑 비슷한 생각인데 나는 올림에 대해 어떻게 해야할지 모르겠어서 연산을 다 마치고 연산이 끝난 데이터를 역순으로 뽑아 node를 만들었다면, 이 사람은 한번에 node까지 만든것을 볼 수 있다. 올림을 저렇게 할 생각을 못했었는데 진짜 똑똑한것 같다.
속도면에서는 굉장히 앞도적으로 빠르다
이 부분에 대해서는 조금 더 공부한 내용을 추가하도록 하겠다! Node를 아주 부셔버리겠어...
알고리즘을 어떻게 공부해야할까 어느 사이트를 참고해야할까 엄청 고민하던 찰나에, 우연히 보게된 글에서 LeetCode로 공부하는게 좋다길래 참고하여 공부하려고 한다! Easy고 나발이고 x밥인 나는 이 사람 말대로 이것도 어려웠다ㅋㅎ,, 괜찮아.. 열심히 하면 늘겠지!
생각해보니까 문제 안올림ㅋㅋㅋ
# 내 코드
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
output = []
for i in range(len(nums)) :
target -= nums[i]
if target in nums[i+1:] :
output.append(i)
output.append(nums[i+1:].index(target)+i+1)
return output
target += nums[i]
return
Runtime , Memory
메모리 사용량은 적지만 시간이 굉장히 오래걸리는 내 코드... Discussion에 올라와있는 코드들은 딕셔너리를 사용하여 효과적으로 속도를 향상시킬 수 있었다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i, n in enumerate(nums):
if n in dic:
return [dic[n], i]
dic[target-n] = i
Runtime, Memory
근데 또 Discussion에서 나온 의견으로는 nums = [11, 2, 2, 7, 11, 15] , target = 9 일 때, 정답은 [1,3]인데 위의 코드로 하면 [2,3]이 나오는 오류가 발생한다... 근데 내코드는 잘 됨 헤헷 속도를 잃고 정확성을 얻었다 암튼 코딩 하수인 나는 리스트도 enumerate가 된다는 새로운 사실을 알았으니 그것만으로도 만족 헤헷,,, 그리고 딕셔너리 사용이 속도면에서 효과적이라는 것을 알았으니 이것도 만족 헤헷...
입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.
문제 해설
게임 요구 사항을 구현해보는 문제입니다. 같은 모양의 카카오프렌즈 블록이 2x2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임인데요. 인접한 모든 블록이 사라지는 실제 게임들과 달리 계산을 쉽게 하기 위해 2x2로 제한하고, 사라진 블록 자리에는 새로운 블록이 채워지지 않습니다. 그럼에도 불구하고 인접한 블록을 모두 스캔해야 하는 문제라 짧지 않은 코드가 필요했을 것 같네요. 이번 시험에서 가장 긴 코드가 필요한 문제였습니다. 자바의 경우 무려 80라인이나 필요했네요. 블록 매트릭스를 생성하여 스캔하고 제거해 나가는 작업을 반복하면서 더 이상 제거되지 않을 때 사라진 블록 자리의 수를 계산하면 됩니다.
이 문제의 정답률은 48.01%입니다.
import numpy as np
def block_game(data) :
# "CCBDE","AAADE","AAABF","CCBBF" 이렇게 되어있는 요소를 분리하여 저장
game = []
for i in data :
for j in range(len(i)) :
game.append(i[j])
# 게임은 m*n이므로 numpy를 사용해서 reshape 해줌
game = np.array(game).reshape(len(game)//len(data[0]),len(data[0]))
# 0으로만 이루어진 배열을 생성, 알파벳이 똑같으면 count해줄 용도로 사용
board = np.zeros(game.shape[0]*game.shape[1]).reshape(game.shape[0],game.shape[1])
# numpy -> list
game = game.tolist()
new_board = board.tolist()
count = 0
while 1 :
# 매번 0으로만 이루어진 배열을 리스트로 바꿔줌 / while문 탈출을 위한 조건을 위해서
new_board = board.tolist()
# 직접 print해서 생각하는게 빠름!
for i in range(len(game)-1) :
for j in range(len(game[i])-1) :
# 게임에 사용되어 터진 녀석들을 0으로 바꿔줬기 때문에 2*2가 0으로 전부 같으면 pass
if game[i][j] == game[i][j+1] == game[i+1][j] == game[i+1][j+1] == 0 :
continue
# 알파벳이 2*2로 동일하면 알파벳 위치와 동일한 위치의 new_board를 1로 바꿔줌
elif game[i][j] == game[i][j+1] == game[i+1][j] == game[i+1][j+1] :
new_board[i][j], new_board[i][j+1], new_board[i+1][j], new_board[i+1][j+1] = 1,1,1,1
# new_board의 1의 갯수 count
for i in new_board :
count += i.count(1)
# new_board가 1인 위치와 동일한 위치의 game을 0으로 바꿔주고, 바로 위에 있는 요소를 아래에 복사함
for i in range(len(new_board)) :
for j in range(len(new_board)) :
# 첫줄(i=0)에 없어진 캐릭터는 그냥 그 위치를 0으로 바꿔주는 것으로 끝냄
if new_board[i][j] == 1 and i == 0 :
game[i][j] = 0
# 없어진 캐릭터(new_board==1)자리 위에 뭔가 있으면 (i!=0)
# 위의 데이터를 없어진 캐릭터 자리로 옮기고 위의 데이터를 0으로 바꿈
elif new_board[i][j] == 1 :
game[i][j] = game[i-1][j]
game[i-1][j] = 0
# 0으로만 이루어진 리스트가 변화가 없다면 (전부 0이라면) 짝이 더 이상 없는 것이므로 count 반환
zero_count = 0
for i in new_board :
zero_count += i.count(1)
if zero_count == 0 :
return count
list_data = ["CCBDE","AAADE","AAABF","CCBBF"]
list_data2 = ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]
block_game(list_data)
