알고리즘 코드카타 122 - 테이블 해시 함수

https://school.programmers.co.kr/learn/courses/30/lessons/147354

프로그래머스

 

문제 설명
완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다.
첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.

해시 함수는 col, row_begin, row_end을 입력으로 받습니다.
테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다.
row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다.
테이블의 데이터 data와 해시 함수에 대한 입력 col, row_begin, row_end이 주어졌을 때 테이블의 해시 값을 return 하도록 solution 함수를 완성해주세요.

제한 사항
1 ≤ data의 길이 ≤ 2,500
1 ≤ data의 원소의 길이 ≤ 500
1 ≤ data[i][j] ≤ 1,000,000
data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다.
1 ≤ col ≤ data의 원소의 길이
1 ≤ row_begin ≤ row_end ≤ data의 길이

 

각 컬럼들의 특정 원소를 기준으로 오름차순 정렬하고 만약 같다면 기본키를 기준으로 내림차순 정렬을 해야한다. 그리고 정렬된 데이터를 기준으로 누적 bitwise XOR를 반환해야한다.

 

def solution(data, col, row_begin, row_end):
    answer = 0
    new_data = []
    
    return answer

 

우선 정렬된 리스트를 저장할 새로운 리스트를 초기화한다.

 

# def solution(data, col, row_begin, row_end):
#     answer = 0
#     new_data = []

    while data:
        compare_data = data.pop()
        index = 0
        if not new_data:
            new_data.append(compare_data)
        else:

#     return answer

 

data의 값을 하나 pop해서(앞이든 뒤든 관계없다.) new_data가 빈 리스트인 경우 new_data에 추가한다. 비어 있지 않은 경우에는 새로운 조건을 통해 데이터를 정렬할 수 있도록 하고 입력할 데이터의 인덱스값을 추적하기 위한 변수은 index를 초기화한다.

 

#     while data:
#         compare_data = data.pop()
#         index = 0
#         equal = False
#         if not new_data:
#             new_data.append(compare_data)
#         else:
            for d in new_data:
                if d[col-1] < compare_data[col-1]:
                    index += 1
                elif d[col-1] > compare_data[col-1]:
                    break
                else:
                
            new_data.insert(index, compare_data)


#     return answer

 

new_data에 새로 입력된 모든 데이터데 대해서 비교를 수행한다. 비교를 수행할 컬럼의 순번인 col은 순번을 1부터 계산하고 파이썬의 리스트의 순번은 0부터 계산을 하기 때문에 올바른 데이터를 비교하기 위해서 col-1번째 원소를 기준으로 비교를 해야한다.

시작인덱스는 0이고 현재 비교중인 데이터(d[col-1])가 입력예정인 데이터(compare_data[col-1])보다 작은 경우, 인덱스를 1증가시켜서 데이터가 입력될 위치를 조정한다. 그리고 만약 비교중인 데이터가 입력예정인 데이터보다 큰 경우 입력될 데이터의 올바른 인덱스를 찾았다는 의미이므로 반복문을 종료하고 현재 인덱스(index)에 현재 데이터(compare_data)를 입력해준다.

만약 비교중인 데이터와 입력예정인 데이터의 값이 같은 경우, 각 데이터의 고유키(0번째 원소)를 기준으로 비교를 해야하므로 새로운 조건을 입력해준다.

 

# def solution(data, col, row_begin, row_end):
#     answer = 0
#     new_data = []

#     while data:
#         compare_data = data.pop()
#         index = 0
#         equal = False
#         if not new_data:
#             new_data.append(compare_data)
#         else:
#             for d in new_data:
#                 if d[col-1] < compare_data[col-1]:
#                     index += 1
#                 elif d[col-1] > compare_data[col-1]:
#                     break
#                 else:
                    index = 0
                    for d2 in new_data:
                        if d2[col-1] != compare_data[col-1]:
                            index += 1
                        else:
                            if d2[0] > compare_data[0]:
                                index += 1
                            else:
                                break
#             new_data.insert(index, compare_data)

#     for i in range(row_begin-1, row_end):
#         answer ^= S_i(new_data[i], i)

#     return answer

 

compare_data가 입력될 새로운 인덱스를 찾기 위해서 index를 0으로 초기화하고 new_data의 모든 원소와 새로 비교를 수행한다.

new_data의 예상 모양은 [[col-1]이 다른 데이터들, ..., ... [col-1]이 같은 데이터들, ..., ... [col-1]이 다른 데이터들] 이므로 우선 index를 [col-1]이 같은 데이터들과 비교할 수 있도록 조정해야한다. 따라서 [col-1]의 값이 서로 다른 경우 index를 증가시켜서 다음 원소와 비교를 한다. 그리고 같은 경우에는 고유 키를 기준으로 내림차순 정렬을 해야하기 때문에 각각 [0]번째 원소를 비교하여 입력해야할 값이 더 작을 경우 index를 증가시키고 더 클경우 반복문을 종료하여 데이터를 현재 index에 입력을 하면 된다. (고유 키는 모두 다른 값을 가지기 때문에 같은 값에 대해서는 비교할 필요가 없다.)

 

이때 문제가 되는 점은 먼저 반복문을 종료할때, break를 사용했는데 위의 코드의 반복문은 두개가 중첩되어 있는 상태기 때문에 하나가 종료되더라도 더 상위에 있는 반복문은 종료되지 않아서 index의 값이 원하지 않아도 변한다는 점이고 또한 [col-1]이 다른 데이터들이 있는 구간을 지나서 [col-1]이 같은 데이터들을 기준으로 고유 키를 비교할 때, 입력될 데이터가 [col-1]이 같은 데이터들이 있는 구간의 가장 끝에 위치해야 할 경우 다시 [col-1]이 다른 데이터들이 있는 구간에 진입하게 된다는 것이다. 이것을 해결하기 위해서 코드에 새로운 변수를 하나 추가한다.

 

