수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/2852

문제 이해 

- 1번 팀과 2번 팀이 농구 경기를 하는데, 48분 동안 각 팀이 이기고 있던 시간을 계산하는 문제다. 

- 필요한 변수로는 score, time, ans가 있는데 score는 각 점수를 기록하는 거라고 이해가 되지만, time과 ans는 약간의 생각이 필요하다. time은 이기고 있는 팀의 이전 시간을 기록하는 딕셔너리이고, ans는 두 팀이 동점인 경우 시간 기록은 다시 리셋되므로 그때까지 팀에서 이기고 있는 시간을 기록하기 위한 용도로 사용한다. 즉, time은 ans를 만들기 위한 수단이라고 이해했다. 

- 한가지 주의해야할 점은 헤맸던 부분이 골을 하나 넣었다고 했을 때 그 팀이 이기는 상황으로 바뀔 수도 있지만, 아닌 경우도 있다. 그래서 이기는 경우를 다른 팀의 점수를 앞질렀을 때부터 시간을 재야 한다. 

    - 그래서 state변수가 필요하다. state가 0인 상황에서는 골을 넣은 팀이 이기는 상황이 되고, 그때 state와 time이 바뀐다. 

    - 만약 state != 0 인 상황에 두 팀의 점수가 동일하게 됐다면 동점인 상황이므로 그때 state는 0이 되고, 그 전까지 이기던 팀의 점수를 카운트(ans[state] += t - time[team]) 해서 기록해야 한다. 

- 그리고 시간 계산하는 것도 별도의 라이브러리를 이용해야하는 줄 알았는데, 그럴 필요 없이 처음부터 초로 계산한 다음에 마지막에 분:초로 출력하면된다. 이렇게 하면 풀이가 훨씬 단순해진다. 

- 까먹으면 안되는게 마지막 48까지 이기고 있는 팀이 있다면 그거까지 한 번 더 계산해줘야지 정답이 뜬다. 

- 그리고 1팀의 이기고 있던 시간과 2팀의 이기고 있던 시간을 순차대로 출력해주면 된다. 

    - ans에 있는 값들은 초 단위 이므로,  60의 몫을 분으로 60의 나머지를 분으로 출력하면 된다. 

    - 다만 시간은 분,초 모두 두자리 수로 표현해야하므로 (1분 30초 같은 경우는 01:30으로 출력) '{:0>2}'를 이용해서 출력하면 된다. 

    - {:0>2} 는 >2와 0으로 분리해 생각할 수 있는데, >2는 왼쪽으로 2칸을 확보하라는 뜻이고 만약 그 두 자리 중에 남는 자리을 때 그 자리를 0으로 채우라는 문법이다. 

정답 풀이 

import sys
input = sys.stdin.readline

n = int(input())
score = {1: 0, 2: 0}
time = {1: 0, 2: 0}
ans = {1: 0, 2: 0}
state = 0  # 0 : even, 1 : team1 leads, 2 : team2 leads


for _ in range(n):
	# 골을 넣은 팀과 시각이 주어진다
    team, t = input().split()
    team = int(team)
    m, s = map(int, t.split(':'))
    t = m * 60 + s
    score[team] += 1

    if state == 0:
        time[team] = t
        state = team
    elif state != 0 and score[1] == score[2]:
        ans[state] += t - time[state]
        state = 0

if state != 0:
    ans[state] += 60 * 48 - time[state]

