데이터 엔지니어링

1.문제 소개

• 구현/문자열 문제유형이다.
• https://www.acmicpc.net/problem/2852

2.코드

# Main Idea
# 1) 입력 테스트 케이스의 데이트 문자열 타입을 처리하기 편한 초 단위로 변환
# 2) 점수를 낸 로그를 반복문으로 돌면서, 점수를 낸 직전 스코어의 승자 팀이 있는 경우 1팀과 2팀의 이긴 시간을 누적 저장
# 3) 마지막에는 승팀의 존재 여부를 확인하고, 이긴 시간을 추가 보정

# 입력 데이터 파싱
def set_test_case():
    n = int(input())
    score_log = []
    for i in range(n):
        input_str= input().split(" ")
        team = int(input_str[0])
        score_time_str = input_str[1].split(":")
        minutes = int(score_time_str[0])
        seconds = int(score_time_str[1])

        total_seconds = minutes * 60 + seconds
        score_log += [[team,total_seconds]]

    return score_log
def get_winner(a_score,b_score):
    return 0 if a_score > b_score else 1

def get_format_answer(seconds):
    minutes = seconds //60
    seconds = seconds % 60
    return f"{minutes:02d}:{seconds:02d}"
def solution():
    score_log  = set_test_case()
    current_score = [0,0] # 1, 2팀의 누적 점수
    last_winner = -1
    answer = [0,0] # 1,2 팀의 정답출력을 위한 리스트

    for idx,t in enumerate(score_log):

        # 이전 스코어가 동점이 아닌경우 계산
        if current_score[0] != current_score[1] :
            last_winner = get_winner(current_score[0], current_score[1])
            answer[last_winner] += t[1]-score_log[idx-1][1]

        # 누적 점수 저장
        if t[0] == 1:
            current_score[0] +=1
        else:
            current_score[1] +=1

    if current_score[0] != current_score[1]:
        last_winner = get_winner(current_score[0], current_score[1])
        answer[last_winner] += 60*48 - score_log[-1][1]

    print(get_format_answer(answer[0]))
    print(get_format_answer(answer[1]))

if __name__=='__main__':
    solution()

1.문제 소개

• 구현/그리디 문제유형이다.
• https://www.acmicpc.net/problem/1138

2.코드

# Main Idea :
# 	- 정답을 편하게 구하기 위해 자료구조를 만든다
# 		(lt,height)
# 		* lt = 왼쪽 방향으로 키가 큰 사람 수 
# 		* height = 키 
# 	- lt,height 순서로 정렬 한다.
# 	- 정답 배열을 만든다
# 	- 정답 배열에 lt 조건 대로 height 를 저장한다
# 	- lt 조건에 맞는지 체크하면서, 정답 배열에 들어갈 위치(cursor)를 구한다.
# 	- 정답 배열에 원소 추가
# 		- 위치(cursor) 기준으로 오른쪽 배열 복제.
# 		- 정답배열 위치(cursor)에 원소를 추가하고 + 오른 쪽 배열 복제본 복사 

def set_test_case():
    n = int(input())
    input_str = input().split(" ")
    arr = []
    input_str = list(map(int,input_str))
    for i,v in enumerate(input_str):
        arr += [(v,(i+1))]

    return arr

def solution():
    # 테스트 케이스 입력
    arr = set_test_case()

    # 왼쪽 방향 자기보다 키 큰 사람의 수 기준으로 정렬
    sorted_arr = sorted(arr, key=lambda x: x[1], reverse=True)
    # 키 큰 사람의 수가 동일할 경우 키가 큰 사람 기준으로 내림 차순 정렬
    sorted_arr = sorted(sorted_arr, key=lambda x: x[0], reverse=False)
    # 정답 배열 선언
    answer = [0] * len(sorted_arr)


    for item in sorted_arr:
        cursor = 0
        height = item[1]
        cnt = item[0]
        #lt 조건에 맞는지 체크하면서, 정답 배열에 들어갈 위치(cursor)를 찾음
        while cursor < len(arr) and answer[cursor] > 0 and cnt > 0 :
            if answer[cursor] > height :
                cnt -=1
            cursor += 1
        # 정답 배열에 원소 추가
        right_part = answer[cursor:-1]
        answer[cursor] = height
        answer[cursor+1:] = right_part

    # 정답 출력
    answer = list(map(str,answer))
    print(" ".join(answer))


if __name__ == '__main__':
    solution()

3.코멘트

• 단순히 입력 케이스 배열에서 규칙을 찾아 정답을 구할 수 있는 방법으로 접근하려면 더 어렵다. 유형대로 그리디하게 풀어야 한다.
• 그 동안 서로 많이 바빠서 4개월만에 알고리즘 스터디원들이 모여 재미있게 진행했다.
• 앞으로는 조금 더 자주 볼 수 있기를 기대한다.