pkm7628의 IT공부!

https://school.programmers.co.kr/learn/courses/30/lessons/258712

처음에는 딕셔너리를 만들어 선물을 준 사람과 받은 사람관의 관계를 나타내고, 각 사람의 [준 선물/ 받은 선물 / 선물 지수]를 저장할 딕셔너리를 생성했다.

이후 서로간의 관계에 따라 다음달에 받을 선물을 확인하는 로직을 작성하던 중, 내가 받았을 때와 받지 않았을 때의 관계를 찾는것이 너무 어려웠다.

def solution(friends, gifts):
    answer = {x:0 for x in friends}
    gifts_to_friends = {x:{} for x in friends}
    gifts_count = {x:[0,0,0] for x in friends}
    for i in gifts:
        give, take = i.split()
        gifts_count[take][1] += 1 # 받은 선물 카운팅
        if take in gifts_to_friends[give]:
            gifts_to_friends[give][take] += 1 # 선물 전달 내역 기록
            gifts_count[give][0] += 1 # 준 선물 카운팅
        else:
            gifts_to_friends[give][take] = 1
            gifts_count[give][0] += 1
            
    for name in gifts_count:  #선물 지수 구하기
        gifts_count[name][2] = gifts_count[name][0] - gifts_count[name][1]
            
    print(gifts_to_friends)
    print(gifts_count)
    
    for giving_name in gifts_to_friends:
        for friend in friends:
            if giving_name != friend: #자신인 경우 제외
                if gifts_to_friends[giving_name]: # 내가 선물을 준 사람이 있다면 
                    for taking_name in gifts_to_friends[giving_name]: #여기까지는 ok
                        if giving_name in gifts_to_friends[taking_name]: #상대도 나에게 주었다면
                            if gifts_to_friends[giving_name][taking_name] > gifts_to_friends[taking_name][giving_name]:
                                answer[giving_name]+=1
                            elif gifts_to_friends[giving_name][taking_name] == gifts_to_friends[taking_name][giving_name]:
                                if gifts_count[giving_name][2] > gifts_count[taking_name][2]:
                                    answer[giving_name]+=1
                    
    
    return max(answer.values())

나는 자신인 경우를 제외하였지만, 또 다시 어떤 관계에 대해 계산하는 문제가 있었다.

이 문제는 enumerate를 활용해 index 슬라이싱을 활용해 해결하였다.

관계가 없는 상황을 계산하는 것이 어려웠다. 이 문제는 딕셔너리 메서드 중 .get()메서드를 통해 해결했다.

.get() 메서드는 키를 지정해주고 그 키에대한 값이 있다면 반환해주고, 없다면 특정 값을 지정해 반환할 수 있다.

def solution(friends, gifts):
    answer = {x:0 for x in friends}
    gifts_to_friends = {x:{} for x in friends}
    gifts_count = {x:[0,0,0] for x in friends}
    for i in gifts:
        give, take = i.split()
        gifts_count[take][1] += 1 # 받은 선물 카운팅
        if take in gifts_to_friends[give]:
            gifts_to_friends[give][take] += 1 # 선물 전달 내역 기록
        else:
            gifts_to_friends[give][take] = 1
        gifts_count[give][0] += 1 # 준 선물 카운팅
            
    for name in gifts_count:  #선물 지수 구하기
        gifts_count[name][2] = gifts_count[name][0] - gifts_count[name][1]
            
    # print(gifts_to_friends)
    # print(gifts_count)
    
    for i, giving_name in enumerate(friends):
        for j, taking_name in enumerate(friends[i+1:], i+1): # 나를 제외 / 이전에 확인한 것은 제외
            if giving_name != taking_name:
                give_count = gifts_to_friends[giving_name].get(taking_name, 0) # .get()메서드 / 딕셔너리에서 해당 키의 값이 있다면 반환, 없다면 반환할 값을 지정 가능
                take_count = gifts_to_friends[taking_name].get(giving_name, 0)
                
                if give_count > take_count:
                    answer[giving_name] += 1
                elif give_count < take_count:
                    answer[taking_name] += 1
                else:  # 선물을 주고받은 기록이 없거나 수가 같은 경우
                    if gifts_count[giving_name][2] > gifts_count[taking_name][2]:
                        answer[giving_name] += 1
                    elif gifts_count[giving_name][2] < gifts_count[taking_name][2]:
                        answer[taking_name] += 1
                    
    
    return max(answer.values())

이렇게 해당 문제를 풀이했다.

https://school.programmers.co.kr/learn/courses/30/lessons/340212

이 문제는 간단한 수식을 통해 해결할 수 있을거라 생각했다.

