Jenikeju

내가 푼 풀이

접근방법 1. DFS 백트래킹 (시간초과)

최단시간을 구하는 문제는 BFS와 맞다..

1. 미로를 진입해 레버를 찾기까지 걸린시간을 구한다.

2. 레버를 찾았다면 레버위치에서 출구까지의 걸린시간을 더한다.

3. 레버를 못찾거나, 탈출구를 못찾았다면 -1출력

-> 이방법을 처음에 생각해서 사용해봤는데, 시간초과를 피할 수 없었다.

최악의 경우 모든 길을 찾아야하므로 BFS를 이용하기로 했다.

접근방법 2. BFS

DFS를 실패하고 바로 BFS를 설계했지만, BFS도 시간초과가 좀 났었다.

BFS는 인접한 지점 먼저 탐색이지만, 이미 탐색한곳은 재탐색을 하지 않게 해줘야한다.

재탐색여부를 저장하는 visited[Bool]에 값을 넣는 시점에따라 완전탐색, 조건에맞는 부분탐색을 하게 되었다.

BFS는 탐색시작지점에서 인접한 노드를 저장한다.

저장한 노드를 선입선출(큐와 같이)방식으로 빼내서 탐색을 실시한다.

여기서 탐색된곳임을 지정하는 과정이 다음노드를 넣을때 설정해줘야한다.

예로 [노드: 인접한노드]로 주어졌을때, [1: 2345] [2: 3456] [3: 45678] 이라면

1번 노드를 탐색했을때, 다음탐색은 2 - 3 - 4 - 5 를 탐색한다.

2번 노드를 탐색했을때, 다음탐색은 3 - 4 - 5 - 3 - 4 - 5 - 6 이된다.

2번과 인접한 노드는 이미 다음순서로 지정되있어서 중복탐색하게된다.

이렇게 큐에 쌓이지 않도록 하려면 인접한 노드를 넣을때, 그 노드는 이미 탐색이 되었다 라고 지정해줘야한다.

그러면 조건속에서 2번 노드를 탐색할때, 2번의 인접노드들은 이미 탐색된 노드들로 판단되므로, 큐에 쌓이지않는다.

이 점을 새기며, 코드를 수정하니 시간초과가 뜨지 않았다.

import Foundation

func solution(_ maps:[String]) -> Int {
    // 입력
    var map = [[String]]()
    var visited = [[Bool]]()
    var counted = [[Int]]()
    var start = (x: 0, y: 0)
    var lever = (x: 0, y: 0)
    var end = (x: 0, y: 0)
    for i in 0..<maps.count {
        let s = maps[i].map{String($0)}
        visited.append(Array(repeating: false, count: s.count))
        counted.append(Array(repeating: 10000000, count: s.count))
        map.append(s)
        for j in 0..<s.count {
            if map[i][j] == "S" {
                start = (x: j, y: i)
            }
            if map[i][j] == "L" {
                lever = (x: j, y: i)
            }
            if map[i][j] == "E" {
                end = (x: j, y: i)
            }
        }
    }
    // BFS
    var needVisit = [(x: start.x, y: start.y)]
    var index = 0
    var dx = [0,1,0,-1]
    var dy = [1,0,-1,0]
    var copyVisited = visited
    var copyCounted = counted
    copyCounted[start.y][start.x] = 0
    // lever위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        
        index += 1
        if cur.x == lever.x && cur.y == lever.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            needVisit.append((x: mx, y: my))
        }
    }
    // 레버에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveLeverTime = copyCounted[lever.y][lever.x]
    if arriveLeverTime >= 10000000 { return -1 }
    
    needVisit = [(x: lever.x, y: lever.y)]
    index = 0
    copyCounted = counted
    copyCounted[lever.y][lever.x] = 0
    copyVisited = visited
    // end위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        

        index += 1
        if cur.x == end.x && cur.y == end.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            needVisit.append((x: mx, y: my))
        }
    }
    // 출구에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveEndTime = copyCounted[end.y][end.x]
    if arriveEndTime >= 10000000 { return -1 }

    return arriveLeverTime + arriveEndTime
}

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

