[백준] 10163 색종이 (브론즈1) / 서브태스크, 시간초과 해결

문제요약

나의 코드 및 설명 (53점)

• 분명히 모든 조건을 충족했다고 생각했는데 100점이 아닌 53점이 나왔고, 원인은 마지막 조건에서의 시간초과 때문이었다.

n = int(input())

total = [[0] * 1001 for _ in range(1001)]

for i in range(1,n+1):
    a,b,w,h = map(int, input().split())
    for j in range(b,b+h):
        for k in range(a,a+w): #바뀌어야할 부분
            total[j][k] = i #바뀌어야할 부분

for i in range(1,n+1):
    result = 0
    for j in range(1001):
        result += total[j].count(i)
    print(result)

나의 코드 및 설명 (100점)

• 100점을 맞는 코드는 생각보다 간단했는데, 기존에는 이중 for문을 통해 전체 색종이를 표현한 리스트(1001*1001)의 눈금 하나하나의 정보를 바꿔주었지만, for문을 한번만 사용하여, 리스트 슬라이싱을 통해 특정 y축에 해당하는 모든 x축의 눈금을 바꿔주는 식으로 문제를 해결하는 것이다.
• 참고로, 리스트 슬라이싱 사용 시, 등호를 기준으로 오른쪽 항은 특정 값이 아닌 바꿔줄 리스트의 범위에 해당하는 리스트가 와야 의도한대로 값이 나온다.

n = int(input())

total = [[0] * 1001 for _ in range(1001)]

for i in range(1,n+1):
    a,b,w,h = map(int, input().split())
    for j in range(b,b+h): #바뀐부분
        total[j][a:(a+w)] = [i]*w #바뀐부분

for i in range(1,n+1):
    result = 0
    for j in range(1001):
        result += total[j].count(i)
    print(result)

피드백

전체 도화지에서 특정 도형의 넓이를 구할 때, 전체 도화지를 이차원 리스트를 표현하고, 특정 x,y 좌표에 해당하는 값을 바꿔주는 식으로 문제를 해결하는데, 이번 문제도 같은 방식으로 문제를 해결하면 될 것 같아서 풀었지만, 시간초과가 나서 당황했다.
이중 for문을 통해 값을 일일이 바꿔주는 방법도 있지만, 하나의 for문만 사용하여 y축에 해당하는 x의 값 전체를 바꿔주는 방법도 있다는 것을 명심하자.