알고리즘 풀이 백준(BOI) 17140) 이차원 배열과 연산 (Python)

백준(BOI) 17140 - 이차원 배열과 연산

---

 

 

 

17140번: 이차원 배열과 연산

 

[문제풀이]

 

 

  3 * 3 배열을 입력받고 'R' 연산과 'C'연산을 계속 반복하여 테이블을 변형시키다가 원하는 인덱스에 원하는 숫자가 있을 경우 이때의 Count를 출력해주는 문제이다.

 

 R연산과 C연산은 대상을 테이블의 로우로 할 것인지 칼럼으로 할 것인지만 다르고 연산 방법은 같다.

 

연산 방법은 다음과 같다.

 

R연산 (행의 길이 >= 열의 길이) : 테이블 행 하나하나를 대상으로 실행한다.  테이블의 첫 번째 행이 [1,3,2,1] 일 경우 1이 두 개, 2가 한 개, 3이 한 개 이므로 결과는 [2,1,3,1,1,2]이다. 정렬순서는 횟수의 오름차순을 우선으로 하고 동일 횟수일 경우 숫자의 오름차순으로 한다. 두 번째 행이 [1 2 1] 일 경우 [2 1 1 2]인데, 만약 여기서 연산이 종료된다면 테이블 각 행의 최고 길이는 6이므로 빈칸을 0으로 메운다. 즉 [2 1 1 2 0 0] 이 된다.C연산 (행의 길이 < 열의 길이) :  R연산과 동일하지만 대상이 테이블의 열이다.

 

 위 연산을 반복하다 100의 길이를 넘어가면 나머지는 버린다. 이후 원하는 좌표에 원하는 값이 있을 경우 종료하고 카운트를 반환하는 문제이다.

 

 

이 문제는 배열의 정렬방법과 몇 가지만 주의하면 쉽게 풀 수 있다.

 

 먼저 말하자면 필자는 틀리게 제출했는데 맞았다. 제출하던 중 배열의 길이가 100이 넘어가면 초과된 부분은 버리는 코드를 작성하지 않은 걸 깨달았는데 정답처리가 되었다. 테스트 케이스에 그런 경우가 존재하지 않는 것 같다.

 

 위 연산은 딕셔너리를 이용했고 정렬은 람다식으로 했다. 딕셔너리를 이용한 이유는 1이 존재하면 거기에 밸류 값만 늘려주는 방식이 왠지 편할 것 같았다.  R연산을 예시로, 다음과 같이 구현했다. 딕셔너리를 초기화하고 행을 탐색한다. 행의 한 열 한 열에 대해 딕셔너리에 키가 존재하면 밸류에 +1을, 키가 존재하지 않으면 그 숫자에 대한 키:밸류 값을 만들어준다. (ex. 3 : 1)

dic = {}
"""
... 이하생략 ...
"""
if dic.get(item) is None:
	dic.update({item:1})
else:
	num = dic.get(item)
	num += 1
	dic.update({item:num})

 

 

 이후 정렬을 해주면 문제에서 요구하는 배열과 똑같아진다. 정렬은 이중 정렬로 람다식을 사용했다. 정렬의 우선순위는 출현 횟수를 우선으로 오름차순으로, 동일할 경우 숫자를 오름차순으로 정렬해주는 것이다.

arr = sorted(dic.items(), key = lambda x: (x[1], x[0])) 

 

dic.items()는 딕셔너리를 배열 형태로 리턴해준다. 이 배열을 가지고 (키 = 람다식) 기준으로 정렬해준 후 arr에 대입한다. 람다식은 딕셔너리의 인덱스 1의 밸류 값(출현 횟수)을 1순위로, 인덱스 0의 밸류 값(숫자)을 2순위로 하여 정렬해준다. c.f) x[1] 앞에 -를 붙여주면 내림차순이 된다.

 이후 배열을 반환하고 그 배열을 가지고 다시 R, C연산을 하면 된다.

 

 

 

 

 문제를 풀다 주의해야할 함정이 하나 있다.

 

예제 6에서 오류가 났으면 깨달았을 수도 있지만 다음과 같은 입력을 보자.

 

3 3 3
1 1 1
1 1 1
1 1 1

 

grid[2][2] == 3 이 오면 종료된다. 하지만 함정이다. 위 배열은 첫 번째 r연산을 거치면 3*2 배열이 된다.

# 초기상태
[1 1 1]
[1 1 1]
[1 1 1]
# R연산 (r >= c)
[1 3]
[1 3]
[1 3]
# R연산 (r >= c)
[1 1 3 1]
[1 1 3 1]
[1 1 3 1]

첫 번째 R연산을 거친 후 grid[2][2] 를 별다른 조건 없이 체크하게 되면 런타임 에러다. 주의하자. 

 

이 문제는 로직이라 할 게 따로 없으니 정리하지 않겠다. 

 

---

 

[전체 소스코드]

def go(indi):
    global grid
    arr = []; result = []
    dic = {}
    maxlength = 0
    #R연산
    if indi == 0:
        for i in range(len(grid)):
            dic.clear()
            arr.clear()
            for j in range(len(grid[i])):
                if grid[i][j] != 0:
                    arr.append(grid[i][j])
            for item in arr:
                if dic.get(item) is None:
                    dic.update({item:1})
                else:
                    num = dic.get(item)
                    num += 1
                    dic.update({item:num})
            arr.clear()
            arr = sorted(dic.items(), key = lambda x: (x[1], x[0])) 
            temp = []
            for item in arr:
                for item in item:
                    temp.append(item)
            result.append(temp)
            for item in result:
                maxlength = max(maxlength , len(item))
            returnArr = [[0 for _ in range(maxlength)]for _ in range(len(grid))]
            for i in range(len(result)):
                for j in range(len(returnArr[0])):
                    if j < len(result[i]):
                        returnArr[i][j] = result[i][j]            
    #C연산
    else:
        for i in range(len(grid[0])):
            dic.clear()
            arr.clear()
            for j in range(len(grid)):
                if grid[j][i] != 0:
                    arr.append(grid[j][i])
            for item in arr:
                if dic.get(item) is None:
                    dic.update({item:1})
                else:
                    num = dic.get(item)
                    num += 1
                    dic.update({item:num})
            arr.clear()
            arr = sorted(dic.items(), key = lambda x: (x[1], x[0])) 
            temp = []
            for item in arr:
                for item in item:
                    temp.append(item)
            result.append(temp)
            for item in result:
                maxlength = max(maxlength , len(item))        
            returnArr = [[0 for _ in range(len(grid[0]))]for _ in range(maxlength)]
            for i in range(len(result)):
                for j in range(len(returnArr)):
                    if j < len(result[i]):
                        returnArr[j][i] = result[i][j]                        
    return returnArr
    
r, c, k = map(int, input().split())
r-=1; c-=1
grid = [list(map(int, input().split())) for _ in range(3)]
answer = 0
while True:
    if r < len(grid) and c < len(grid[0]):
        if grid[r][c] == k : break
    answer += 1
    if answer > 100 : answer = -1; break
    if len(grid) >= len(grid[0]): grid = go(0)
    else: grid = go(1)
print(answer)