미야's Day

*내가 작성한 코드 

def solution(today, terms, privacies):
    answer = []
    today_year = int(today[:4])
    today_month = int(today[5:7])
    today_day = int(today[-2:])

    term_x = []
    for i in range(len(terms)):
        term_x.append(terms[i].split())

    privacie_x = []
    for i in range(len(privacies)):
        privacie_x.append(privacies[i].split())

    for index, i in enumerate(privacie_x):
        m = 0
        privacies_year = 0
        privacies_month = 0
        privacies_day = 0
        for j in term_x:
            if i[1] == j[0]:
                m = int(i[0][5:7]) + int(j[1])
                privacies_year = int(i[0][:4]) + (m // 12)
                privacies_month = m % 12
                privacies_day = int(i[0][-2:])
        if today_year == privacies_year and today_month == privacies_month and today_day == privacies_day:
            answer.append(index + 1)
        else:
            if today_year > privacies_year:
                answer.append(index + 1)
            elif today_year == privacies_year:
                if today_month > privacies_month:
                    answer.append(index + 1)
                elif today_month == privacies_month:
                    if today_day > privacies_day:
                        answer.append(index + 1)

    return answer
print(solution("2021.12.08", ["A 18"], ["2020.06.08 A"]))

결과 -> 1번, 17번 시간 초과

*정답 코드

def solution(players, callings):
  
    play_dict = dict()
    
    for index, name in enumerate(players):
        play_dict[name] = index
        
    for player in callings:
        idx = play_dict[player]
        front = players[idx - 1]
        
        play_dict[player] = idx - 1
        play_dict[front] = idx
        
        players[idx - 1] = player
        players[idx] = front
        
        
    return players

*깨달은 점: 시간 절약에는 dict() 를 활용하자! 딕셔너리 !!!!!!!

문제: 프로그래머스 PCCE기출문제 10번 데이터 분석

def solution(data, ext, val_ext, sort_by):
    answer = [[]]
    a = []
    sort = ["code", "date", "maximum", "remain"]
    for i in range(len(data)):
        for index, c in enumerate(sort):
            if ext == c:
                if data[i][index] < val_ext:
                    a.append(data[i])
    for num, s in enumerate(sort):
        if s == sort_by:
            answer = sorted(a, key=lambda x:x[num])


    return answer

sorted(a, key=lambda x:x[num]) 

-> 배열a에서 원소x의 x[num]번째 원소를 기준으로 오름차순 정렬한 결과를 반환한다. 

*처음 enumerate() 함수 쓰지 않고 푼 내 코드

def solution(board, moves):
    answer = 0
    bag = []
    for i in moves:
        for j in range(len(board)):
            if board[j][i-1] != 0:
                if bag and bag[-1] == board[j][i-1]:
                    del bag[-1]
                    answer += 2
                else:
                    bag.append(board[j][i-1])
                board[j][i-1] = 0
                break 

    return answer

* enumerate() 함수 사용한 코드

def solution(board, moves):
    answer = 0
    bag = []
    for i in moves:
        for index, j in enumerate(board):
            if j[i-1] != 0:
                if bag and bag[-1] == j[i-1]:
                    del bag[-1]
                    answer += 2
                else:
                    bag.append(j[i-1])
                board[index][i-1] = 0
                break 
    return answer

이 문제를 풀면서 정말 많은 시도를 했던 문제였다...

처음에는 14번부터 테케가 통과가 안되더니

다시 수정후, 17번 테케만 유독 안되었다...

그렇게 방법을 찾던 중, 질문하기에 누군가가 17번 테케를 남겨놓은 댓글을 보았고,

해당 테케를 추가했더니 딱 그 테케에서 오류가 났다!

이 부분에 대한 원인을 찾아서 수정하고 나니 통과할 수 있었다. 후후....

혹시나 저처럼 17번 테스트케이스에서 계속 틀리는 분들을 위하여 포스팅을 남겨놓겠슴다..

문제설명:

제한사항:

나의 풀이:

저는 이렇게 풀었다 정도로만 생각해주세요...ㅎㅎ

def solution(keymap, targets):
    answer = [0] * len(targets)
    key_count = 0
    
    for word in range(len(targets)):
        for i in targets[word]:
            key_count = 0
            for key in keymap:
                if i in key:
                    if key_count != 0:
                        if key_count >= key.index(i) + 1:
                            key_count = key.index(i) + 1
                    else:
                        key_count = key.index(i) + 1          
                else:
                    continue 
            if key_count == 0:
                answer[word] = -1
            else:
                if answer[word] != -1:
                    answer[word] += key_count
    

    return answer

추가한 테스트케이스:

오류났던 원인?

오류가 발생했던 코드는 첫문장 for word in range(len(targets)) -> for word in targets로 설정하여 answer에 index값을 word에 해당하는 인덱스로 지정하여 값을 넣어주었더니

위와 같이 targets의 원소가 같을 경우 항상 첫번째 인덱스에 값을 넣어주어 [27, 0, 0]으로 값이 나와 오류가 났던 것이었다.

내 코드)

from fractions import Fraction
def solution(N, stages):
    answer = []
    success = []
    cnt = 0
    for i in range(1, N + 1):
        if i in stages:
            a = stages.count(i)
            b = len(stages) - cnt 
            cnt += a 
            success.append([i, float(Fraction(a, b))])
        if i not in stages:
            success.append([i, 0])
    success.sort(key = lambda x : (-x[1], x[0]))  #x[1]은 내림차순, 같은 값일 경우 x[0] 오름차순 정렬
                
    for i in range(N):
        answer.append(success[i][0])    
    return answer

*오늘의 배움!

