(BOJ17140 이차원 배열과 연산

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/17140
• 풀이 링크
  • Python

• 이차원 배열이 주어지고, 해당 배열에서 특정 위치의 값이 원하는 값이 될 때까지의 연산 횟수를 구하는 문제이다.
• 연산은 지금 배열의 행, 열 길이에 따라 자동적으로 결정된다.
  • 연산을 적용하는 위치는 행, 열의 길이에 따라 바뀌지만,
  • 연산은 같은 방식으로 진행된다.
• 행의 길이, 열의 길이, 행에 연산, 열에 연산 등 조금씩 햇갈릴 수 있는 부분이 있어 이 부분만 주의하면 될 것 같다.

r, c, k = MIIS()
r, c = r - 1, c - 1
seq = [[0] * 100 for _ in range(100)]
for i in range(3):
    x, y, z = MIIS()
    seq[i][0] = x
    seq[i][1] = y
    seq[i][2] = z

• 최대 100개 길이만 사용한다고 했고, 때에 따라 리스트를 조정하는 것 보다 100 * 100의 리스트를 먼저 생성하는 것이 더 효율적일 것이라 생각함
• 그 후 왼쪽 위 3 * 3 구역에 값을 입력
• 인덱스가 0이 아니라 1부터 시작하는 값을 찾으므로, r, c는 1씩 빼줌

row, column = 3, 3
for count in range(101):
    if seq[r][c] == k:
        print(count)
        break
    if row >= column:
        for i in range(row):
            sort_row(i)
    else:
        for i in range(column):
            sort_column(i)
    count += 1
else:
    print(-1)

• 문제 풀이의 핵심 코드
• 우선 행의 길이, 열의 길이에 따라 연산을 적용하는 위치가 변경된다.
  • 그런데, 리스트를 동적으로 크기 조절하는 것이 아니라 100 * 100으로 고정했기 때문에 연산할 위치를 다시 탐색해야 하는 경우가 발생할 수 있다.
  • 그래서 지금 행, 열의 실질적 길이를 저장하기 위해 row, column 변수를 생성했다.
• 다음 for 문을 순회하며 탐색한다.
  • 처음에는 while문으로 구성했는데, 어짜피 탐색은 최대 100번까지만 하게 되어 for-else로 구성했다.
  • 문제에서 “100초가 지나도”라는 부분때문에 99초까지 탐색했는데 틀렸다는 결과가 나왔는데, 100초까지 탐색, 100초 초과는 -1 출력을 의미하는 것 같아서 위와 같이 구성했다.
• 만약 특정 위치 값이 일치하면 횟수를 출력, 종료하고, 아니라면 행, 열의 길이에 따라 연산을 수행한다.

def sort_row(idx: int):
    global seq, row, column
    count_nums = {}
    for i in range(column):
        x = seq[idx][i]
        if not x:
            continue
        if x in count_nums:
            count_nums[x] += 1
        else:
            count_nums[x] = 1
    new_nums = sorted([(v, k) for k, v in count_nums.items()][:50])
    for i, (x, y) in enumerate(new_nums):
        seq[idx][i * 2] = y
        seq[idx][i * 2 + 1] = x
    for j in range(len(new_nums) * 2, 100):
        seq[idx][j] = 0
    if column < len(new_nums) * 2:
        column = len(new_nums) * 2


def sort_column(idx: int):
    global seq, row, column
    count_nums = {}
    for i in range(row):
        x = seq[i][idx]
        if not x:
            continue
        if x in count_nums:
            count_nums[x] += 1
        else:
            count_nums[x] = 1
    new_nums = sorted([(v, k) for k, v in count_nums.items()][:50])
    for i, (x, y) in enumerate(new_nums):
        seq[i * 2][idx] = y
        seq[i * 2 + 1][idx] = x
    for j in range(len(new_nums) * 2, 100):
        seq[j][idx] = 0
    if row < len(new_nums) * 2:
        row = len(new_nums) * 2

• 각 연산이 행 또는 열에 적용될 때 각 행, 열을 정렬하는 함수
  • 두 함수에서는 유사한 부분도 많지만, 결과적으로 값을 추출, 적용하는 위치가 달라 두 개의 함수로 분리했다.
• 우선 최대 row * column 만큼만 값이 있으므로 해당 부분을 탐색하여 각 값의 갯수를 기록한다.
  • 다음 new_nums에 위에서 저장한 값을 하나씩 불러와서 저장 및 정렬하고, 그 값들을 기록한다.
• 배열 길이가 짧아질수도 있기 때문에 나머지 부분은 0으로 표시하고,
• 최대 길이를 갱신한다.