백준 10810 공 넣기 파이썬 배열 풀이

1. 10810

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다.

도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다.

공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에 걸쳐서 공을 넣는 방법이 주어진다. 각 방법은 세 정수 i j k로 이루어져 있으며, i번 바구니부터 j번 바구니까지에 k번 번호가 적혀져 있는 공을 넣는다는 뜻이다. 예를 들어, 2 5 6은 2번 바구니부터 5번 바구니까지에 6번 공을 넣는다는 뜻이다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ N)

도현이는 입력으로 주어진 순서대로 공을 넣는다.

출력

1번 바구니부터 N번 바구니에 들어있는 공의 번호를 공백으로 구분해 출력한다. 공이 들어있지 않은 바구니는 0을 출력한다.

import sys

n, m = map(int, sys.stdin.readline().split())
basket = [0] * n

for _ in range(m):
	i, j, k = map(int, sys.stdin.readline().split())
	basket[i-1:j] = [k] * (j - i +1)
    
for x in basket:
	print(x, sep=' ')

 

코드 풀이

문제를 이해하는 것부터 굉장히 오래 걸렸다. 아무리 읽어도 이해가 안 돼서 노트에 한 줄씩 쓰면서 공이랑 바구니 그림을 다 그려서 겨우 이해했다. 문제를 푸는 방법도 변수를 입력받고 반복문을 써야하는 것까지는 알겠는데 그 다음부터 진행이 꼬여서 구글의 도움을 받았다. 

import sys 후 바구니 갯수 n과 공을 넣을 횟수 m을 입력받는다. sys.stdin.readline()으로 입력받고 split 메서드로 쪼갠 다음 map 함수를 사용해 정수형 타입으로 변경했다. 그리고 basket이라는 새로운 변수에 0이 n개만큼 들어간 리스트를 저장했다. n은 바구니 갯수이다. 바구니에 공이 들어가면 공의 번호를 출력할 수 있게 바구니 갯수와 같은 길이를 가진 리스트를 만들었다. 그리고 공이 들어있지 않은 바구니는 0을 출력한다는 조건이 있으므로 리스트에 0을 저장해 기본값을 0으로 지정했다. 

다음은 i, j, k를 입력받는 부분으로, i는 시작 바구니, j는 끝 바구니, k는 공 번호이다. 세 변수를 입력받는 코드는 위에서 n, m을 입력받았던 map(int, sys.stdin.readline().split())을 동일하게 사용했다. 0이 담긴 리스트(바구니들)에서 슬라이싱을 사용해 0이 있던 자리에 공 번호 k를 채운다. i번부터 j번까지의 바구니에 공을 넣는 것은 미리 만들어둔 바구니들(0이 담긴 리스트)의 0 값을 공 번호 k로 대체해주는 것과 같다. 슬라이싱으로 리스트에 접근해서 기존의 값을 공 번호 i로 바꿔주는 것이다. 

리스트를 슬라이싱 할 때 주의할 점은 리스트의 인덱스 번호는 0부터 시작한다는 것이다. 문제에서 바구니는 1번부터 시작한다. 따라서 원하는 바구니에 공을 넣으려면 시작 바구니 i에서 1을 뺀 값을 슬라이싱 시작 부분에 넣어야 한다. 이 부분이 너무 어려웠다. vscode에서 임의로 리스트를 만들어 이렇게 저렇게 슬라이싱 해본 것이 이해하는 데에 큰 도움이 되었다. 직접 실험해보기를 추천한다. 

이렇게 접근한 리스트의 요소들과 같은 길이의 k 값을 기존의 바구니(0이 담긴 리스트)에 할당하기 위해, k에 j - i +1 을 곱해준다. 1을 더해주는 이유는 위에서 언급한 것처럼 리스트의 인덱스 번호는 0부터 시작하기 때문이다. 슬라이싱은 지정한 끝값-1까지 가져오지만, 공은 끝 바구니 j까지 전부 넣어줘야 한다. i부터 j까지의 리스트 요소 전부를 k로 대체하기 위해 1을 더해줘야 한다. 글로 읽으면 더 헷갈리니까 리스트를 만들어서 슬라이싱하고 값을 대체해보는 게 이해하기 편하다. 

또한 문제의 입력 예시를 보면 2번 바구니에서 시작해 2번 바구니에서 끝나는 케이스가 있다. 만약 끝 바구니 2에서 시작 바구니 2만 뺀다면 k에 0이 곱해져 2번 바구니에 의도한 공 번호 k가 들어가지 않는다. 1을 더하면 시작 바구니 번호와 끝 바구니 번호가 같아도 공 번호가 제대로 들어간다. 

이 모든 과정을 for문 안에 넣고 공을 넣을 횟수인 m번만큼 반복시킨다. 공 번호가 제대로 들어간 리스트가 만들어졌으면 또 한 번 for문을 사용해 리스트 안의 요소들을 전부 출력한다. 구분자 sep=' '을 사용하면 각 요소가 공백으로 구분되어 출력된다. 

 

 

정답 제출까지 기나긴 여정이었다. 노트 두 페이지를 다 채우고 겨우 이해할 수 있었다. 티스토리로 풀이글을 쓰면서 다시 한 번 문제를 풀고 넘어갈 수 있었다. 문제를 제출하고 다음날 다시 풀어보면서 글을 쓰는 게 공부에 정말 좋은 방법같다.