---

 

입출력 예시

rows	columns	queries	result
6	6	[[2,2,5,4],[3,3,6,6],[5,1,6,3]]	[8, 10, 25]
3	3	[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]	[1, 1, 5, 3]
100	97	[[1,1,100,97]]	[1]

내가 푼 풀이

- 회전을 구현하여 해당 범위를 교체하고, 최솟값을 저장한다.

- 따로 다른 알고리즘 없이 회전하는 동작을 구현하면 된다.

import Foundation

func solution(_ rows:Int, _ columns:Int, _ queries:[[Int]]) -> [Int] {
    var board = Array(repeating:Array(repeating: 0, count: columns+1), count: rows+1)
    var answer = [Int]()
    // 입력
    for i in 1...rows {
        for j in 1...columns {
            board[i][j] = ((i-1) * columns + j)
        }
    }
    
    // 쿼리 돌리기
    var b = board
    for query in queries {
        var a = moveNums(query, b)
        var minNum = a.removeLast()
        answer += minNum
        b = a
    }
    
    return answer
}

func moveNums(_ query: [Int],_ arr: [[Int]]) -> [[Int]] {
    var dx = [1, 0, -1, 0]
    var dy = [0, 1,  0, -1]
    var a = arr
    var mx = query[1]
    var my = query[0]
    var rc = query[3] - query[1]
    var cc = query[2] - query[0]
    var previous = a[my][mx]
    var minNum = a[my][mx]
    // 회전하며, 저장된 값과 그 다음의 값을 비교해 최솟값 갱신
    for i in 0..<4 {
        if i == 0 || i == 2 {
            for j in 0..<rc {
                mx += dx[i]
                my += dy[i]
                minNum = min(minNum, a[my][mx])
                var tmp = a[my][mx]
                a[my][mx] = previous
                previous = tmp
                
            }
        } else {
            for j in 0..<cc {
                mx += dx[i]
                my += dy[i]
                minNum = min(minNum, a[my][mx])
                var tmp = a[my][mx]
                a[my][mx] = previous
                previous = tmp
                
            }
        }
    }
    
    a.append([minNum])
    return a
}

내가 푼 풀이

- 주어진 연산자의 우선순위를 모든 경우의수로 탐색해본다.

import Foundation

func solution(_ expression:String) -> Int64 {
    var operation = ["+", "-", "*"]
    var arr = [String]()
    var oop = [[String]]()
    var num = ""
    var answer = Int.min
    // 우선순위의 모든 경우의수 뽑기
    func combi(_ targetArr: [String],_ arr: [String]) {
        if arr.count == 3 {
            oop.append(arr)
        }
        for i in 0..<targetArr.count {
            if !arr.contains(targetArr[i]) {
                combi(targetArr, arr + [targetArr[i]])
            }
        }
    }
    combi(operation, [])
    
    // 연산자와 피연산자 구분하여 저장
    for i in expression {
        if operation.contains(String(i)) {
            arr.append(num)
            arr.append(String(i))
            num = ""
        } else {
            num += String(i)
        }
    }
    arr.append(num)
    
    // 모든경우의수 탐색하여 최댓값 구하기
    for i in oop {
        var a = arr
        for j in i {
            a = operate(String(j), a)
        }
        answer = max(answer, abs(Int(a[0])!))
    }
    
    return Int64(answer)
}

// 주어진 연산자로 계산
func operate(_ op: String,_ expression: [String]) -> [String] {
    var ex = [String]()
    var index = -1
    for i in 0..<expression.count {
        if i == index {
            index = -1
            continue
        }
        if expression[i] != op {
            ex.append(expression[i])
        } else {
            var n1 = Int(ex.removeLast())!
            var n2 = Int(expression[i+1])!
            switch op {
                case "*":
                ex.append(String(n1 * n2))
                case "-":
                ex.append(String(n1 - n2))
                case "+":
                ex.append(String(n1 + n2))
                default :
                continue
            }
            index = i+1
        }
    }
    return ex
}

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

