(백준)#10825 국영수

문제

🔗https://www.acmicpc.net/problem/10825

생각

제한시간 1초
계산 횟수 100,000x4(?)

여기서 중요 포인트는 국어는 감소하는 순서, 영어는 증가하는 순서, 수학은 감소하는 순서...
이런식으로 다 다르게 되어있다는 것.

그래서 처음에 든 생각은
1. 맨 먼저 국어 기준 비교 정렬
2. 국어 점수가 같다면, "같은 것 끼리" 영어 비교
3. 영어 점수도 같다면, "같은 것 끼리" 수학 비교
...
이런 식으로 타고 타고 들어가는거였는데,
혹시 몰라 교재 코드를 참고 해 봤더니
lambda를 통해 한번에 정렬시킬 수 있었다...

lambda(람다)

익명 함수를 지칭하는 용어, 바로 정의하여 사용할 수 있는 함수

리턴값 = lamda 인자 : 표현식

주로 정렬에 자주 쓰이는 것들

• key = lambda x : x[1] -> 두번째 요소만 가져온다. (딕셔너리 value 기준으로 정렬할 때 유용)

  a = {1:2, 5:1, 0:1, 5:2, 3:0)]
  d = sorted(a, key = lambda x : x[1]) 
  #리스트로 변한다는걸 꼭 유념해야함
  d = [(3, 0), (5, 1), (0, 1), (1, 2), (5, 2)]

• key = lambda x : (x[0], -x[1]) -> 여러개도 가능, -를 붙이면 내림차순으로 정렬된다.

  a = [(1, 2), (5, 1), (0, 1), (5, 2), (3, 0)]
  e = sorted(a, key = lambda x : (x[0], -x[1])) 
  => [(0, 1), (1, 2), (3, 0), (5, 2), (5, 1)]

• ex) key = lambda x : (x.split()[1], x.split()[0]) -> 문자열을 나누어서 정렬 가능

  #뒤에 문자 순 정렬
  s = ['2 A', '1 B', '4 C', '1 A']
  s.sorted(s, key=lambda x: (x.split()[1], x.split()[0]))
  => ['1 A', '2 A', '1 B', '4 C']

• ex) key = lambda x : (-x[1], -ord(x[0])) -> 아스키 코드 순으로 정렬 가능

  a_list = ['a', 'b', 'd', 'd', 'b','s']
  a_counter = Counter(a_list).most_common()
  => [('b', 2), ('d', 2), ('a', 1), ('s', 1)]
  
  #문자 역순(아스키 값 이용)
  sorted(a_counter,  key=lambda x: (-x[1], -ord(x[0])))
  => [('d', 2), ('b', 2), ('s', 1), ('a', 1)]

람다를 이용해 여러개를 한번에 정렬하니
정렬이 한 줄로 끝날 수 있었음...

코드

import sys

n=int(sys.stdin.readline().rstrip())
score={}

for _ in range(n):
    s=list(map(str,sys.stdin.readline().split()))
    score[s[0]]=[int(s[1]),int(s[2]),int(s[3])]

sorted_score=dict(sorted(score.items(), key=lambda x: (-x[1][0],x[1][1],-x[1][2],x[0])))
for key in sorted_score.keys():
    print(key)

(백준)#18310 안테나

문제

🔗https://www.acmicpc.net/problem/18310

생각

처음에는 이진 탐색 인가? 싶었는데
계속 여러 경우를 써보면서 생각해보니...
이거 그냥 정렬 해준 후, 가운데 집을 출력하면 되는거잖아...? 하는 생각이 들었다.
주의해야할 점은 집이 짝수개일 경우에는 가운데 두개가 같게 나오는데,
그 경우에만
여러 개의 값이 도출될 경우 가장 작은 값을 출력한다.
위의 조건에 따라 mid=n//2-1로 해준다.

코드

import sys
   
n=int(sys.stdin.readline().rstrip())
house=list(map(int,sys.stdin.readline().split()))
house.sort()
mid=0

if n%2==0:
    mid=n//2-1
else:
    mid=n//2

print(house[mid])

(백준)#1715 카드 정렬하기

문제

🔗https://www.acmicpc.net/problem/1715

생각

우선 카드를 오름차순으로 정렬을 해준 후 차례대로 더해줘야 하는데
중간에 카드를 더해줌으로 써 생기는 작은 덩어리(?)도 오름차순으로 더해줘야함
=>매순간 최소값을 보장해주는 걸 사용해야 한다
= 최소힙!

코드

import sys
import heapq

n=int(sys.stdin.readline().rstrip())
card=[]

for _ in range(n):
    t=int(sys.stdin.readline().rstrip())
    heapq.heappush(card,t)
answer=0

while len(card)>1:
    tmp1=heapq.heappop(card)
    tmp2=heapq.heappop(card)
    sum=tmp1+tmp2
    heapq.heappush(card,sum)
    answer+=sum
    

print(answer)

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

문제

🔗https://programmers.co.kr/learn/courses/30/lessons/42889

생각

계산횟수 500x200,000
애매하다... 줄여보자.

각 stage에 도달한 현황을 리스트로 한눈에 확인할 수 있게 만들자!
만약 stages=[2, 1, 2, 6, 2, 4, 3, 3] 라면
s=[0,1,3,2,1,0,1] 가 나오게
그런 다음 실패율을 구해준다.

s[i] #스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 
/ 
sum(s[i:]) #스테이지에 도달한 플레이어 수

그리고 실패율을 key로 내림차순 정렬을 해주면 된다.

코드

def solution(N, stages):
    answer = []
    fault={}
    s=[0 for _ in range(N+2)]
        
    for stage in stages:
        s[stage]+=1
    
    for i in range(1,N+1):
        if sum(s[i:])>0:
            fault[i]=s[i]/sum(s[i:])
        else:
            fault[i]=0

    answer=list(dict(sorted(fault.items() ,key=lambda x: x[1] , reverse=True)).keys())
    
    return answer