def solution(diffs, times, limit):
    time_prev = [(times[x-1]+times[x]) for x in range(1, len(times))]
    time_prev = [times[0]] + time_prev
    # print(time_prev)
    time = 10**15 + 1
    level = 0
    while (time > limit):
        time = 0
        level += 1
        for i in range(len(diffs)):
            if time > limit:
                break
                
            if diffs[i] <= level:
                time += times[i]
                # print('if문')
                # print(level, time)
            else:
                time += time_prev[i] * (diffs[i] - level) + times[i]
                # print('level :', level)
                # print("else문 itme :", time)
        
        
    return level

다음과 같이 수식을 활용해 풀었으나 시간 초과 오류가 발생했다.

수가 커지면서 너무 많은 반복을 해서 그런거 같다.

반복 횟수를 줄여야 한다는 생각을 하였고 이진 탐색을 통해 횟수를 줄일 수 있다고 생각했다.

Left, Right를 지정해주고 가운데 지점부터 확인하면서 Left, Right를 초기화 해준다.

def solution(diffs, times, limit):
    time_prev = [(times[x-1]+times[x]) for x in range(1, len(times))] # time_prev를 미리 계산
    time_prev = [times[0]] + time_prev # 첫 번째값 대입

    left, right = 1, max(diffs) # 이진 탐색을 위한 index 지정
    while left <= right: # lift > right라면 그 지점이 최초로 time <= limit인 부분
        level = (left + right) // 2 # 중간 지점 확인(정수형)
        time = 0
        for i in range(len(diffs)):
            if time > limit: # 시간초과 발생시 다음 탐색
                break
            
            time += times[i] # 기본적으로 times[i]를 더해주기 때문에 지정 
            if diffs[i] > level: # 숙련도가 낮을 경우 시간 추가
                time += (diffs[i] - level) * time_prev[i]

        if time <= limit: # 시간이 리미트를 넘어서지 않은 경우 오른쪽 지점을 변경
            right = level - 1
        else:
            left = level + 1
    
    return left

https://school.programmers.co.kr/learn/courses/30/lessons/132265?language=python3

이 문제를 처음 접했을 때는 인덱스 슬라이싱을 먼저 떠올렸다.

그래서 for 문을 돌리며 인덱스를 기준으로 left와 right를 자르고 len(), set()을 통하여 포함되어 있는 토핑 갯수를 확인하였다.

그러나 시간초과 문제를 직면하였다.

그 다음에는 deque를 활용해서 큐 자료구조를 활용하였다.

최대한 연산을 줄이고 길이를 나타내는 변수(check, count)를 만들어서 비교하였다.

절반만 맞고, 절반은 시간초과가 떴다.

from collections import deque

def solution(topping):
    answer = 0
    check = len(set(topping))
    count = 0
    dq1 = deque()
    dq2 = deque(topping)

    for i in topping:
        dq2.popleft()
        if (not i in dq1):
            dq1.append(i)
            count += 1

        if (not i in dq2):
            check -= 1
        
        if (count < check):
            continue
        elif (count > check):
            break
        else:
            answer += 1
    return answer
    
topping = [1, 2, 1, 3, 1, 4, 1, 2]

print(solution(topping))

가장 마지막 방식으로는 딕셔너리를 활요해 문제를 풀었다.

확실히 딕셔너리로 풀었을 때 가장 시간이 단축되었다.

문제의 형태에 따라 좋은 방식을 선택한다면 풀이하는 시간을 많이 줄일 수 있다.

주석 부분은 처음에는 사용했지만, 없어도 문제가 풀리기 때문에 주석처리 했다.

처음에 이 코드를 이해하려면 필요하기에 남겨두었다.

def solution(topping):
    answer = 0
    left_dic = {}
    right_dic = {}
    left_len = 0
    right_len = 0

    for d in set(topping):
        right_dic[d] = 0
        right_len += 1
    
    for i in topping:
        right_dic[i] += 1
        
    for j in topping:
        
        if (not j in left_dic):
            left_dic[j] = 0
            left_len += 1
        
        # left_dic[j] += 1
        right_dic[j] -= 1
        
        if right_dic[j] == 0:
            # del right_dic[j]
            right_len -= 1
            
        if (left_len < right_len):
            continue
        elif (left_len > right_len):
            break
        else:
            answer+=1
    
    return answer
    
topping = [1, 2, 1, 3, 1, 4, 1, 2]

print(solution(topping))

https://school.programmers.co.kr/learn/courses/30/lessons/150368

처음 이 문제를 풀이할 때 전체 할인률을 [10, 20, 30, 40]으로 각각 지정하여 플러스 이용자가 가장 많은 할인률을 확인한 뒤, 그 범위 안에서 좁혀 나갈 생각을 하였다.