내가 푼 풀이

- 주어진 동작들을 함수로 구현한 뒤, 재귀호출 형식으로 구현한다.

import Foundation

func solution(_ p:String) -> String {
    return correctSameString(p)
}

// 전체적인 동작
func correctSameString(_ str: String) -> String {
    // 올바른문자열이라면 재귀 탈출
    if isCorrectString(str) {
        return str
    } else {
        var arr = divideString(s: str)
        // 분리한 문자열 u가 올바른 문자열이면 v는 다시 재귀호출
        if isCorrectString(arr[0]) {
            return "\(arr[0])" + "\(correctSameString(arr[1]))"
        } else {
            // 분리한 문자열 u가 올바른 문자열이 아니라면, v는 재귀호출하고, (v)u 형식으로 출력
            var s = ""
            var cs = ""
            var sarr = arr[0]
            // u문자열의 앞뒤 자르기
            if sarr.count != 0 {
                s = String(sarr.prefix(sarr.count-1))
                s.remove(at: s.startIndex)
            }
            // u문자열 뒤집기
            for i in s {
                if i == "(" {
                    cs += ")"
                } else {
                    cs += "("
                }
            }
            // 형식에 맞게 재귀호출
            return "(" + correctSameString(arr[1]) + ")" + "\(cs)"
        }
    }
}

// 문자열을 두개의 올바른 괄호문자열로 나눈다.
func divideString(s: String) -> [String] {
    var str = s
    var leftStr = ""
    var rightStr = ""
    for i in 1...str.count/2 {
        var index = i * 2
        leftStr = String(str.prefix(index))
        rightStr = String(str.suffix(str.count - index))
        if isSameCountString(leftStr) && isSameCountString(rightStr) {
            return [leftStr, rightStr]
        }
    }
    return [leftStr, rightStr]
}

// 균형잡힌 문자열인지 판단
func isSameCountString(_ p: String) -> Bool {
    var str = p
    var count = 0
    for i in str {
        if i == "(" {
            count += 1
        } else if i == ")" {
            count -= 1
        }
    }
    
    if count != 0 {
        return false
    } else {
        return true
    }
}

// 올바른 문자열인지 판단
func isCorrectString(_ p: String) -> Bool {
    var stack = [String]()
    for i in p {
        switch i {
            case "(":
            stack.append("(")
            case ")":
            if !stack.isEmpty {
                stack.removeLast()
            }
            default:
            continue
        }
    }
    if stack.isEmpty {
        return true
    } else {
        return false
    }
}

내가 푼 풀이

- 이문제의 구현방법은 어렵지않지만, 예외처리를 굉장히 엄격하게 해야한다.

접근방법:

1. 주어진 배열을 받아서 해당 노래의 음을 재생시간에 맞춰서 늘리거나 줄여줌(문제조건3번)

2. 조절된 음을 m의크기만큼 부분문자열로 만듬

3. 예외처리에 따라서 m과 동일한 문자열이 있는지 확인

4. 같은음이 다른 재생시간에서도 발견된다면, 음악길이가 긴것먼저, 음악길이도 같다면 먼저 재생된것으로 출력한다.

예외처리가 너무 빡셌다.. 특히 Swift는 문자열에대해 아주 가혹해서 더 어려웠던것같다.

확실히 카카오 문제는 구현도 어렵게 예외처리도 어렵게,,

*** 여러가지 예외들)

1. 음뒤에 #이 붙어있는것은 다른음으로 취급한다. #문자열 처리가 잘 되어있어야한다.

2. 노래의길이는 재생시간만큼 반복재생하거나 줄여야한다.

3. 부분문자열이 중간에 있을때, m과 동일한지 비교할 수 있어야한다.

코드로 구현하면 다음과 같다.(매우김)

import Foundation

