[ALGO] Sorting PROBLEM 2

문제 1

문제 1 풀이

• 기본적인 정렬 문제이지만 정렬 조건이 순차적으로 여러개라는 점만 주의하면 된다!
• 람다 함수를 통해 정렬 조건 순차적으로 명시!

code

n = int(input())            # 학생 수
data = []
for _ in range(n):
    data.append(list(input().split()))

arr = sorted(data, key= lambda x : (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

for i in range(n):
    print(arr[i][0])

문제 2

문제 2 풀이

• 완전탐색으로도 해결할 수 있지만 시간초과
• 타겟이 될 만한 집을 골라야 하는데 이 때 집의 위치를 전부 정렬시켰을 때 중앙에 있는 집이 타겟으로 적합!
• 집 개수가 홀수, 짝수일때 모두를 고려하기 위해 안정성 있게 타겟을 2개 설정(짝수일 때는 중앙이라고 할 수 있는 타겟이 2개!)
• 완전탐색 O(N^2)에서 시간복잡도가 O(N)으로 줄어듬!

code

import sys

n = int(input())            # 집 개수
pos = list(map(int, input().split()))       # 집 위치
pos.sort()
mid = len(pos)//2
target_list = [pos[mid-1], pos[mid]]

min_value = sys.maxsize
result = 0

for target in target_list:
    sum = 0
    for j in range(len(pos)):
        sum += abs(target-pos[j])
    if min_value > sum:
        result = target
        min_value = sum

print(result)

문제 3 (프로그래머스 코드 참고)

문제3 풀이

• stage에 도달했지만 클리어하지 못한 사용자를 먼저 구하자!
• 이후에는 문제에서 제시된 수식으로 정리

code

def solution(N, stages):  # N: 스테이지 개수, stages : 사용자가 멈춰있는 스테이지 배열
    answer = []
    user = len(stages)

    for i in range(1, N + 1):  # 각 스테이지마다 실패율 계산
        count = stages.count(i)         # 도달, but 클리어 못한 수
        if count == 0:
            failure = 0
        else:
            failure = count / user
        answer.append((i,failure))
        user -= count                    # stage에 도달하지 못한 user 제외
    answer = sorted(answer, key = lambda x : -x[1])
    answer = [i[0] for i in answer]
    return answer

문제 4

code

[출처] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 지음)