[백준/Swift] 1946 : 신입 사원

 

 

• BOJ_1946.swift

• 1946 : 신입 사원/ 문제 소개
• 풀이 과정
• 코드 구현

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

1946 :  신입 사원 / 문제 소개

 

진영 주식회사에서 신입사원을 뽑는다.

지원자는 N명이고

각 지원자 마다 서류심사 성적, 면접 시험 성적이 주어진다.

 

신입사원 채용 은 최대한 많이 하려고한다.

어떤 지원자 A의 성적이 다른 지원자 B의 성적(서류, 면접) 중 하나가 높거나 둘다 높다면 채용된다.

즉 A지원자가 B원자의 (서류, 면접) 둘 다 낮을 경우 A지원자는 탈락이다.

풀이 과정

 

맨 처음에 이 문제를 풀 때 어떻게 하면 Greedy적으로 풀어나갈 수 있을까 생각했다.

이 문제를 풀기 전에 유명한 회의실 배정 문제를 풀었는데 주어진 입력값은 동일하나 문제가 달라지니 이게 Greedy인가? 잠~시 당황했지만 부분적으로 Greedy조건을 선택해 나가면 될 것이라 생각했다.

우선 사용자의 채용정보는

2개의 튜플로 된 list에 저장했다. 

이때 타입은 (document: Int, interview : Int) 타입으로하는 Element를 정의해 주었다.

list에 담긴 지원자의 interview가 1등인 지원자부터 소팅을 해주었다.

list.sort(by: )
{
	return $0.interview < $1.interview
}

그럴 경우 list 의 index 0부터 끝까지 우선 list의 0번째 지원자의 interview성적이 가장 높다. 근데 여기서 채용 조건을 보면 둘중 하나라도 높으면 합격이기에 document(서류)가 list[0] 번째 지원자의 서류보다 등수가 높으면 된다.

 

여기서 등수가 높다는거,, 1등은  1. 2등은 2. 3등은 3. 이런식이다.

 

그 예로

list[0]의 지원자는

4 1

list[1]의 지원자는 

3 2

이다. 오른쪽 인터뷰 성적만 보면 채용 실패가 맞지만 왼쪽 서류 성적을 봤을 때 list[0]지원자보다 높은 점수를 받았음으로 list[1]지원자는 햅격~~이다.

list[2]의 지원자는

2 3

이다. 마찬가지로 오른쪽 인터뷰성적만 보면 채용 실패가 맞지만 왼쪽 서류 성적을 봤을 때 list[1]지원자 보다 높은 점수를 받았음으로 list[2]지원자는 햅격~이다.

list[3] 

5 5로 가정한다면

list[2]지원자보다 서류, 인터뷰 점수가 낮기에 list[3]지원자는 불합격이다 ㅠ

 

한가지 주의할 점은

흠.. 한 3번정도 코드를 줄여가면서, 포문을 줄여가면서? 문제를 풀었는데 아무리 맞는 로직 인데도 자꾸 시간초과가 났다.

입출력이 느려서 그렇다.

라이노 님의 fileIO를 써야한다

이때 커멘드창에 입력을 붙여넣을 경우!! EOF를 눌러줘야 동작된다 EOF는 컨트롤 + d 이다.

백준 스위프트 좀 잘좀 대우해줘요ㅠㅠ... swift가 곧세상을지배핳건데

코드 구현

 

import Foundation

typealias Element = (document: Int, interview : Int)


final class FileIO {
    private var buffer:[UInt8]
    private var index: Int
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
        index = 0
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer.withUnsafeBufferPointer { $0[index] }
    }
    
    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true
        
        while now == 10
                || now == 32 { now = read() }
        if now == 45{ isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }
        
        return sum * (isPositive ? 1:-1)
    }
    
    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()
        
        while now == 10
                || now == 32 { now = read() }
        
        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }
        
        return str
    }
}

func BOJ_1946()
{
    let file  = FileIO()
    var res = ""
    
    for _ in 0..<file.readInt()
    {
        var list  = [Element]()
        var pass  = 0
        var count = 1
        for _ in 0..<file.readInt()
        {
            list.append((file.readInt(),file.readInt()))
        }
        
        list.sort(by: )
        {
            return $0.interview < $1.interview
        }
        pass = list[0].document
        
        for i in 1..<list.count
        {
            if pass > list[i].document
            {
                pass = list[i].document
                count += 1
            }
        }
        res += "\(count)\n"
    }
    print(res)
}
BOJ_1946()

 

visit my github