10825, 18310, 1715 (백준) 42289(프로그래머스)

10825 국영수

📌문제 링크
https://www.acmicpc.net/problem/10825

💡 문제 풀이
파이썬 sort함수에 key와 lambda를 이용해 요소별로 접근할 수 있었던 것을 기억했다

좋은 예시가 있어 아래에 사진 첨부

나는 grade.sort(key=lambda x : (-x[1],x[2],-x[3],x[0]))와 같이 문제에서 제시한 조건에 맞게 요소별 오름,내림차순을 설정해주어 풀이하였다

📋코드

import sys
input = sys.stdin.readline
grade = []

#입력받기
N = int(input())
for _ in range(N):
    name, kor, eng, math = input().split()
    grade.append((name, int(kor), int(eng), int(math)))
    
    
grade.sort(key=lambda x : (-x[1],x[2],-x[3],x[0]))
for _ in range(N):
    print(grade[_][0])

18310 안테나

📌문제 링크
https://www.acmicpc.net/problem/18310

💡 문제 풀이
문제를 보고 처음엔 정렬한 후에 이분탐색으로 푸는것인줄 알았다
하지만 코드를 구현하며 언제 왼쪽, 오른쪽으로 갈지 기준이 애매하다는 것을 알고 for문을 통해 최소 값을 구현하여 풀었지만 역시나 시간초과

📋코드
첫번째 시도에 시간초과가 나서 O(n^2)방식이 아닌
NxN크기의 리스트를 만들어 O(NlogN)방식으로 바꾸었지만 이번엔 메모리 초과가 났다

두번째 시도 - 메모리 초과

import sys
input = sys.stdin.readline
N = int(input())
house = sorted(list(map(int, input().split())))
dist_list = []
sum_list = []

for _ in range(N):
    dist_list.append([0]*N)
for i in range(N):
    for j in range(i+1,N):
        dist_list[i][j] = house[j] - house[i]
        dist_list[j][i] = dist_list[i][j]

for i in range(N):
    sum_list.append(sum(dist_list[i]))
    
minV = min(sum_list)
minIdx =sum_list.index(minV)
print(house[minIdx]) 
        

두번이나 열심히 해봤으니 검색해보자 하고 검색했더니 코드 한 줄로 끝나는 문제였다 ㅋㅋ 더 풀다가 검색했으면 노트북 부실뻔

print(house_li[(n-1)//2])

뭔가 중간값인것 같으면서도 한편으론 위치적으로 오른쪽에 집들이 모여있으면 오른쪽에 있는 값이 답일 줄 알았는데.. 수학적 사고력이 부족했다

최종코드

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
house_li = []
house_li = list(map(int, input().split()))
house_li.sort()
print(house_li[(n-1)//2])

1715 카드정렬하기

📌문제 링크
https://www.acmicpc.net/problem/1715

💡 문제 풀이
처음에는 문제 예시만 보고 입력받은 값들을 정렬하고 아래와 같이 값이 작은 것 부터 값을 누적해주며 푸는 것 인줄 알았다

계속 틀렸다고 나와서 테스트케이스를 검색해보니 내가 잘못 생각했었다.

계산을 할 때 마다 작은 두 값을 계속 선택해야 하는데 내가 풀었던 방식으로 풀게되면 입력값에 같은 값이 있을 때는 최종값이 최소가 아니게 된다.
(예를 들면 3 3 3 3이 입력되면 (3+3)+(3+3)+(6+6)=24로 최소가 되야 하지만 내가 생각했던대로 풀면 (3+3)+(6+3)+(9+3)=27이 나온다)

그러므로 우선순위 큐를 통해 항상 작은 두 값을 선택하도록 접근해야 한다는 것을 알았다

comp_val += card_list[i+1]
    result += comp_val

📋코드

처음푼 코드

import sys
input = sys.stdin.readline

n =int(input())
card_list = [int(input()) for _ in range(n)]
card_list.sort()
comp_val=card_list[0]
result = 0

if n!=1:
    comp_val = card_list[0]
else:
    print(0)

for i in range(n):
    if i==n-1:
        break
    comp_val += card_list[i+1]
    result += comp_val
print(result)

최종 코드

import sys
import heapq
input = sys.stdin.readline

n =int(input())
card_list = [int(input()) for _ in range(n)]
heapq.heapify(card_list)
result = 0

if n!=1:
    while len(card_list)>1:
        tmp = heapq.heappop(card_list) + heapq.heappop(card_list)
        result += tmp
        heapq.heappush(card_list,tmp)
    print(result)
else:
    print(0)

42889 실패율(프로그래머스)

📌문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42889

💡 문제 풀이
문제 풀이는 주석에 달아 놓았습니다

풀이는 어렵지 않았지만 예외처리를 해주는데 헷갈려서 시간이 좀 걸렸다

📋코드

def solution(N, stages):
    players = len(stages)
    answer = [0 for _ in range(N)]
    looser = [0 for _ in range(N)]

    #answer리스트에 각 스테이지에 도달한 플레이어 수 입력
    for v in stages:
        if v == N+1:
            v -= 1
        for t in range(v):
            answer[t] += 1
            
    #looser리스트에 각 스테이지에 도달했지만 클리어 하지 못한 플레이어 입력
    for v in stages:
        if v==N+1:
            continue
        looser[v-1] += 1

    #answer리스트에 실패율 갱신
    for i in range(N):
        if answer[i] == 0: 
            answer[i] = (0,i)
        else:
            answer[i] = (looser[i]/answer[i],i)

    #answer리스트에 실패율에 따라 정렬(같을 시 작은 번호대로)
    answer.sort(key= lambda x: (-x[0],x[1]))
    
    for i in range(N):
        answer[i] = answer[i][1]+1
    return answer