21131. 행렬정렬 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

T = int(input())
for test_case in range(1, T + 1):
    N=int(input())
    matrix=[]
    for _ in range(N):
        matrix.append(list(map(int,input().strip().split())))
    swap=0
    count=0
    for i in range(N-1,0,-1):
        if matrix[i][i-1]>matrix[i-1][i]:
            if swap%2!=0:
                swap+=1
                count+=1
        else:
            if swap%2==0:
                swap+=1
                count+=1
    print(count)

• 문제에서 중요한 전제 조건은 ‘정렬 가능한’ 이다.
• transpose로 무조건 정렬이 가능하도록 행렬이 들어온다는 것이다. 따라서 x가 가장 큰 구간부터 조건에 만족하도록 transpose를 취하면 된다.
• diagonal을 기준으로 아래 행렬의 원소가 더 크기 때문에, 쌍을 이루는 2개의 원소만 비교해서 조건에 만족하지 않으면 tanspose했다고 가정한다.
• 이때 x크기의 행렬을 transpose하면 1~x-1 행과 열의 원소도 영향을 받기 때문에 swap의 횟수에 따라 x-1, x-2…에서 transpose할지 하지 않을지를 결정한다. (x-2에서 원래의 행렬은 transpose가 필요한데, 이미 x-1에서 transpose되었다면 할 필요가 없기 때문)