[프로그래머스] 완전탐색 알고리즘(Swift)

프로그래머스 코딩테스트 고득점 Kit에 있는 완전탐색 문제를 Swift로 풀어봤습니다.

 

문제

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예시

[1,2,3,4,5]	[1]
[1,3,2,4,2]	[1,2,3]

Code

func solution(_ answers:[Int]) -> [Int] {
    //1번
    let one = [1, 2, 3, 4, 5]
    let two =  [2, 1, 2, 3, 2, 4, 2, 5]
    let three = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    
    //2번
    var result: [Int : Int] = [1:0, 2:0, 3:0]
    
    //3번
    for (index, element) in answers.enumerated() {
        result[1]! += element == one[(index % one.count)] ? 1 : 0
        result[2]! += element == two[(index % two.count)] ? 1 : 0
        result[3]! += element == three[(index % three.count)] ? 1 : 0
    }
    
    //4번
    return result.filter({
        return ($0.value == result.values.max()) && ($0.value != 0)
    }).keys.sorted()
}

solution([1,3,2,4,2]) //[1,2,3]

해설

1. 수포자가 찍는 방식은 일정 패턴이 반복되기 때문에 수포자의 수 만큼 변수를 생성하고 해당하는 각각의 패턴들을 넣어줬습니다.

 

2. return값이 가장 높은 점수를 받은 수포자의 번호이기 때문에, 수포자의 번호와 맞은 개수를 저장하기 위해  Dictionary를 선언하고 [1:0, 2:0, 3:0]를 넣어줬습니다.

 

3. 가장 중요한 부분인데 앞서 2에서 만들어둔 딕셔너리의 key에 해당하는 1,2,3 을 사용하여 정답이 일치할때마다 해당 키의 value 자리에 값 1을 더해주어 최종 정답 개수를 산출합니다.

산식은 element == one[(index % one.count)] ? 1 : 0

• element는 answers의 1개 항목
• one[(index % one.count)]는 (index % one.count)를 통해 one의 항목 개수만큼 루프를 돌수 있게 만들어줍니다. (one[index] 사용시 range 초과됨)
• 3항 연산자를 사용해 조건이 true면 1, false면 0 return

 

4. result에 조건에 맞는 값만 남겨두고 바로 return 하기 위해 filter 함수를 사용했고, 가장 많이 맞춘 수포자만 남기되 동점자가 있을시 같이 return해야 되기 때문에 $0.value == result.values.max() 를 통해 result내의 가장 큰 값을 가진 키값쌍만을 남겼습니다.

&& $0.value != 0 을 통해 한문제도 못맞은 수포자도 제외시켰습니다.

해당 filter 연산을 통해 남은 Dictionary에서 keys를 통해 key값(수포자 번호)을 추출해서 동점자가 있을시 오름차순 정렬 하라는 조건에 맞게 sorted() 함수를 호출하여 최종적으로 가장 많이 맞은 수포자의 번호가 오름차순으로 정렬되어 return됩니다.