1713번: 후보 추천하기

 

1713번: 후보 추천하기

 

 

후보 추천하기

 

문제

월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

입력

첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

출력

사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.

예제 입력 1 

3
9
2 1 4 3 5 6 2 7 2

예제 출력 1 

2 6 7

 

 

---

풀이

 

 

먼저 문제를 이해해보자.

 

• 사진틀의 개수 N
• 추천 받은 학생은 순서대로 사진틀에 들어가야 한다.
• 사진틀이 꽉 찼다면, 추천받은 횟수가 가장 적은 학생을 삭제하거나 횟수가 같은 학생이 둘 이상이면 가장 오래 사진틀에 있었던 학생을 삭제한다.
• 삭제된 학생의 추천 횟수는 0으로 초기화된다.
• 결과적으로 사진틀에 남아있는 학생을 출력해라.

 

처음 내 생각

 

횟수를 체크하는 배열을 따로 만들고 queue를 사진틀으로 두어 판단하려고 했다.

queue가 N+1크기이면 사진틀이 꽉 찬상태에서 학생이 들어온거니, 그 때 삭제조건에 따라 학생을 삭제하려고 했다.

 

하지만 다음과 같은 예외사항에 오류가 나온다.

 

3
8
1 1 1 2 2 3 3 4

 

let N = Int(readLine()!)!
let recommedCnt = Int(readLine()!)!

var queue: [Int] = []
var cnt = [Int](repeating: 0, count: recommedCnt+1)

let input = readLine()!.split(separator: " ").map{Int(String($0))!}

for i in 0..<input.count{
    
    if queue.count == N+1{
        let removeQ = queue.remove(at: cnt.min()!)
        cnt[removeQ] = 0
    }
    
    queue.append(input[i])
    cnt[input[i]] += 1
}

let result = Set(queue).sorted()

for i in 0..<result.count{
    print(result[i], terminator: " ")
}

 

 

답은 1 3 4가 나와야 하는데 2 3 4가 나오는 것을 확인할 수 있다.

 

코드는 다음과 같은 문제점이 있다.

 

• queue의 크기가 N+1일 때 삭제
• queue에 이미 존재하는 값인데 중복으로 들어간다.

 

---

설계

 

 

사진틀은 정해져있고, 입력받은 추천 학생을 사진틀에 넣고 삭제조건에 따라 삭제하며 최종적으로 사진틀에 남은 학생을 구하면 된다.

 

삭제조건은 두 가지이다.

사진틀이 학생으로 다 찼다면

 

• 추천횟수가 가장 적은 학생을 삭제
• 추천횟수가 같은 학생이 두명이상일 때, 사진틀에 가장 오래있었던 학생을 삭제

 

추천횟수 판단하고 가장 오래된 학생을 찾아야하는 것이 관건이다.

 

1️⃣ 추천횟수 판단

 

문제에서 1<=학생<=100으로 주어져 있어 cnt[101] 배열을 만들어 횟수를 판단하는 데 사용하였다.

 

2️⃣ 가장 오래된 학생

 

queue를 통해 가장 오래된 학생 = 처음에 있는 값으로 판단하였다.

 

 

---

 

구현

 

• cnt[]로 추천 횟수 판별
• queue로 사진틀 구현
• 삭제조건으로 queue.count == N일 때, 조건에 맞는 값 삭제 

 

 

 

 

 

---

 

전체코드

 

 

let N = Int(readLine()!)!
let recommedCnt = Int(readLine()!)!

var queue: [Int] = []
var cnt = [Int](repeating: 0, count: 101)

let input = readLine()!.split(separator: " ").map { Int(String($0))! }

for i in 0..<input.count {
    let student = input[i]
    cnt[student] += 1
    
    if queue.contains(student) {
        continue
    }

    if queue.count == N {
        var minIndex = 0
        for j in 1..<queue.count {
            if cnt[queue[j]] < cnt[queue[minIndex]]{
                minIndex = j
            }
        }

        let removeStudent = queue.remove(at: minIndex)
        cnt[removeStudent] = 0
    }

    queue.append(student)
}

let result = Set(queue).sorted()

for value in result {
    print(value, terminator: " ")
}