크래프톤 정글 week03, day24 - 알고리즘 문제

가장 긴 부분수열

• 수열 A가 입력되면 가장 긴 증가하는 부분 수열 구하기

import sys
input = sys.stdin.readline

def longLCS(a):
    # 받은 문자열의 길이를 체크
    length = len(a)
    # 처음 시작을 1로 해야 원소가 처음 나올때 1이 체크된다.
    list = [1]*length

    # 처음껀 비교대상이 없기 때문에 1부터 시작
    for i in range(1, length):
        # i 이전 수들끼리 비교해야 하기 때문에 i까지 반복
        for j in range(i):
            # i값이 j값보다 크고(증가 수열) 리스트에 i를 넣었을 때 기존 리스트보다 길면 갱신
            if a[i] > a[j] and list[i] < list[j]+1:
                list[i] = list[j]+1

    # 리스트에서 제일 최대값을 반환
    return max(list)

n = int(input())
a = list(map(int, input().split()))
print(longLCS(a))

수열 한 줄만 주어지길래 for문으로 다음 배열 비교하면서 할려고 했는데 로직 자체를 잘못 짰다.

현재 값에서 이전 값들을 비교해서 리스트에 넣어야 했기 때문에 이중 for문을 사용해 수열이 증가할수록 1씩 증가

​

회의실 배정

• 시작시간과 끝시간이 정해진 회의를 시간대를 겹치지 않고 최대 몇개까지 예약할 수 있는지 확인하는 문제

import sys
input = sys.stdin.readline

def set_meeting():
    n = int(input())
    meeting = [list(map(int, input().split())) for _ in range(n)]
    meeting.sort(reverse=False, key=lambda x:(x[1], x[0]))
    cnt = 1
    reserve = 0

    while reserve <= n:
        for j in range(reserve+1, n+1):
            if j == n:
                return cnt
            elif meeting[reserve][1] <= meeting[j][0]:
                cnt = cnt + 1
                reserve = j
                break

    return cnt


print(set_meeting())

처음엔 시작시간을 정렬해서 끝시간과 시작시간을 대조해 안겹치는걸 찾으려고 했는데 코드가 잘 안짜져서 팀원의 조언을 듣고 끝시간을 정렬해서 시작값이랑 비교해 같거나 큰 회의만 체크해 그 회의부터 다시 반복을 돌렸다. 시작시간으로 정렬해도 비슷하게 나왔을 것 같긴 한데 둘이 뭐가 다른지는 아직 잘 모르겠다.

​

신입 사원

• 시험 순위와 면접 순위를 비교하며 실력이 떨어지는 사원 쳐내는 문제

import sys
input = sys.stdin.readline

def employ():
    t = int(input())

    for _ in range(t):
        n = int(input())
        new_comer = [list(map(int, input().split())) for _ in range(n)]
        new_comer.sort(key=lambda x:x[0])

        max_interview_rank = new_comer[0][1]
        cnt = 1

        for i in range(1, n):
            if new_comer[i][1] < max_interview_rank:
                cnt += 1
                max_interview_rank = new_comer[i][1]
                
        print(cnt)

employ()

예제를 착각해서 원래 [0]은 시험 순위이고 [1]은 면접 순위인데 [0]이 시험 점수인줄 알고 너무 복잡하게 생각하느라 오래걸렸다.

시험 순위를 오름차순으로 정렬해서 1등부터 시작해 1등의 면접 순위보다 낮은 애들은 다 쳐내고 높은친구는 체크해서 다시 그 친구부터 반복을 시작했다

​

 

학습 시간 : 10 ~ 24시