[프로그래머스/Lv.1 (Swift)] 이차원 배열, 해시 테이블 사용하기

 

2024 KAKAO WINTER INTERNSHIP - 가장 많이 받은 선물
2022 KAKAO BLIND RECRUITMENT - 신고 결과 받기

 

 

두 문제를 유사한 방법으로 해결했습니다.

 

잘못 생각하면 불필요한 순회를 넣게 되며, 타임아웃이 많이 생길 수 있을 것 같습니다.

해시테이블을 적절히 사용해야 합니다.

 

 

 

우선, 두 문제의 공통적인 특징은 A와 B 간의 관계를 기억하고 있어야 한다는 점입니다.

 

두 사람이 선물을 주고받은 기록이 있다면,
이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
(2024 KAKAO WINTER INTERNSHIP - 가장 많이 받은 선물)

각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
(2022 KAKAO BLIND RECRUITMENT - 신고 결과 받기)

 

 

선물을 준 사람 <-> 선물을 받은 사람

신고를 한 사람 <-> 신고를 당한 사람

 

위와 같이, 두 사람 간의 관계를 가지고 있어야 합니다.

 

여기에서 이차원 배열을 사용해야겠다는 아이디어를 얻을 수 있는데,

(A, B)와 (B, A)가 서로 다른 것으로 취급되기 때문입니다.

 

A가 앞에 오면 신고된 유저, 뒤에 오면 신고한 유저와 같이 순서가 존재하기 때문에 Set으로는 엮일 수 없습니다.

 

 

 

하지만, 배열은 Int 인덱스를 통해 접근합니다.

 

두 문제에서 우리가 관계를 정의해야 하는 사람들의 이름(id_lists, friends)은

String 형태로 주어지는데요.

 

그렇다면, 잠시 "이름값 그대로를 key로 사용하는 해시테이블을 만들어볼까?"

라는 생각을 해봅니다.

 

["선물을 주는 사람": ["선물을 받은 사람": 개수]] 를 갖는,

딕셔너리가 중첩된 구조도 생각해보았는데요.

 

'개수' 값을 가져오기 위한 과정이 복잡해집니다.

 

 

 

그래서, 각 사람들에게 고유의 Int 인덱스를 부여해 보았습니다.

 

 

예를 들어, 위와 같이 이름값들이 주어졌을 때,

["이름": 인덱스] 형태를 띄고 있는 해시 테이블을 만드는 것입니다.

 

이렇게 하면 문제를 풀 때,

"포차코"의 인덱스 값을 알고 싶다면 인덱스 딕셔너리에서 바로 뽑아올 수 있습니다.

 

var indexDict: [String: Int] = [:] // 인덱스를 담는 dict

// indexDict 초기화
for (index, friend) in friends.enumerated() {
    indexDict[friend] = index
}

 

초반에 이름들을 모두 순회하며, 주어진 이름의 인덱스를 value로 지정합니다.

 

 

 

 

그렇다면, 각 인덱스를 곧 각 사람의 고유 식별자 같이 여길 수 있으므로

	0	1	2	3
0
1
2
3

 

var giftArr = Array(repeating: Array(repeating: 0, count: friends.count), 
                    count: friends.count) // 행: 준 횟수, 열: 받은 횟수

 

위와 같이 이차원 배열만 만들어주면 됩니다.

 

 

 

 

위 이차원 배열에 값을 넣거나, 빼고 싶을 때는 어떻게 할까요?

 

// giver, taker 초기화
let split = gift.split(separator: " ")
let giver = String(split[0])
let taker = String(split[1])

// giver와 taker의 인덱스 뽑기
let giverIndex = indexDict[giver, default: 0]
let takerIndex = indexDict[taker, default: 0]

// giftArr 채우기
giftArr[giverIndex][takerIndex] += 1

 

 

위와 같이 이름 값에 대한 고유 인덱스를 indexDict에서 뽑아와,

이차원 배열에 바로 접근하면 됩니다.

 

 

