수학과의 개발자 도전기

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

문제 이해

- arr로 각 인덱스들 앞에 해당 인덱스 값보다 큰 수가 몇 개 있는지에 대한 정보가 주어진다. 

- 이제 그 순서에 맞춰서 숫자를 나열해야하는데, 방법은 다음과 같다. 

  - 작은 수부터 채워나가면 되는데, 큰 사람이 왼쪽에 몇 명 있어야 하는지 주어진 값만큼의 빈자리를 비워두고 다른 값을 채워나간다. 

- 예시로, 2 1 1 0 으로 주어진 경우에 다음과 같은 과정으로 진행 된다. 

  0번 인덱스(1번) : 0 0 1 0 (왼쪽에 두명이 있으므로 2칸을 비워두고 자리를 채운다)

  1번 인덱스(2번) : 0 2 1 0 (2번은 왼쪽에 자기보다 큰 값이 1개이므로)

  2번 인덱스 (3번) : 0 2 1 3

  3번 인덱스 (4번) : 4 2 1 3 

- 주어진 배열 값을 순차적으로 진행하면서, 왼쪽에 0의 값을 센 다음 그 값과 배열 값이 같고, 정답 배열 값도 0이라면 정답 배열에 추가될    수 있다. 이때, 정답 배열에 (해당 인덱스 + 1 값)을 저장하면 된다

정답 풀이 

n = int(input())

arr = list(map(int, input().split()))
answer = [0 for _ in range(n)]

for i in range(n):
    count = 0
    for j in range(n):
        if count == arr[i] and answer[j] == 0:
            answer[j] = i + 1
            break
        elif answer[j] == 0 : # count != arr[i]
            count += 1

print(' '.join(map(str, answer)))

참고 블로그 : https://gudwns1243.tistory.com/31

- 문제 : 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)