# def solution(data, col, row_begin, row_end):
#     answer = 0
#     new_data = []

#     while data:
#         compare_data = data.pop()
#         index = 0
        equal = False
#         if not new_data:
#             new_data.append(compare_data)
#         else:
#             for d in new_data:
                if equal:
                    break
#                 if d[col-1] < compare_data[col-1]:
#                     index += 1
#                 elif d[col-1] > compare_data[col-1]:
#                     break
#                 else:
#                     index = 0
#                     for d2 in new_data:
#                         if d2[col-1] != compare_data[col-1]:
                            if equal:
                                break
#                             index += 1
#                         else:
                            equal = True
#                             if d2[0] > compare_data[0]:
#                                 index += 1
#                             else:
#                                 break
                    else:
                        equal = True
#             new_data.insert(index, compare_data)

#     return answer

 

첫 반복문이 시작되는 시점에서 equal이라는 변수의 값을 False로 초기화한다. 그리고 equal이 True로 변하는 지점과 equal이 True일 때 종료되는 지점을 설정한다.

equal의 값이 True로 바뀌게 되는 지점은 두 곳으로 [col-1]의 값이 같아서 두번째 반복문으로 진입했을 때, [col-1]이 다른 데이터들이 있는 구간을 지나서 [col-1]이 같은 데이터들과 고유 키를 비교하는 지점이다. 해당 구간에 진입했을 때, equal의 값이 True로 변하게 되고 [col-1]이 같은 데이터들이 있는 구간을 통과하고 [col-1]이 다른 데이터들이 있는 구간에 다시 진입했을 때, 반복문을 즉시 종료하게 된다.

또한 두번째 for반복문이 정상적으로 종료된 경우(break를 통해서 중간에 정지되지 않았을 때) new_data에 있는 모든 데이터와 비교를 마쳤다는 의미로 [col-1]이 같은 데이터 중에서 고유 키가 가장 작은 값임을 의미한다. 이때 역시 첫번째 반복문을 계속해서 반복하는 상황을 방지하기 위해서 equal을 True로 변경해준다.

 

다시 첫번째 for 반복문으로 돌아가서, 반복문이 실행될때, equal의 값이 True라면, 이미 하위 반복문을 통과한 이후라는 의미이므로 즉시 반복문을 종료하고 현재 index값에 compare_data를 입력하면 된다.

 

이렇게 해서 문제의 설명대로 데이터들을 정렬할 수가 있는데... 사실 이렇게 복잡하게 작성할 필요는 없다. 파이썬의 sort()함수는 리스트 내의 리스트의 원소를 기준으로 정렬할 수 있기 때문이다.

 

def solution(data, col, row_begin, row_end):
    answer = 0
    data.sort(key=lambda x: (x[col-1], -x[0]))

    return answer

 

위의 코드를 통해서 data의 원소 x의 [col-1]을 기준으로 오름차순 정렬하고 그 값이 같은 경우 고유 키([0])을 기준으로 내림차순 정렬할 수 있다.

 

def S_i(data, i):
    i += 1
    result = 0
    for d in data:
        result += d % i
    return result

 

이제 문제에 주어진 조건에 따라 S_i함수를 작성한다. S_i는 현재 리스트의 모든 값을 현재 인덱스의 값으로 나는 나머지를 더해서 출력하는 함수이다. 현재 데이터를 data로, 인덱스를 i로 해서 값을 출력하도록 한다. i에 1을 더해준 이유는 컬럼의 순번이기 때문이다. 위에서 설명했듯 리스트의 원소의 순번은 0번부터 계산을 하기 때문에 문제에서 준 조건대로 컬럼의 순번인 1번부터 계산을 하기 위해서는 1을 더해야한다.

 

# def solution(data, col, row_begin, row_end):
#     answer = 0
#     data.sort(key=lambda x: (x[col-1], -x[0]))

    for i in range(row_begin-1, row_end):
        answer ^= S_i(data[i], i)

#     return answer

 

이제 row_begin과 row_end의 사이에 있는 모든 원소에 대해서 S_i를 취하고 XOR연산을 수행한다. XOR는 현재 두 값 answer, S_i(data[i], i)가 다를 경우 더해주고 같은 경우 0을 반환하는 연산이다.

answer의 시작값은 항상 0이기 때문에 S_i가 0이 아닐경우와 0인 경우 모두 S_i를 반환하게 된다. 따라서 굳이 S_i와 S_(i+1)을 비교할 필요가 없어진다. (answer의 값은 항상 S_(i-1)이 되므로)

따라서 위의 반복문을 수행하면 원하는 answer의 값을 반환할 수 있다.

 

완료!

 

위의 복잡한 코드는 문제의 설명을 보고 내가 직접 구현한 코드이고 아래의 간단간 코드는 위의 코드를 작성한 후에 혹시 리스트 내의 리스트의 원소를 기준으로 정렬이 가능할까 싶어서 찾아본 코드였다. lambda식을 잘 다루지 못하기 때문에 그 방법으로 직접 구현하는 것은 힘들었겠지만 아무튼 결과 자체는 동일하게 얻어낼 수 있었다. 물론 시간이 훨씬 오래걸렸기 때문에 좋은 코드는 아니었겠지만...