print('{:0 > 2}:{:0 > 2}'.format(ans[1] // 60, ans[1] % 60))
print('{:0 > 2}:{:0 > 2}'.format(ans[2] // 60, ans[2] % 60))

참고 블로그

https://velog.io/@shin421179/BOJ-2852-NBA-%EB%86%8D%EA%B5%AC

- 문제 : https://www.acmicpc.net/problem/1205

1시간의 시도 끝에 풀었던 문제;; 실버4인데 왜이렇게 어려운지

문제 이해 

- 주어진 노래 점수 리스트(n)에서 새로운 점수(score)를 추가하려고 하는데, 배열의 길이는 최대 p까지만 가능하다. 그래서 len(n) <= p 인 경우에만 연산을 할 수 있다.

- 만약 len(n) < p 라면 그냥 새 점수를 추가하면 되고, len(n) == p라면 다음 조건을 따라야 한다. 

    - n에서 가장 적은 점수를 pop하고, 새 점수(score)를 추가 해야한다. 

    - 단, 새 점수가 가장 적은 점수 초과여야 한다. 아니라면 pop도 못한다. 

- 만약 새 점수를 n에 추가할 수 있는 상황이라면, 각 점수를 정렬한 뒤 새로 추가한 점수인 score의 등수를 구해서 출력하면 된다. 

    - 등수 구하는 것도 주의해야하는데, 같은 점수가 있을 때 해당 점수의 등수는 같은 점수의 가장 마지막 순서 번호가 등수가 된다. 

      예시로 [100, 90, 90, 80] 인 경우 각 점수의 등수는 1, 2, 2, 4가 된다. 

    - 이는 딕셔너리를 이용하면 되는데, 딕셔너리를 점수별로 정렬한 뒤 각 점수의 개수를 세면 된다.

정답 풀이 

from collections import Counter
import sys
input = sys.stdin.readline #이거 해줘야 EOFError 발생 안함

n, score, p = map(int, input().split())

scores = list(map(int, input().split()))
scores.sort(reverse = True)

answer = -1
flag = True
if n <= p:
    if n < p:
        scores.append(score)
    elif n == p :
        if score > scores[-1]:
            scores.pop()
            scores.append(score)
        else:
            flag = False
    
    if flag : 
        temp = Counter(scores)
        result = sorted(temp.items(), key = lambda x : x[0], reverse = True)
        rank = 1
        for x, y in result:
            if x == score:
                answer = rank
                break
            rank += y
            
print(answer)

엄청나게 틀렸던 기록,,

- 문제 : https://www.acmicpc.net/problem/9017

문제 이해 

- 생각보다 조건이 까다로워서 시간이 좀 걸렸던 문제다. 이해한 문제 조건으로는 다음과 같다. 

- 달리는 사람들은 모두 팀에 속해있고, 팀의 총 인원이 6명 미만인 팀은 점수 계산에서 제외된다. 

- 팀의 점수를 산출하는 방식은 상위 4명의 점수를 합하는 것이다. 

- 살아남은 각 팀의 팀원들 중 상위 4명의 점수를 합산해서 가장 적은 점수를 얻은 팀이 우승하게 된다. 

-> 위 조건을 보면 알겠지만, 일단 팀 별로 조건에 맞는 팀원의 수를 구해야 하고, 그 중 팀 수가 6명 미만인 팀은 제외해야 한다. 

-> 이제 각 남은 팀 중에서 상위 4명의 점수를 구한 뒤 정렬해서 우승한 팀을 출력해야 하는 문제다. 

-> 만약 4등까지의 점수 합이 같은 두 팀이 있을 때는 5등의 점수도 비교해야 한다. 

-> 자격을 갖춘 팀을 먼저 구해야하는 것을 간과해 헤맸던 문제다. 

풀이 로직

- 각 입력값을 n과 scores에 입력 받은 뒤, 각 팀의 자격 여부를 확인하기 위해 팀의 인원수를 구해야한다. 

- 각 팀의 인원수는 Counter 라이브러리를 이용해 {팀 번호 : 사람 수 }의 certified 딕셔너리를 만든다 

- 만약 자격이 안되는 팀이라면 {팀 번호 : -1} 처리를 해준다. (딕셔너리에서 빼면 나중에 에러가 발생한다)

- 살아남은 팀들의 점수를 result 딕셔너리({팀 번호 : [점수 배열]})에 저장하는데, 자격이 있는 팀들(딕셔너리 값이 -1이 아닌)의 점수를 배열에 추가한다. scores의 순서대로 점수를 부여하므로 score 변수를 이용하고, 반복문을 하나씩 돌 때마다 + 1해준다. 

- 각 팀에서 4명까지의 점수를 합해서 우승 팀을 가려야 하는데, 여기에서 또 어려운 점이 있다. 

    - 만약 4등까지의 점수 합이 동일한 경우 5등의 점수를 비교해서 더 낮은 팀이 우승 후보가 된다. 

    - 그래서 먼저 4등까지의 점수 합(num_sum)을 구한 뒤 추가로 fifth 변수에 5등의 점수도 추가한다. 

    - 그래서 만약 num_sum과 4등까지의 합이 같은 팀이 있는 경우에는 5등의 점수를 비교하면 된다. 

정답 풀이 

from collections import Counter
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    scores = list(map(int, input().split()))

    certified = Counter(scores)
    for x in certified.keys():
        if certified[x] < 6 : 
            certified[x] = -1
             
    result = {}   # {팀 번호 : [점수 배열]}
    score = 1
    for i in range(len(scores)):
        temp = scores[i]
        if certified[temp] != -1:
            if temp in result:
                result[temp].append(score)
            else:
                result[temp] = [score]
            score += 1

    answer = -1
    fifth = 0
    num_sum = 1e9
    for team, num_arr in result.items():
        if num_sum > sum(num_arr[:4]):
            answer = team
            fifth = num_arr[4]
            num_sum = sum(num_arr[:4])
        elif num_sum == sum(num_arr[:4]):
            if num_arr[4] < fifth:
                answer = team
                fifth = num_arr[4]
                num_sum = sum(num_arr[:4])
    print(answer)

- 문제 : https://www.acmicpc.net/problem/11723

문제 이해 

- 주어진 숫자만큼 주어진 명령어에 맞춰서 진행하면서 명령어가 check일 때 조건에 맞춰서 출력을 하는 문제다.

  1) 명령어가 add, remove, check, toggle의 옆에는 숫자 x가 띄어쓰기로 주어지고 

  2) 명령어가 all, empty인 경우는 숫자 없이 명령어만 주어진다. 

  -> 명령어에 맞춰서도 따로 분리를 해줘야 한다.

- 명령어 add에서 중복된 원소 추가는 안되기에 원소의 중복이 없는 set()을 사용했다. 

- 단계는 Silver5로 문제 자체는 그렇게 어렵지는 않았지만, 생각해야 할 게 꽤 많아서 시도를 많이 했던 문제다.

풀이 로직 

- 주어진 문자열을 temp에 저장하고, 원소가 2개면 command, number를 저장하고 원소가 1개라면 commad만 설정한다. 

- number는 string이므로 이것도 꼭 int()로 변경해줘야지 문제를 안 틀린다. 

- commad의 종류에 따라 각 케이스에 맞춰서 연산을 진행하면 된다.

정답 풀이1

아래 처럼 진행해도 정답이 뜨지만, 주어진 명령어 저장 및 처리가 분리되어있어 시간이 오래 걸리는 것 같다. 

import sys
input = sys.stdin.readline

arr = set()
for _ in range(int(input())):
    temp = input().split()
    if len(temp) == 2:
        command, number = temp[0], temp[1]
        number = int(number)
    else:
        command = temp[0]
    
    if command == 'add':
        arr.add(number)
        
    if command == 'remove':
        if number in arr:
            arr.remove(number)
            
    if command == 'check':
        if number in arr:
            print(1)
        else:
            print(0)
            
    if command == 'toggle':
        if number in arr:
            arr.remove(number)
        else:
            arr.add(number)
    if command == 'all':
        arr = set([i for i in range(1, 21)])
        
    if command == 'empty':
        arr = set()

정답 풀이2

이 풀이로 하면 시간이 좀 더 적게 걸리는데, 명령어가 주어졌을 때 바로 분기문을 명령어에 대한 처리를 하고, set에서 원소 제거시 remove()보다 discard()를 사용하는 점이 달랐다. 내용은 이 블로그를 참고했다.

import sys

m = int(sys.stdin.readline())
S = set()

for _ in range(m):
    temp = sys.stdin.readline().strip().split()
    
    if len(temp) == 1:
        if temp[0] == "all":
            S = set([i for i in range(1, 21)])
        else:
            S = set()
    
    else:
        func, x = temp[0], temp[1]
        x = int(x)

        if func == "add":
            S.add(x)
        elif func == "remove":
            S.discard(x)
        elif func == "check":
            print(1 if x in S else 0)
        elif func == "toggle":
            if x in S:
                S.discard(x)
            else:
                S.add(x)