[Programmers] DEV MATCHING (211016)

1번문제 : 아이디 추천

문제 개요

• 새 아이디가 기존 리스트에 없으면 리턴
• 기존 리스트에 있으면 새 아이디를 만든다.

접근방법

• while문으로 기존 리스트에 없을 때까지 반복
• 모든 아이디는 S와 N으로 구성되어 있으므로, 숫자문자열 리스트 nums를 만들고 숫자가 나오면 그 인덱스까지는 문자-문자열이므로 S로, 그 이후는 숫자-문자열이므로 N으로 구분한다.(슬라이싱)
• 이후 N1은 문제에 나와있는 대로 10진 정수로 바꾸었다가 1 증가시키고 다시 문자열로 바꾼다.

결과

• 적혀있던 테스트케이스는 모두 통과했지만 정확도가 45% 였다.
• N이 최대 6자리이고 N이 0으로 시작하면 여러자리일 수 없다는 조건(cow010 은 불가) 등등을 따로 처리하지 않았기 때문으로 보인다.
• 해설이 공개되면 업데이트 해야겠다.

def solution(registered_list, new_id):
    global nums

    while new_id in registered_list:
        cnt = 0
        
        for char in new_id:
            if char not in nums:
                cnt += 1
        S = new_id[:cnt]
        N = new_id[cnt:]

        if len(N) == 0:
            n = 0
        elif len(N) > 6:
            return -1
        else:
            n = int(N)

        N1 = str(n+1)
        new_id = S + N1

    return new_id


nums = list(map(str,[x for x in range(10)]))
solution(["cow", "cow1", "cow2", "cow3", "cow4", "cow9", "cow8", "cow7", "cow6", "cow5"], "cow")

 

문제2 : 가장 긴 휴가 일수는?

문제 개요

• 매달이 1일~30일이라 할 때, 
• 사용가능한 연차수 / 연차를 쓸 수 있는 달의 첫날 요일 / 공휴일리스트
• 가 파라미터로 주어진다.
• 예를들어, 금요일이 1일, 휴일이 [6, 21, 27, 28]일이고 사용가능 연차가 4일이라면 연차를 22, 25, 26, 29일에 쓰면 연속으로 21~30일 총 10일을 쓸 수 있다.

문제 접근

• 요일에 따른 주말을 뽑아내려 했는데, 아이디어가 잘 생각나지 않아서 직접 다 적었다. 더 좋은 방법이 있을 것이다.
• 주말들을 queue에 담고, 주어진 휴일리스트를 더한다. 이때, 리스트와 리스트를 더하기 위해 extend해준다.
• 이후 중복을 없애고 리스트를 정렬한다.
• 그다음, 연속된 정수를 담는 코드를 작성했는데, packet에 temp 리스트들이 들어가게 된다. 예를들어 [1, 2, 4, 5, 6] 이라면 temp는 각각 [1, 2] 와 [4, 5, 6]이 되고 최종 packet은 [[1, 2], [4, 5, 6]] 이 된다.
• 원래는 leave에 1부터 30까지의 정수가 들어가야 하는데 에러가 나서 임의의 리스트로 넣었다.

(추가) ++ 우리반 멤버 코드풀이 접근법

• 한 달을 False 만 들어있는 리스트로 만들고, 휴일을 True로 만든다.
• 이 때, 주말은 7로 나눈 나머지 값을 활용한다.
• 휴일은 결국 True로 시작하게 되니까 리스트를 돌면서 True가 나오면 검색을 시작해서 그 이후 나오는 False를 연차 수만큼 True로 바꿔주고 연차를 다 쓰면 최댓값을 갱신한다.
• => 이 코드는 모든 경우의수를 다 확인하지 않아도 되므로 효율적이라고 생각한다.

def solution(leave, day, holidays):
    if day == "SAT":
        queue = [1, 2, 7, 8, 15, 16, 22, 23, 30]
    if day == "SUN":
        queue = [1, 7, 8, 14, 15, 21, 22, 28, 29]
    if day == "MON":
        queue = [6, 7, 13, 14, 20, 21, 27, 28]
    if day == "TUE":
        queue = [5, 6, 12, 13, 19, 20, 26, 27]
    if day == "WED":
        queue = [4, 5, 11, 12, 18, 19, 25, 26]
    if day == "THU":
        queue = [3, 4, 10, 11, 17, 18, 24, 25]
    if day == "FRI":
        queue = [2, 3, 9, 10, 16, 17, 23, 24, 30]

    queue += holidays
    queue.extend(leave)
    queue = sorted(list(set(queue)))
	
    # 연속된 날짜를 리스트에 담는 코드
    packet = []
    tmp = []
    v = queue.pop(0)
    tmp.append(v)
    
    # 최대 연속일수 초기화
    max_num = 0
    while queue:
        vv = queue.pop(0)
        
        if v + 1 == vv:
            tmp.append(vv)
            v = vv
            
        else:
            packet.append(tmp)
            tmp = []
            tmp.append(vv)
            v = vv

    packet.append(tmp)

    for i in range(len(packet)):
        one_packet = len(packet[i])
        max_num = max(one_packet, max_num)

    return max_num


print(solution([22, 25, 26, 29], "FRI", [6, 21, 23, 27, 28]))

 

풀어야 하는 코드(에러)

• 사용가능 연차가 4일이라고 할 때 1~30일 중 임의의 4개 날짜를 뽑는 조합(combinations)를 사용하여
• 모든 경우를 돌리면서 최대 연속일수를 구하려고 했으나 4가 출력되었다. 반복문에 에러가 있는 것으로 보인다.
• 그리고 이 경우 30일 중 임의의 4개날짜 조합을 뽑는 경우의 수가 약 5000개이고 이것을 매번 새롭게 넣어서 연속숫자를 뽑아 비교하면 연산횟수가 클 것 같다... (미래의 나야 부탁해..)

from itertools import combinations

def solution(leave, day, holidays):

    if day == "SAT":
        queue = [1, 2, 7, 8, 15, 16, 22, 23, 30]
    if day == "SUN":
        queue = [1, 7, 8, 14, 15, 21, 22, 28, 29]
    if day == "MON":
        queue = [6, 7, 13, 14, 20, 21, 27, 28]
    if day == "TUE":
        queue = [5, 6, 12, 13, 19, 20, 26, 27]
    if day == "WED":
        queue = [4, 5, 11, 12, 18, 19, 25, 26]
    if day == "THU":
        queue = [3, 4, 10, 11, 17, 18, 24, 25]
    if day == "FRI":
        queue = [2, 3, 9, 10, 16, 17, 23, 24, 30]

    queue += holidays
    days = [x for x in range(1, 31)]
    hols = list(combinations(days, leave))
    max_num = 0
    for i in range(len(hols)):
        queue.extend(hols[i])
        queue = sorted(list(set(queue)))

        packet = []
        tmp = []
        v = queue.pop(0)
        tmp.append(v)

        while queue:
            vv = queue.pop(0)

            if v + 1 == vv:
                tmp.append(vv)
                v = vv

            else:
                packet.append(tmp)
                tmp = []
                tmp.append(vv)
                v = vv

        packet.append(tmp)

        for i in range(len(packet)):
            one_packet = len(packet[i])
            max_num = max(one_packet, max_num)

    return max_num


print(solution(4, "FRI", [6, 21, 23, 27, 28]))