해시 테이블을 사용했기 때문에,

각 관계에 대한 값을 찾을 때 O(1)의 시간복잡도를 가집니다.

 

 

---

 

 

더 좋은 방법들이 있겠지만 고차함수 혹은 기타 문법들이 아직 익숙하지 않아,

최대한 코드를 작성할 때 간소화하지 않고 생각하기 편한 방법으로 짜고 있습니다.

 

아래는 제가 작성한 답들입니다.

 

 

 

2024 KAKAO WINTER INTERNSHIP - 가장 많이 받은 선물

import Foundation

func solution(_ friends:[String], _ gifts:[String]) -> Int {
    
    var indexDict: [String: Int] = [:] // 인덱스를 담는 dict
    var giftArr = Array(repeating: Array(repeating: 0, count: friends.count), 
                        count: friends.count) // 행: 준 횟수, 열: 받은 횟수
    var expectedArr = Array(repeating: 0, count: friends.count) // 인덱스에 맞추어 
    var giftCountArr = Array(repeating: 0, count: friends.count)
    
    // 이름을 key로, 인덱스를 value로 하는 dict
    for (index, friend) in friends.enumerated() {
        indexDict[friend] = index 
    }
    
    // gifts 순회
    for gift in gifts {
        // giver, taker 초기화
        let split = gift.split(separator: " ")
        let giver = String(split[0])
        let taker = String(split[1])
        
        // giver와 taker의 인덱스 뽑기
        let giverIndex = indexDict[giver, default: 0]
        let takerIndex = indexDict[taker, default: 0]
        
        // giftArr 채우기
        giftArr[giverIndex][takerIndex] += 1
        
        // giftCountArr 채우기
        giftCountArr[giverIndex] += 1
        giftCountArr[takerIndex] -= 1
    }
        
    // expectedArr 채우기
    for i in 0..<friends.count {
        for j in 0..<friends.count {
            if i == j { continue }
            
            if giftArr[i][j] > giftArr[j][i] {
                expectedArr[i] += 1
            } else if giftArr[i][j] == giftArr[j][i] {
                if giftCountArr[i] > giftCountArr[j] {
                    expectedArr[i] += 1
                } 
            }
        }
    }
    
    let sortedArr = expectedArr.sorted { $0 > $1 }
    
    return sortedArr[0]
}

 

 

2022 KAKAO BLIND RECRUITMENT - 신고 결과 받기

import Foundation

func solution(_ id_list:[String], _ report:[String], _ k:Int) -> [Int] {
    
    var indexDict: [String: Int] = [:]  // 각 유저의 인덱스를 보관
    var reportArr = Array(repeating: Array(repeating: 0, count: id_list.count),
                          count: id_list.count) // 행: 신고자, 열: 피신고자
    var result: [Int] = Array(repeating: 0, count: id_list.count)        

    // indexDict 초기화
    for (index, id) in id_list.enumerated() {
        indexDict[id] = index
    }
    
    // report 순회
    for r in report {
        // 신고자, 피신고자 
        let split = r.split(separator: " ")
        let giver = String(split[0])
        let taker = String(split[1])
                
        let giverIndex = indexDict[giver, default: 0]
        let takerIndex = indexDict[taker, default: 0]
        
        // reportArr 업데이트
        if reportArr[giverIndex][takerIndex] == 0 { 
            reportArr[giverIndex][takerIndex] = 1
        }
    }
    
    // 열 별로 순회하면서, 값을 모두 더함
    // 만약 값이 k보다 클 경우, 1을 표시한 사람들의 인덱스로 +1    
    for i in 0..<reportArr.count {
        var sum = 0
        var giverArr = [Int]()
        
        for j in 0..<reportArr.count {
            if i == j { continue }
            if reportArr[j][i] == 1 { 
                sum += 1
                giverArr.append(j)
            }
        }
                
        if sum >= k {
            for g in giverArr {
                result[g] += 1
            }
        }
    }
    
    return result
}