[SV 8주차] 문자 인식, 전화번호 목록, 시간 관리하기

문제

동혁이는 새로운 이미지 문자 인식 프로그램을 만들었다. 이 프로그램은 종이에 쓰여 있는 글자를 스캔한 뒤, 텍스트 파일로 저장한다. 동혁이는 밤을 새며 열심히 프로그램을 만들었지만, 프로그램의 신뢰도는 100%가 아니며, 어떤 글자는 인식하지 못했다. 결국 동혁이는 100%가 아니라는 점에서 실망하였고, 대전으로 도망가게 되었다.

대전으로 도망가버린 동혁이를 대신해서, 동혁이가 만든 이미지 문자 인식 프로그램의 인식률을 계산하는 프로그램을 작성하시오.

인식률은 인식한 문자의 수를 R, 전체 문자의 수를 A라고 했을 때, R/A이다. 줄바꿈 문자는 문자로 세지 않는다.

입력

입력은 N개의 테스트 케이스로 구성되어 있다. 첫째 줄에 테스트 케이스의 개수 N이 주어진다. 각 테스트 케이스는 적어도 한 줄이고, 인식하지 못한 문자는 '#'로 표시한다. 각 테스트 케이스의 다음에는 빈 줄이 한 칸씩 있다. 각 줄은 100글자를 넘지 않고, 줄의 수도 200줄을 넘지 않는다.

 

 

import sys

N = int(sys.stdin.readline())

for _ in range(N):
    R, A = 0, 0
    
    while True:
        line = sys.stdin.readline().rstrip()

        if line == '':
            break
        
        for char in line:
            if char == '#':
                A += 1
            else:
                A += 1
                R += 1
    
    ratio = round(R / A * 100, 1)

    if str(ratio).split('.')[-1] == '0':
        ratio = int(ratio)

    print(f'Efficiency ratio is {ratio}%.')

 

1. sys 모듈을 가져온다.

2. 첫 줄에서 테스트 케이스 개수 N을 읽는다. ( sys.stdin.readline()은 문자열을 반환하므로 int()로 정수로 변환한다. )

3. R은 인식된 글자수, A는 전체 글자수이다. 이 둘은 테스트 케이스마다 초기화된다.

4. while True는 각 테스트 케이스의 여러 줄을 처리하기 위한 무한 루프이다. 

5. 한 줄 읽어서 line에 저장한다.  rstrip()은 오른쪽 끝 \n 제거한다.

6. 빈 줄(" ")이면 현재 테스트 케이스는 종료된다. 

7. 현재 줄의 문자 하나씩 다음을 반복한다. 

8. 현재 문자가 #이면 인식 실패한 것이므로 전체 글자 수 A만 1 증가한다.

9. 그렇지 않으면 인식 성공한 것이므로 전체 글자 수 A가 1 증가하고, 인식된 글자 수 R도 1 증가한다.

10. 인식률을 계산하기 위해 R / A * 100을 하고 round(..., 1)은 소수점 첫째 자리 반올림하므로 이를 ratio에 저장한다.

11. 만일 소수점이 .0 이면 정수로 변환해서 출력할 때 불필요한 .0을 제거한다.

12. 문제 요구사항에 맞게 Efficiency ratio is ( ) % 형식으로 출력한다.

( 코드에서 앞에 f는 f-string을 만들기 위해 붙이는 접두사이다. 문자열 안에 { }를 쓰고 그 안에 변수나 표현식을 넣으면

실시간으로 값이 문자열에 들어간다. )

 

 

---

 

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    numbers = [input().strip() for _ in range(n)]
    numbers.sort()
    consistent = True
    for i in range(n - 1):
        if numbers[i+1].startswith(numbers[i]):
           consistent = False
           break
    print("YES" if consistent else "NO")

 

1. sys 모듈을 불러온다. ( 입력을 빠르게 받기 위해서 사용하는 것)

2. 파이썬의 기본 함수인 input() 보다 빠른 입력 함수인 sys()를 input 이름으로 재할당한다. ( 많은 입력을 처리할 때 속도 중요)

3. 테스트 케이스 개수를 정수로 변환해서  t에 저장한다.

4. 각 테스트 케이스에서 다음과 같이 반복한다. (변수를 사용하지 않으므로 _를 씀)

5. 해당 테스트 케이스의 전화번호 개수를 정수로 변환하여 n에 저장한다.

6. n줄을 읽어 리스트에 저장한다. 이때 strip()은 줄 끝의 \n을 제거해 순수한 번호 문자열만 남기는 역할을 한다.

7. 전화번호들을 문자열 순으로 정렬한다. 이렇게 하면 같은 접두사를 가진 문자열들이 인접하게 된다.

8. 일관성(consistent) 여부를 True로 일단 표기한다.

9. 인접한 쌍을 비교하기 위해서 0부터 n-2까지 다음을 반복한다.

10. 바로 다음 번호가 현재 번호의 접두사인지 확인한다. startswitch가 True이면 numbers[i]가 numbers[i+1]의 접두사인것이다. 

      따라서 일관성은 False라고 하고 반복을 종료한다.

11. 일관성이 참이면 Yes를 출력하고 그렇지 않으면 No를 출력한다.

 

* "문자열".startswith("접두사") 형식으로 사용. 결과는 True 또는 False

 

 

---

문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다. 

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

 

입력

첫 줄에는 일의 개수인 N을 받고

두 번째 줄부터 N+1줄까지 T_i와 S_i를 입력받는다. 

 

 

import sys
input = sys.stdin.readline

N = int(input())
tasks = []
for _ in range(N):
    T, S = map(int, input().split())
    tasks.append((S, T))

tasks.sort()

current_time = tasks[-1][0]  # 제일 늦은 데드라인부터 시작
for S, T in reversed(tasks):
    current_time = min(current_time, S) - T

print(current_time if current_time >= 0 else -1)

 

1. 표준 입력을 빠르게 읽기 위해 sys 모듈을 불러온다.

2. 기본 input()보다 빠른 입력 함수로 input을 재지정한다. (많은 입력을 처리할 때 속도 향상을 위함)

3. 할 일의 개수를 읽어 정수로 변환하여 N에 저장한다.

4. (데드라인, 소요 시간) 쌍을 저장할 빈 리스트를 만든다.

5. 다음을 N번 반복한다.

6. 한 줄에서 걸리는 시간과 데드라인을 정수로 읽어서 T, S에 저장한다.

7. (데드라인, 시간) 형태로 튜플을 만들어 tasks에 추가한다. ( tasks.sort()  했을 때 자동으로 데드라인 기준으로 정렬되게 하기 위함)

8. 데드라인을 오름차순으로 정리한다. 그러면 데드라인이 빠른 작업부터 나열된다.

9. 가장 늦은 작업의 데드라인을 현재 시작 가능 시간의 초기값으로 설정한다.

10. 데드라인이 큰 작업부터 작은 작업 순으로 역순 반복한다. 그러면 각 작업을 가능한 한 늦게 시작하도록 뒤에서부터 고정할 수 있다.

11. 각 작업은 최대 S시점까지 끝나야 하므로, 현재 확보된 current_time과 S 중 더 이른 시점을 기준으로 잡는다.

     그 작업을 끝내기 위해 작업 시간이 T만큼 앞당겨야 하므로 -T를 해주어 그 작업의 시작 시점을 지정한다.

12. 최종적으로 얻은 current_time이 0이상이면 그 값( 존이 가장 늦게 일어날 수 있는 시간)을 출력한다. 

      음수이면 모든 일을 제 시간에 마칠 수 없다는 뜻이므로 -1을 출력한다.