단계별로 풀어보기 백준_10810번

공 넣기

문제는 다음과 같습니다.

 

 

문제를 요약하자면 바구니를 리스트라고 표현하고, 리스트안에 계속해서 업데이트를 해서 최종적으로 수정 된 리스트가 올바르게 출력되는 프로그램을 작성하는 문제입니다.

 

이 게시글 부터는 예제 입력 부분에서 입력을 받는 부분은 언급하지 않겠습니다.

저의 알고리즘은 다음과 같습니다.

 

먼저 N만큼의 0으로 채워진 리스트를 생성합니다.

이후 M만큼의 반복을 하며 받은 M이라는 리스트에서 M[0], M[1], M[2]를 각각 인덱싱 합니다.

이후 단순하게 N만큼 0으로 채워진 L리스트에 그 수만큼 값을 할당 해줍니다.

 

L = []
A, B = map(int, input().split())

for _ in range(A):
    L.append(0)

for _ in range(B):
    M = list(map(int, input().split()))
    m0 = M[0] - 1  
    m1 = M[1] 
    values = M[2]
    
    L[m0:m1] = [values] * (m1 - m0)

print(" ".join(map(str,L)))

 

이 문제에서의 키 포인트는 L[m0:m1] = [values] * (m1 - m0) 입니다.

파이썬을 많이 하셨던 분들도 이 리스트의 기초를 모르시는 분들도 많을 것 이라고 생각합니다.  먼저 저희가 원하는 길이가 3이라고 가정했을 때 3만큼 인덱싱 한 길이를 스칼라 값에 매핑하는 것은 오류를 발생시킵니다.

따라서 받는 값 역시 리스트로 표현해줘야 합니다. 따라서 같은 값을 할당할 것 이기 때문에 [values ] 에 그 크기만큼 곱해줘 리스트를 복사하는 방법이 있습니다.

 

제가 접근한 2번째 코드 풀이 입니다. 이중 for문으로 들어가 값을 직접 할당하는 방식입니다. 하지만 이는 시간복잡도를 심하게 초래할 수 있기 때문에 지양합니다. 

#10810번
L=[]
A,B = map(int,input().split())

for _ in range(A):
    L.append(0)
    
for _ in range(B):
    M = list(map(int,input().split()))
    m0 = M[0]
    m1 = M[1]+1
    values = M[2]
    for k in range(m0-1,m1):
        L[k] = values
print(" ".join(L))