문제
https://www.acmicpc.net/problem/17140
접근 방식
문제에서 하라는대로 따라가면 되는 전형적인 시뮬레이션(구현) 문제다.
단순하게 표현하면:
최대 100초 -> 100번 도는 loop 내에서:
- matrix[r][c] == k 여부 확인해서 loop 탈출
- R연산 / C연산이런 알고리즘인데, 어떻게 접근할지는 다들 어렵지 않게 생각할 거 같은데, 구현하면서 중간중간 막히는 게 있었을 것 같다. 개인적으로 소소한 구현 팁들을 얻어가기 좋은 문제였다.
코드
from collections import Counter
from itertools import chain
def rc_calc(matrix, n): # R 연산 + matrix trimming
max_n = -float('inf')
for i in range(n): # 행별 sort
target = [x for x in matrix[i] if x != 0] # 0 제외 시키고
sorted_lst = sorted(Counter(target).items(), key=lambda x: (x[1], x[0]))
matrix[i] = list(chain(*sorted_lst)) # 2차원 -> 1차원 -> 다시 해당 행에 담기
max_n = max(max_n, len(matrix[i])) # 최대 길이 tracking
# 최대 행 길이에 맞춰 0 채우기
for i in range(n):
if len(matrix[i]) < max_n:
matrix[i] = matrix[i] + [0] * (max_n - len(matrix[i]))
matrix[i] = matrix[i][:100]
r, c, k = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(3)]
time = -1
for t in range(101):
r_len, c_len = len(matrix), len(matrix[0]) # 세로 길이, 가로 길이
if 0 < r <= r_len and 0 < c <= c_len and matrix[r - 1][c - 1] == k:
time = t
break
# R 연산 / C 연산 (+ matrix trimming)
if r_len >= c_len:
rc_calc(matrix, r_len)
else:
matrix = list(map(list, zip(*matrix))) # zip 활용 -> 행열 변환 (transpose)
rc_calc(matrix, c_len)
matrix = list(map(list, zip(*matrix))) # 원상복귀
print(time)처음에는 matrix를 뒤집지 않고 R연산, C연산 따로 구현했었다. 그러다가 C연산 구현하면서 고려할 게 많아서 matrix 뒤집고 R연산 하나 사용하는 게 속 편하다는 걸 깨달았,,🫠
💡 PYTHONIC TIPS
1. 2차원 배열을 1차원 배열로 !
list(chain(*sorted_lst))
itertools의 chain 메소드와 unpacking을 활용한 방식이다.
chain은 인자로 받은 iterable을 연결(concat)하는 메소드로, 2차원 리스트를 unpacking 하면 여러개의 1차원 리스트가 되어, 이를 연결하면 하나의 긴 1차원 리스트로 만들 수 있다.
📌 참고 자료
2. 행렬 뒤집기
list(map(list, zip(*matrix)))
zip과 unpacking을 활용해서 행렬을 전치시키는 방식으로, 이것도 한번 잘 알아두면 유용하게 활용할 수 있다.
간단하게 부연 설명하자면,
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
이런 이차원 배열이 있다면, *matrix로 언패킹 한다면 1차원 배열 세개로 unpacking 될 것이다. 이렇게 :
- 리스트1: [1, 2, 3]
- 리스트2: [4, 5, 6]
- 리스트3: [7, 8, 9]이를 zip한다면? (-> zip 함수는 길이가 동일한 iterable을 묶어준다)
- [1, 4, 7]
- [2, 5, 8]
- [3, 6, 9]이렇게 iterable이 만들어질 것이다. 이를 각각 list 형태로 만들고 전체를 list로 묶으면 행렬이 전치된 2차원 행렬이 만들어지는 것이다.
📌 참고 자료
etc
또 새로웠던 점은 슬라이싱 시, 범위를 넘어서도 인덱스 오류가 나지 않는다는 점이다.
matrix[i] = matrix[i][:100]➡️ 100까지 존재하지 않더라도 사용 가능
📌 https://stackoverflow.com/questions/9490058/why-does-substring-slicing-with-index-out-of-range-work
파이썬 사용할수록 느끼는거지만.. 너무 편리한 모듈이 많아서 사람을 버릇없게 만든다,, 떼잉
