[Python/파이썬][🥈5] 백준 알고리즘 2563 - 색종이

📖[Python/파이썬][🥈5] 백준 알고리즘 2563 - 색종이

📜문제

---

구현

수학적 원리 및 기본 문법/함수들 속성을 이용하자
첫 접근을 잘하자
for문 하나라도 더 줄여서 시간을 줄여보자
#배열속성 #2차원배열

---

📕풀이방향

2차원 배열을 이용하여 흰색 도화지를 100*100을 0으로 초기화해놓고
색종이 받을 때마다 1로 매핑하여 최종 도화지 값들의 합을 구하자

---

📝알고리즘 구현순서

1. 2차원 배열으로 100*100 도화지를 0으로 초기화하자
2. 색종이 받을 때마다 for loof와 array속성을 이용하여 1로 매핑하자
3. 최종적으로 도화지 값들의 합을 구하자

---

💻결과코드

import sys
input = sys.stdin.readline

graph = [[0]*100 for _ in range(100)]  #도화지 초기화

for _ in range(int(input().rstrip())):
    x,y = map(int, input().split())
    for i in range(y,y+10):
        graph[i][x:x+10] = [1]*10  #array 속성을 이용하여 for loof처럼 동작

print(sum(map(sum,graph)))

---

📚내 기존 코드와 정리

✏️초기 코드

import sys
input = sys.stdin.readline

graph = [[0]*100 for _ in range(100)]

for _ in range(int(input().rstrip())):
    x,y = map(int, input().split())
    for i in range(y,y+10):
        for j in range(x,x+10):
            graph[i][j] = 1

print(sum(map(sum,graph)))

👉🏻 테스트케이스 for loof을 제외하더라도 for loof이 총 2개라 O(N2)으로,
총 116ms 시간이 걸렸음
왠지 문자열처럼 array에도 graph[y:y+10][x:x+10]과 같은 문법이 존재할 것 같아 시도해봤지만 에러가 발생하여 백준 유저들의 숏코딩을 참고함

---

✏️코드 개선 및 정리

for i in range(y,y+10):
  for j in range(x,x+10):
    graph[i][j] = 1
을 아래와 같이 개선함

for i in range(y,y+10):
  graph[i][x:x10] = [1]*10

👉🏻 아무래도 graph[y:y+10][x:x+10]은 1번째 인덱스와 2번째 인덱스 간의 구분이 애매하다보니
[x:x+10]과 같은 문법은 1회만 적용되는 것 같음
시간은 112ms로 4ms 줄어는 것을 확인할 수 있었음

---

정리

1. 구현문제는 첫 접근이 중요하다
   : 사실 첫 접근을 색종이 받으면서 10*10 해버리고, 두 번째 색종이부터는 겹치는 구간을 빼서 곱하려고 했었는데.... 3,4장 겹칠수록 정답이 아니라는 확신이 들었다🤦🏻‍♀️
   
   
2. array, string 등 기본 언어 문법에 충실하자
   : 알고리즘 문제가 아닌 이상 시간절약 및 메모리최소화 등 클린코드 구현은 기본 언어의 문법에 달렸다. 위 예제에서는 for loof을 줄여도 4ms라는 약소한 차이였지만, 실제 코드 구현에는 작은 습관이 큰 시간을 절약할 수 있을 것 같다. 물론 가독성 면에서는 for loof 여러 개 쓰는게 구분이 쉬워 좋아보이지만.... 상황에 따라 적절히 사용하자