func solution(_ m:String, _ musicinfos:[String]) -> String {
    var answer = ["0", "(None)"]
    var index = 0
    var musics = [[String]]()
    var mCount = m.count
    
    // 주어진 음악정보를 음악길이만큼 늘리거나 줄여서 따로 저장한다.
    while index < musicinfos.count {

        var infos = musicinfos[index].split(separator: ",")
        // 재생시간 계산
        let start = infos[0].split(separator: ":").joined(separator: "")
        let end = infos[1].split(separator: ":").joined(separator: "")
        let startNum = Int(start.prefix(2))! * 60 + Int(start.suffix(2))!
        let endNum = Int(end.prefix(2))! * 60 + Int(end.suffix(2))!
        let total = (endNum - startNum)
        
        // 음악이름, 음악의 음정
        let name = infos[2]
        var music = infos[3].map{String($0)}
        var converted = [String]()
        var musicIndex = 0
        
        // 음정 문자열을 배열로 변환
        while musicIndex < music.count {
            var str = music[musicIndex]
            if str == "#" {
                musicIndex += 1
                continue 
            }
            if musicIndex == music.count-1 {
                converted.append(str)
                musicIndex += 1 
                continue
            }
            if music[musicIndex+1] == "#" {
                str = str + "\(music[musicIndex+1])"
                converted.append(str)
            } else {
                converted.append(str)
            }
            musicIndex += 1
        }
        
        // 변환한 배열을 통해 재생시간만큼 줄이거나 늘린다.
        let a = converted.joined(separator: "")
        var musicString = ""
        var sin = 0
        for i in 0..<total {
            musicString += converted[sin]
            sin += 1
            if sin == converted.count {
                sin = 0
            }
        }
        // 음악길이로 조절한 음악을 따로저장
        musics.append([String(musicString.count),String(musicString),String(name)])
        index += 1
    }
    
    // 같은 음악인지 판단
    for i in musics {
        let length = i[0]
        var str = i[1]
        let name = i[2]
        
        var sine = 0
        var strs = [String]()
        
        // m의 길이만큼 부분문자열 배열 생성
        while true {
            if sine + mCount > Int(length)! { break }
            sine += 1
            strs.append(String(str.prefix(mCount)))
            str.remove(at: str.startIndex)
        }
        """
        같은 문자열인지 확인
        1. i == strs.count-1
        뒷자리가 #이 아닌문자열이 들어온다면 뒤에 #이 이어지는지 확인해야한다. 
        하지만 뒤에 오는 문자가 없다면 같은문자로 판단
        2. (i+1 < strs.count && strs[i+1].suffix(1) != "#") 
        뒷자리가 더 올수있는상황에서 그다음 부분문자열의 마지막문자가 #이 아니라면, 그 뒤로 #이 올 수 없다는 뜻
        그래서 같은문자로 판단 (#이 안오는 일반 음정이다.)
        (부분 문자열 순서는 ex.ABCD의 2길이 문자열 이라면 AB, BC, CD 이므로 BC 뒤에 오는문자는 CD의 마지막문자 D)
        """
        for i in 0..<strs.count {
            if strs[i] == m {
                if i == strs.count-1 || (i+1 < strs.count && strs[i+1].suffix(1) != "#"){
                    if Int(answer[0])! < Int(length)! {
                        answer = [String(length), String(name)]
                    }
                }
            }
        }
    }
    return answer[1]
}

내가 푼 풀이

첫번째 접근법: 당연히 완전탐색

1. 각 배열마다 최대공약수를 구한다.

2. 구한 최대공약수를 상대 배열에 전체적으로 나누어본다.

3. 나누어지지 않는 숫자중 최댓값 출력

4. 없다면 0

-> 시간초과

주어진 원소의 최댓값이 1억이라서 이방법으로 한다면 최대공약수를 구하는 반복문만 최대 1억번 돌리게된다..

두번째 접근법: 유클리드 호제법

시간을 단축하기위해 단순반복방법이 아닌 유클리드호제법으로 최대공약수를 구하는 시간을 줄인다.

1. 배열마다 유클리드호제법으로 최대공약수를 구한다. 반복은 배열의 갯수만큼(최대 50만번)

2. 구한 최대공약수로 상대배열을 나눠본다.

3. 나눠지면 0으로 초기화, 안나누어지면 그대로

