본문 바로가기

알고리즘, 자료구조

[백준| 단계별로 풀어보기 4단계 1차원 배열 | Python] 10870번 공 넣기

1. 문제 목적

백준 10810번 문제는 간단히 말해, 공을 바구니에 넣는 문제입니다. 여기서는 N개의 바구니가 일렬로 놓여 있고, 각각의 바구니에 0번부터 N-1까지 번호가 매겨져 있습니다. 문제의 목적은 주어진 명령에 따라 특정 구간의 바구니에 특정 번호의 공을 넣는 방식으로, 배열 또는 리스트의 특정 구간에 값을 할당하는 방법을 익히는 데 있습니다.

2. 핵심 개념

  1. 리스트: 파이썬의 기본 자료구조 중 하나로, 여러 값을 순서대로 저장할 수 있습니다. 이 문제에서는 각 바구니를 리스트의 각 요소로 표현합니다.
  2. 슬라이싱: 리스트에서 특정 범위의 요소를 선택하는 방법입니다. 문제에서 특정 구간의 바구니에 공을 넣을 때 사용됩니다.
  3. 반복문: 특정 작업을 반복적으로 수행하게 하는 구문입니다. 이 문제에서는 여러 번의 명령을 처리하기 위해 사용됩니다.

3. 문제 해결 절차

  1. 바구니 초기화: N개의 바구니를 0으로 초기화된 리스트로 생성합니다.
  2. 명령 처리: 각 명령에 따라 지정된 구간의 바구니에 특정 번호의 공을 넣습니다. 이 때, 슬라이싱과 할당을 활용합니다.
  3. 결과 출력: 최종 바구니 상태를 출력합니다.
# 입력 처리
N, M = map(int, input().split()) # N: 바구니 개수, M: 명령 개수
basket = [0] * N # 바구니를 0으로 초기화

# 명령 처리
for _ in range(M):
    i, j, k = map(int, input().split()) # i부터 j번 바구니에 k번 공을 넣음
    basket[i-1:j] = [k] * (j-i+1) # 슬라이싱과 할당을 사용해 공을 넣음

# 결과 출력
print(' '.join(map(str, basket)))

4. 코드 분석

  • basket = [0] * N: N개의 바구니를 0으로 초기화하여 생성합니다. 각 바구니는 초기에 공이 들어있지 않다고 가정합니다.
  • for _ in range(M): M개의 명령에 대해 반복합니다.
  • i, j, k = map(int, input().split()): 한 줄에 입력된 i, j, k 값을 정수로 변환하여 가져옵니다. 여기서 i와 j는 공을 넣을 바구니의 범위, k는 넣을 공의 번호입니다.
  • basket[i-1:j] = [k] * (j-i+1): 슬라이싱을 사용하여 i-1번째부터 j-1번째 바구니까지 선택하고, [k] * (j-i+1)을 통해 해당 구간에 k번 공을 넣습니다. 파이썬에서 리스트의 인덱스는 0부터 시작하기 때문에 i-1로 처리합니다.
  • print(' '.join(map(str, basket))): 최종 바구니 상태를 공백으로 구분하여 문자열로 변환한 후 출력합니다.

5.추가 개념

파이썬에서의 리스트(List)

  • 동적 배열(Dynamic Array): 파이썬의 리스트는 사실 동적 배열에 가깝습니다. 리스트의 크기는 고정되어 있지 않으며, 프로그램 실행 중에 요소를 추가하거나 삭제함으로써 크기를 변경할 수 있습니다.
  • 다양한 데이터 타입: 하나의 리스트에 정수, 실수, 문자열 등 포함을 포함하여 다양한 타입의 데이터를 저장할 수 있습니다.
  • 내장 함수와 메서드 지원: 리스트를 조작하기 위한 다양한 내장 함수와 메서드(예: append(), remove(), sort() 등)를 지원합니다.

파이썬에서의 배열(Array)

  • 단일 데이터 타입: 파이썬의 배열(특히 array 모듈에서 제공하는 배열)은 모든 요소가 동일한 데이터 타입을 가져야 합니다. 이는 메모리 사용을 효율적으로 하고 성능을 최적화하는 데 도움이 됩니다.
  • 메모리 효율성: 배열은 동일한 데이터 타입의 요소만을 저장하기 때문에, 리스트에 비해 메모리를 더 효율적으로 사용할 수 있습니다. 이는 특히 대량의 숫자 데이터를 다룰 때 중요합니다.
  • 성능 최적화: 특정 타입의 데이터에 최적화되어 있기 때문에, 배열을 사용하면 특정 연산과 처리에서 리스트보다 더 나은 성능을 제공할 수 있습니다.

주요 차이점 정리

  1. 타입 제한: 배열은 동일한 타입의 데이터만 저장할 수 있으며, 리스트는 다양한 타입의 데이터를 저장할 수 있습니다.
  2. 성능과 메모리 사용: 배열은 리스트보다 메모리 사용이 효율적이며, 데이터가 동일한 타입일 때 더 빠른 연산이 가능할 수 있습니다.
  3. 사용 편의성: 리스트는 파이썬의 내장 타입으로서 더 다양한 메서드와 용이한 사용법을 제공합니다.

슬라이싱(Slicing)

  • 정의: 슬라이싱은 리스트나 문자열 같은 연속적인 데이터 타입에서 부분집합을 선택하는 연산입니다.
  • 문법: 리스트[시작인덱스:끝인덱스]의 형태로 사용되며, 시작인덱스는 포함되고 끝인덱스는 포함되지 않습니다. 예를 들어, 리스트[1:4]는 리스트의 두 번째 요소부터 네 번째 요소까지를 선택합니다.
  • 인덱스: 파이썬의 인덱스는 0부터 시작합니다. 따라서 i-1은 사용자가 생각하는 시작 인덱스를 파이썬의 인덱싱 방식에 맞추기 위해 조정하는 것입니다.

할당(Assignment)

  • 정의: 할당은 변수에 값을 저장하는 행위입니다. 리스트 슬라이싱에 할당을 사용할 때, 선택된 범위에 새로운 리스트의 내용을 대입합니다.
  • 활용: 슬라이싱된 부분에 새로운 리스트를 할당함으로써, 해당 부분의 값을 일괄적으로 변경할 수 있습니다.

구문 분석

  • basket[i-1:j]: basket 리스트에서 i-1번째 요소부터 j-1번째 요소까지의 부분집합을 선택합니다. 여기서 i-1이 사용된 이유는 파이썬이 0-based 인덱싱을 사용하기 때문입니다.
  • [k] * (j-i+1): 하나의 요소 k를 포함하는 리스트를 생성하고, 이를 (j-i+1)번 반복하여 확장합니다. 이는 i부터 j까지의 구간 길이와 같습니다. 결과적으로 k 값이 반복되는 새로운 리스트가 생성됩니다.
  • 할당 부분: 슬라이싱으로 선택된 basket의 부분에 [k] * (j-i+1)으로 생성된 리스트를 할당합니다. 이로써 i-1부터 j-1까지의 모든 요소가 k 값으로 대체됩니다.

6. 마무리

리스트의 인덱스에 접근하여 값을 변경하는 방법을 알 수 있었다.