그러나 문제를 풀이하면서 전체의 결과를 다 확인해야 된다는 것을 확인하였다.

그래서 모든 할인률을 확인하기 위해 중복 순열을 사용하였다.

from itertools import product 

def solution(users, emoticons):
    # users : n명의 구매 기준을 담은 2차원 정수 배열 [비율, 가격]
    # emoticons :m개의 정가를 담은 1차원 정수 배열
    for i in users:
        if i[0]%10 != 0:
            i[0] = ((i[0] // 10) + 1)*10 

    sales = list(product([10, 20, 30, 40], repeat = len(emoticons)))
    
    best_param = [0,0,0] #가장 값이 좋은 plus_user, sum_cost, sales값
    for sale in sales:
        plus_user = 0
        sum_cost = 0
       
        for user in users:
            cost = 0
            for j in range(len(emoticons)):
                if user[0] <= sale[j]:
                    cost += (emoticons[j] * (1-(sale[j] / 100)) )

            if user[1] <= cost:
                plus_user += 1
                cost = 0
            sum_cost += cost
        
        if (best_param[0] < plus_user):
            best_param[0] = plus_user
            best_param[1] = sum_cost
            best_param[2] = sale
        elif(best_param[0] == plus_user):
            if (best_param[1] <= sum_cost):
                best_param[1] = sum_cost
                best_param[2] = sale
    
    answer = [best_param[0], int(best_param[1])]

    return answer

돌아가는 원리를 파악하고 싶다면 아래의 코드를 실행해 보기를 추천한다.

단 원리를 파악할 때 먼저 2명의 users를 확인하길 바란다.

from itertools import product 

def solution(users, emoticons):
    # users : n명의 구매 기준을 담은 2차원 정수 배열 [비율, 가격]
    # emoticons :m개의 정가를 담은 1차원 정수 배열
    for i in users:
        if i[0]%10 != 0:
            i[0] = ((i[0] // 10) + 1)*10 

    sales = list(product([10, 20, 30, 40], repeat = len(emoticons)))
    print(sales)
    
    best_param = [0,0,0] #가장 값이 좋은 plus_user, sum_cost, sales값
    for sale in sales:
        plus_user = 0
        sum_cost = 0
        print('sale =',sale)
        for user in users:
            cost = 0
            for j in range(len(emoticons)):
                if user[0] <= sale[j]:
                    cost += (emoticons[j] * (1-(sale[j] / 100)) )

            print('cost =', cost)
            if user[1] <= cost:
                plus_user += 1
                cost = 0
            sum_cost += cost
        
        if (best_param[0] < plus_user):
            best_param[0] = plus_user
            best_param[1] = sum_cost
            best_param[2] = sale
        elif(best_param[0] == plus_user):
            if (best_param[1] <= sum_cost):
                best_param[1] = sum_cost
                best_param[2] = sale

        print('플러스 이용자 =',plus_user, '최종금액 =',sum_cost)
        print('result =', best_param[0], best_param[1])
        print('='*30)
    
    answer = [best_param[0], int(best_param[1])]
    print('best_param =', best_param[2])
    
    
    return answer

# users = [[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]]
# emoticons = [1300, 1500, 1600, 4900]

users = [[40, 10000], [25, 10000]]
emoticons = [7000, 9000]
print(solution(users, emoticons))

https://school.programmers.co.kr/learn/courses/30/lessons/43165

처음 코드는 다음과 같다.

개인적은 dfs(깊이 우선 탐색) 보다 bfs(너비 우선 탐색)의 방식이 나한테 잘 맞는다고 생각했다.

그러나 이 코드에서는 시간 초과가 떴는데, 문제점을 살펴본 결과 pop(0)의 과정에서 n개의 모든 원소를 확인하여 빼기때문에 시간 복잡도는 O(n)이라고 한다.

만약 depue의 자료형이라면 popleft()을 활용해 O(1)의 시간복잡도로 문제를 풀이할 수 있다.

def solution(numbers, target):
    answer = 0
    q = []
    n = len(numbers)
    q.append([numbers[0],0])
    q.append([-(numbers[0]), 0])
    while q:
        num, index = q.pop(0)
        index += 1
        if index != n:
            q.append([num + numbers[index], index])
            q.append([num - numbers[index], index])
        else:
            if num == target:
                answer += 1
    return answer

from collections import deque를 선언하고

popleft() 함수를 활용해 다음과 같이 수정했다.

from collections import deque
def solution(numbers, target):
    answer = 0
    q = deque()
    n = len(numbers)
    q.append([numbers[0],0])
    q.append([-(numbers[0]), 0])
    while q:
        num, index = q.popleft()
        index += 1
        if index != n:
            q.append([num + numbers[index], index])
            q.append([num - numbers[index], index])
        else:
            if num == target:
                answer += 1
    return answer

수를 n만큼 입력받고 어떠한 수 N으로 나눴을 때 나머지가 모두 동일하다면 N을 출력하는 문제이다.

n = int(input())
L = []
for i in range(n):
    L.append(int(input()))
    
min_num = min(L)

for i in range(1, min_num+1):
    check = [x%i for x in L]
    if check.count(check[0]) == len(check):
        # print(check)
        print(i, end =' ')

생각보다 쉽게 풀이했다

리스트 안에 찾는 수가 있으면 몇 번째에 있는지 출력

없다면 -1 출력하는 문제였다.

try / except 문을 활용하여 풀었다.

n, target = map(int, input().split())
L = list(map(int, input().split()))

try:
    print(L.index(target)+1)
except:
    print(-1)

중앙값에 도달하는지 확인하고 원래 받은 데이터에서 찾아서 출력

n = int(input())  
apart = [] 
check = []

for i in range(n):
    x, y = map(int, input().split())
    apart.append((x, y))      
    check.append(y)

apart.sort()

peple = sum(a[1] for a in apart)
count = 0  


for i in range(n):
    count += apart[i][1] 
    if count >= peple / 2:  
        print(check.index(apart[i][1]) + 1)  
        break

코드해설

n = int(input())  # 아파트 단지 수 입력
apart = []   # 아파트 위치와 거주 인구를 저장할 리스트
check = []

# 아파트 위치와 거주 인구 입력 받기
for i in range(n):
    x, y = map(int, input().split())  # x: 아파트 위치, y: 아파트에 거주하는 사람 수
    apart.append((x, y))         # (위치, 거주 인구) 쌍으로 리스트에 추가
    check.append(y)
# 아파트 위치를 기준으로 정렬 (번호가 작은 아파트를 먼저 고려해야 하므로 위치를 기준으로 정렬)
apart.sort()
print(apart)
# 전체 인구의 절반을 넘는 순간을 찾기 위한 준비
peple = sum(a[1] for a in apart)  # 전체 거주 인구의 합
count = 0  # 누적 인구

# 아파트 단지를 순차적으로 보면서 중앙값에 해당하는 단지 찾기
for i in range(n):
    count += apart[i][1]  # 현재 아파트까지의 누적 인구 수 계산
    if count >= peple / 2:  # 누적 인구가 절반을 넘으면 해당 아파트가 중앙값
        print(check.index(apart[i][1]) + 1)  # 아파트 단지는 1번부터 시작하므로 i+1을 출력
        break

카드를 위 아래로 선택해 하나를 뺐을때 모든 카드를 순서대로 낼 수 있는지 확인하는 문제

n = int(input())
card = list(map(int, input().split()))
count = 1
check = True
while (len(card) > 0):
    if(card[0] == count):
        card.pop(0)
    elif(card[-1] == count):
        card.pop()
    else:
        check = False
        break
    
if check:
    print('YES')
else:
    print('NO')

이렇게 풀이했는데 완전히 연속되는 숫자가 아닌지 실패했다.

n = int(input())
card = list(map(int, input().split()))

check = True
while (len(card) > 0):
    if(card[0] == min(card)):
        card.pop(0)
    elif(card[-1] == min(card)):
        card.pop()
    else:
        check = False
        break
    
if check:
    print('YES')
else:
    print('NO')

가장 작은 카드를 비교하는거로 해결했다.

처음 n(인원수)를 입력받고

이름과, iq를 입력받는다.

iq가 높은순으로 3명 출력한다. 단, iq가 같으면 먼저 측정한 사람을 출력한다.

dict을 활용해서 풀려했지만 잘 되지 않아 리스트의 index를 찾아 해결하였다.

<망한코드>

n = int(input())
L = []
for i in range(n):
    L.append(list(input().split()))
    
    
dict_L = dict(L)
print('dict_L', dict_L)
sorted_dict = sorted(dict_L.items(), key = lambda a : a[1] , reverse = True)
print('sorted_dict', sorted_dict)

for i in range(3):
    print(list(sorted_dict[i])[0])

<문제 해결>

n = int(input())
L = []
name = []
iq = []
for i in range(n):
    a, b = input().split()
    name.append(a)
    iq.append(int(b))

for i in range(3):
    max_index = iq.index(max(iq))
    print(name[max_index])
    name.pop(max_index)
    iq.pop(max_index)