4. 두개의 최대공약수중 최댓값 출력(둘다 나누어졌다면 0이되고, 한쪽만 나누어진다면 그 값이 최대가됨)

-> 성공

코드로 구현하면 다음과 같다.

import Foundation

// 유클리드를 이용한 gcd 재귀호출
func gcd(_ num1: Int,_ num2: Int) -> Int {
    if num2 == 0 {
        return num1
    } else {
        return gcd(num2, num1 % num2)
    }
}
func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    var fA = arrayA[0]
    var fB = arrayB[0]
    
    //A의 최대공약수
    for i in arrayA {
        fA = gcd(fA,i)
    }
    //B의 최대공약수
    for i in arrayB {
        fB = gcd(fB,i)
    }
    // A의 최대공약수로 B를 나눠봄, 나눠지면 0
    for i in arrayB {
        if i % fA == 0 {
            fA = 0
            break
        }
    }
    // B의 최대공약수로 A를 나눠봄, 나눠지면 0
    for i in arrayA {
        if i % fB == 0 {
            fB = 0
            break
        }
    }

    return max(fA, fB)
}

문제 설명

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
  • [대실 시작 시각, 대실 종료 시각] 형태입니다. 
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
  • 예약 시각이 자정을 넘어가는 경우는 없습니다.
  • 시작 시각은 항상 종료 시각보다 빠릅니다. 

내가 푼 풀이

어디선가 많이 본 익숙한 문제다.

1. 시작시간을 기준으로 오름차순 정렬한다.

2. 시작시간이 가장 빠른 예약부터 방에 넣는다.

3. 시작시간이 동일한경우, 종료시간이 빠른 예약부터 넣는다.

4. 방 중에 종료시간+10분과 다음예약이 같거나 크다면 해당방에 다음예약을 넣는다.

주의: 종료시간뒤 10분의 청소시간이 주어지므로 종료시간 + 10분 해야하지만, 50...59분 종료시간엔 시 단위가 바뀐다.

코드로 구현하면 다음과 같다.

import Foundation

func solution(_ book_time:[[String]]) -> Int {
    var reservation = [[Int]]()
    var rooms = [[Int]]()
    var answer = 0
    var index = 0
    // 시작시간과 종료시간을 숫자로 변환
    for i in 0..<book_time.count {
        var res = book_time[i]
        var start = res[0].split(separator: ":").joined(separator: "")
        var end = res[1].split(separator: ":").joined(separator: "")
        reservation.append([Int(start)!, Int(end)!])
    }
    
    // 예약배열을 시작시간 기준 오름차순으로 정렬
    // 시작시간이 같다면 종료시간이 빠른 순으로 정렬
    var sorted = reservation.sorted{ 
        if $0[0] == $1[0] {
        return $0[1] < $1[1]
    } else {
        return $0[0] < $1[0]
    }}
    // index: 정렬된 예약배열 인덱스
    // answer: 정답출력 변수
    while index < sorted.count {
        // 이용중인 방이 없다면 바로 넣는다.
        if rooms.isEmpty {
            rooms.append(sorted[index])
            index += 1
            answer += 1
            continue
        }
        // 다음예약자의 시작시간과 종료시간
        var resStart = sorted[index][0]
        var resEnd = sorted[index][1]
        var find = false
        // 이용중인 방이 있다면 종료시간들을 검사한다.
        for i in 0..<rooms.count {
            var end = rooms[i][1]
            end += 10
            var str = String(end)
            // 종료후 청소시간이 60~69 사이라면 시단위가 올라가야한다.
            if Int(str.suffix(2))! >= 60 {
                end += 100
                end -= 60
            }
            // 종료시간과 다음예약의 시작시간이 동일하거나 작다면 이 방으로 다음예약을 넣는다.
            if end <= resStart {
                rooms[i] = [resStart, resEnd]
                find = true
                break
            } 
        }
        // 교체가능한 방이 없다면 추가
        if !find {
            rooms.append([resStart,resEnd])
            answer += 1
        }
        index += 1
    }
    return answer
}