ⓐ리스트.sort(key = lambda x : ( -x[1] , x[0]))  

>> 앞에 -1을 붙이면 reverse=True 역순을 의미함. 즉, x[1]키를 기준으로 역순으로 정렬하고, x[1]이 같은 값일 경우 x[0]을 기준으로 정렬한다. 

ⓑ리스트.sort(key = lambda x : -x[1])

>> 같은 값이 없거나 계산할 필요 없을 경우 이런식으로 조건 하나만 써줘도 됨.

ⓒsorted(리스트, key= len) 

>> 이런식으로 sorted로 계산해줘도 된다.

프로그래머스 level1. 소수찾기 

원래 풀이대로 하면 시간 초과가 되었다. n의 조건이 2<= n <= 1000000이므로 이 문제는 에라토스테네스의 체를 이용하여 구해야 한다. 

풀이방법:

def solution(n):
    answer = 0
    #에라토스테네스의 체 
    a = [False, False] + [True]*(n-1)   #0,1을 제외한 모든 수를 소수라고 지정 
    primes = []
    
    for i in range(2, n+1):
        if a[i] == True:
            primes.append(i)
            answer += 1
            for j in range(2*i, n+1, i):     #i의 배수 모두 삭제 
                a[j] = False
                
    return answer

프로그래머스 level1. 기사단원의 무기 (약수)

이 문제 또한 약수의 개수를 구하는 문제인데, 루트를 사용하여 시간 복잡도를 줄이는 방향으로 문제를 풀어줘야 한다.

def solution(number, limit, power):
    answer = 0
    prime = [0] * number
    for i in range(1, number+1):
        for j in range(1, int(i**(1/2))+1):
            if i % j == 0:
                prime[i-1] += 1
                if (j**2) != i:
                    prime[i-1] += 1
        if prime[i-1] > limit:
            prime[i-1] = power
    answer = sum(prime)
        
    return answer

처음으로 시간 복잡도를 활용해서 문제를 풀어야 통과가 되는 경험을 하면서 이전보다 문제를 풀이할 때 시간 복잡도를 고려한 방식으로 생각하게 되는 계기가 된 문제들이었다. 

이 문제는 구현 유형 중에 하나인데, 풀이 방법은 여러가지가 있는 것 같다.

후보 수 N명이 주어지고, 각 후보자에 대한 지지하는 사람 수가 주어진다.

그 중 1번 후보자를 지지하는 사람 수가 가장 많아지도록 다른 후보자 지지자 수에서 한 번씩 빼와서 더할 때마다 카운트를 하여 최댓값을 만들 수 있는 카운트의 최솟값을 구하는 문제다.

-나의 풀이 방법:

import sys
input = sys.stdin.readline

n = int(input())    #후보자 수
people = []    #후보자를 지지하는 사람 수를 담을 리스트 
cnt = 0    #연산 횟수 
for _ in range(n):    #각 후보자를 지지하는 사람 수를 입력받아 people리스트에 넣는다. 
    people.append(int(input()))  

while True:
    if people[0] == max(people):    #1번 후보자(people[0]) 지지자 수가 가장 큰 수일때
        for i in range(1, len(people)):    #1번 후보자 외의 후보자 지지자 수를 비교하여 
            if people[i] == people[0]:     #1번 후보자 지지자 수와 동일한 후보자가 있을 때
                cnt += 1          #연산 한 번 수행 후 종료 
                break
        break
    else:                #1번 후보자 지지자 수가 가장 큰 수가 아닐 때
        people[people.index(max(people))] -= 1      #가장 많은 지지자 수를 1감소
        people[0] += 1           #1번 후보자 지지자 수 1증가
        cnt += 1      #연산 1회 증가 
        if max(people) == people[0]:      #1번 후보자 지지자 수가 가장 큰 수가 됬을 때 종료
            for i in range(1, len(people)):    #다른 후보자 지지자 수 중 같은 값이 있을 시
                if people[i] == people[0]:
                    cnt += 1            #연산 1회 증가 후 중료 
                    break
            break
print(cnt)                 #cnt연산값 출력

아직은 if문과 for문을 많이 쓰는 방법으로 구현하고 있다.....ㅎㅎ

이 방법이 시간 복잡도 면에서 좋지 않은 방법이라고 해서 다른 사람들 코드를 보며 계속 공부해야 할 것 같다.

내 생각에 파이썬으로 계속 알고리즘을 풀어본 결과, 내장 함수나 문법을 많이 알고 있을수록 더 효율적이고 시간을 절약할 수 있는 코드를 작성할 수 있는 것 같다. 결국엔 지식의 중요성.....?!!

이와 같이 생각한 이유는 밑에 다른 사람의 코드를 보면 이해할 수 있다. 

하지만 이렇게 손코딩으로 1부터 10까지 직접 풀어보며 원리를 이해해나가는 것도 지금 단계에서는 중요하다고 생각한다.

-다른 사람 풀이

import heapq

n = int(input())

hq = []
for i in range(n):
    votes = int(input())
    if i == 0:
        dasom_votes = votes
        continue

    heapq.heappush(hq, -votes)

bribe_count = 0
while hq:
    votes = -heapq.heappop(hq)
    if votes < dasom_votes:
        break

    dasom_votes += 1
    bribe_count += 1
    heapq.heappush(hq, -(votes - 1))

print(bribe_count)

이 분은 파이썬 표준 라이브러리 중 하나인 힙을 이용해서 구현해냈다. 정말 다른 분들 코드를 볼 수록 대단한 분들이 많은 것 같다...ㅎㅎ 나도 열심히 공부해서 나중엔 한 줄로 알고리즘을 풀 수 있는...날이 오길...ㅎㅎ?