알고리즘2023. 2. 21. 23:21
728x90

[ 문제 ]

https://softeer.ai/practice/info.do?idx=1&eid=395 

 

Softeer

연습문제를 담을 Set을 선택해주세요. 취소 확인

softeer.ai

 

 

[ 코드 ]

w,n = map(int,input().split())

jewerly = [list(map(int,input().split())) for _ in range(n)]
#금속무게 Mi, Pi가 들어오면 우선 map(int,input().split())으로 각각 정수로 받음
# -> 정수 Mi, Pi를 리스트로 묶음 ex. [Mi, Pi]
# -> [Mi, Pi]리스트를 n개 만듦 (파이썬 2차원 리스트) //https://mminky.tistory.com/141

jewerly.sort(key=lambda x: x[1],reverse=True)
# 리스트 jewerly를 정렬할거임.
# 이때, 기준x의 형태는 x[1]임. 즉, 가격인 Pi를 기준으로 정렬함.
# [Mi, Pi]에서 'Mi의 인덱스는 [0]', 'Pi의 인덱스는 [1]'이기 때문.
# reverse=True를 통해 오름차순 정렬. //https://mminky.tistory.com/170

sum_price = 0
for mi, pi in jewerly: # 리스트 jewerly에 있는 모든 mi,pi에 대해 수행
    # 지금넣는무게 <= 전체가방무게
    if mi <= w :
        sum_price += mi*pi #해당 item을 해당 price만큼
        w -= mi #item넣고 남은 무게로 w 갱신
    # 지금넣는무게 > 전체가방무게
    else:
        sum_price += w*pi #item넣고 남은 무게인 w를 해당 price만큼
        break #남은가방무게 보다 큰 애들이 나오면 끝

print(sum_price)

 

 

[ 해결 아이디어 ]

우선 이 문제는 몇 번 틀렸었다.. 그래서 코드별로 정리해보는 아이디어 노트!

 

1. 리스트 정렬

jewerly.sort(key=lambda x: x[1],reverse=True)

(오답노트)

처음에는 아래 처럼 딕셔너리를 이용해서 정렬을 했다.

# sort_dic_value = list(sort_dic.keys())
# sort_dic_weight = list(sort_dic.values())

 

하지만 문제는 딕셔너리는 중복이 안 된다.

따라서 [무게, 가치]라고 했을 때, [90, 2] 다음에 [70, 2]가 들어온다면

[90, 2]에 대한 정보는 사라지고 [70, 2]로 갱신되어 버린다.

그래서 값이 틀려진다.

위에 첨부한 코드대로 리스트 정렬을 하자!

 

2. break 

    # 지금넣는무게 > 전체가방무게
    else:
        sum_price += w*pi #item넣고 남은 무게인 w를 해당 price만큼
        break #남은가방무게 보다 큰 애들이 나오면 끝

(오답노트)

처음에는 else에 break를 쓰지 않았다.

그 결과 테스트케이스를 돌려보니 runtime error가 났다.

 

for mi, pi in jewerly: 라는 for문을 이용하게 되면 가방 안에 모든 무게를 다 넣어도

jewerly리스트 내의 모든 [mi,pi]에 대해서 반복문을 실행한다.

그래서 가방무게를 초과해서 계산하기도 한다.

어차피 지금 넣는 무게 > 전체 가방 무게 라면 전체가방 만큼만 쪼개어 넣으면 끝이기 때문에

break를 해줘서 for문을 끝내주자!

 

 

[ 결과 ]

반응형
Posted by mminky
알고리즘2022. 2. 27. 22:01
728x90

* 정렬은 출제 빈도높고, 평균 점수높다고 한다. (출처 : 프로그래머스)

 

--------------------------------------------------------------------------------------------------------------

 

[ 문제 ]

https://programmers.co.kr/learn/courses/30/lessons/42748

 

코딩테스트 연습 - K번째수

[1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]

programmers.co.kr

 

[ 코드 ]

def solution(array, commands):
    answer = []
    # com을 읽어온다. ex.[2, 5, 3]
    for com in commands:
        a, b, c = com
        ''' (위와 같은 코드)
        a = com[0]   ex. 2
        b = com[1]   ex. 5
        c = com[2]   ex. 3
        '''
        
        # 리스트 슬라이싱을 [시작:끝] 이렇게 했다면 시작~끝-1까지 담김
        arr = array[a-1:b] #2~5번째임. 인덱스에서는 1~4.
        sort_arr = sorted(arr) # 정렬
        
        # answer리스트에 추가해줌
        answer.append(sort_arr[c-1])
        
        #(참고) 이런 식으로 바로 쓰기도 가능!
        #answer.append(sorted(arr)[c-1])
    return answer

 

 

[ 참고자료 ]

파이썬 리스트 슬라이싱, append 가 헷갈린다면 아래 글이 도움될 것!

https://mminky.tistory.com/121

 

[ Python ] 리스트 추가, 삭제, 슬라이싱

* 리스트 추가 .append() * 리스트 원소 삭제 .pop .remove del * 리스트 슬라이싱 1) 이용방법 이렇게 이용하면 (시작)~(끝-1)까지의 항목들이 담긴다. 리스트명[시작:끝] 이런 리스트가 있다고 가정해보자

mminky.tistory.com

 

반응형
Posted by mminky