패스트캠퍼스 환급챌린지 7일차 : 네카라쿠배 취업 끝장내는 파이썬 코딩테스트 마스터

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.

 

 

Chatper 2. 기초 알고리즘

4강. 정렬 알고리즘 소개

5강. 정렬 사용 예제1

6강. 정렬 사용 예제2

레고ㄱㄱ

 

공부 시작했다 공부 끝났다

 

정렬이란?

배열 원소를 순서에 맞게 재배치

 

 

문제

1946번: 신입 사원

 

나의 미스..

1. 문제에서 입력의 값은 '점수'가 아니라 '순위'이다.  (국어를 못 한다)

2. 점수가 남들보다 떨어지지만 않으면 합격하는 문제이다. 즉, 하위 호환일 경우를 찾는 문제로 1등일 경우 하위호환이 될 수 없으니 바로 합격한다고 보면 된다. 나는 이걸 루프돌면서 다 검사하려고 했네...바보.. 정렬이라고 개념 얘기했는데 그냥 냅다 배열로만 풀려고 했다... 

3. 그래서 정렬 개념을 도입해서, 서류심사 순위가 높은 순서대로 정렬되어있으니. 면접 순위가 앞에서 본 가장 높은 순위보다 높으면 뽑힌다. 이 개념을 도입해야, 앞선 모든 사람들의 면접 순위와 비교하지 않는다. 

 

 

강사님 답변

import sys

input = sys.stdin.readline  # input 함수를 sys.stdin.readline으로 정의

T = int(input())

for _ in range(T):
    N = int(input())
    candidates = []

    for _ in range(N):
        s, m = map(int, input().split())
        candidates.append((s, m))

    candidates.sort()

    top_ranking = 1e9  # 무한대
    count = 0

    for i in range(N):
        if candidates[i][1] < top_ranking:
            count += 1
            top_ranking = candidates[i][1]

    print(count)

 

 

 

11728번: 배열 합치기

 

이 문제 그냥 배열 합쳐서 정렬하면 되잖아?

그렇다. 간단하게 그렇게 풀 수 있다. 하지만 그럴 경우 정답은 맞지만 속도가 느려서 탈락한다. 

N 길이 배열 A와 M 길이 배열 B를 더하고 단순 정렬한다면, 시간 복잡도는 O((N+M)log2(N+M)) 

→ 너무 느리다. 다른 방식으로 풀어야 한다.

 

 

강사님 풀이

두 배열 A와 B가 이미 정렬되어 있다.

1. 두 배열에서 가장 작은 값을 하나씩 가져와서 비교한다. A에서 2, B에서 1.

2. 더 작은 값 1을 새 배열 C에 넣는다.

3. B에서 다음 작은 값인 4를 가져온다. 

4. A의 2와 B의 4를 비교한다. 더 작은 값을 C에 넣는다.

5. 반복

 

이 때 시간 복잡도를 계산해보면, 각 배열에서 비교를 위해 하나씩 할당하고(= 연산자 사용.), C 배열에 할당하는 연산이 발생한다. 

즉 O(N+M) 의 시간복잡도를 가짐으로써 이전 풀이보다 훨씬 짧다. 

 

 

풀이 답변

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = []

pos1 = 0
pos2 = 0

while pos1 < N and pos2 < M:
    if A[pos1] < B[pos2]:
        C.append(A[pos1])
        pos1 += 1
    else:
        C.append(B[pos2])
        pos2 += 1

if pos1 != N:
    C.extend(A[pos1:N])
if pos2 != M:
    C.extend(B[pos2:M])

for i in C:
    print(i, end=" ")

 

 

 

 

 

https://abit.ly/lisbva

#패스트캠퍼스 #환급챌린지 #패스트캠퍼스후기 #습관형성 #직장인자기계발 #오공완