[프로그래머스] 코딩테스트 실전 대비 3차 모의고사 후기

테스트 일시

08월 15일 15시~18시

후기 작성이 조금 늦었지만... 더 늦어지면 아예 건너뛸 것 같아서
후다닥 작성합니다!

문제 복기 및 풀이 방법

총 네 문제, 난이도는 하, 중하, 상이었다. 스펙트럼이 아주 넓었던 모의고사였다.
이전에 문제 순서를 번호 순으로 풀다가 아예 못 건든 문제가 있는 것이 너무 아쉬워서
이제는 전체 문제를 한 번에 쑥 훑고 자신 있는 문제부터 풀었다.
순서는 2-1-3-4로 풀었는데, 4번은 결국 풀지 못했다...🥲

🥤 문제 1번(하)

알고리즘은 구현
문제를 읽으면서 코드를 그대로 짜면 바로 답이 나왔다.

다른 스터디원분들께서도 동일하게 코드를 짠 것을 보니
이견이 없을 코드!

# 100점
'''
🥤
일반화된 콜라 문제
빈 병 a 개를 가져다주면 콜라 b 병을 주는 마트가 있을 때,
빈 병 n 개를 가져다주면 몇 병을 받을 수 있는지 계산
'''

def solution(a, b, n):
    answer = 0
    # 바꿔주는 단위 개수보다 많이 있을 때,
    # 단위 개수보다 작아질 때까지 계산
    while n >= a:
        # 단위 개수로 나눈 몫을 미리 대기
        getReady = n // a
        # 전체 병 수에서 바꿀 만큼 빼기
        n -= getReady * a
        # 새 콜라 병수 세기
        newBottle = getReady*b
        answer += newBottle
        n += newBottle
    return 

🍔 문제 2번(중하)

알고리즘은 자료 구조(스택)이었다.
저번에도 스택이 나왔었는데, 이제 스택은 필수적으로 알아야 하는 요소를 다 외운 것 같다.
예를 들면,

• 입력값이 커지거나 많아지면, deque을 쓴다.
• ⭐️slice를 pop으로 대체할 수 있는 경우 대체해야 시간 초과를 방지할 수 있다.

바로 두번째 사항은 이번에 적용하지 못해 만점을 받지 못했는데, 정말 아쉬웠다.

'''
🍔
햄버거 포장
햄버거: 빵-야채-고기-빵
정해진 순서로 쌓인 햄버거만 포장
재료의 정보 나타내는 정수 배열 ingredient가 주어졌을 때,
포장하는 햄버거의 개수를 return
빵: 1, 야채: 2, 고기: 3
'''

'''
시간 초과 41.2점
'''
'''
def solution(ingredient):
    answer = 0
    hamburger = [1, 2, 3, 1]
    index = 0
    while index<len(ingredient):
        if ingredient[index:index+4] == hamburger:
            ingredient = ingredient[0:index] + ingredient[4:]
            answer += 1
            index -= 1
        index += 1
    
    return answer
'''
# 시간 초과 41.2
'''
def solution(ingredient):
    global answer
    answer = 0
    hamburger = [1, 2, 3, 1]
    index = 0
    def makeHamburger(ingreList, curIndex):
        global answer
        if len(ingreList)<4:
            return 
        for idx in range(curIndex, len(ingreList)):
            if ingreList[idx:idx+4] == hamburger:
                answer += 1
                return makeHamburger(ingreList[0:idx]+ingreList[idx+4:], idx-1)
        return
    makeHamburger(ingredient, index)
    
    return answer
'''
# 82.4점
def solution(ingredient):
    answer = 0
    hamburger = [1, 2, 3, 1]
    hamburgerStack = []
    for ingre in ingredient:
        # 전체 ingredient를 돌면서 재료 하나씩 stack에 넣기
        hamburgerStack.append(ingre)
        # 마지막 원소 4개가 햄버거일 때, 포장하기
        if len(hamburgerStack)>=4 and hamburgerStack[-4:] == hamburger:
            # 아마 pop()으로 했으면 100점을 맞지 않았을까...
            hamburgerStack = hamburgerStack[:-4]
            answer += 1
            
    return answer
print(solution([2, 1, 1, 2, 3, 1, 2, 3, 1]))
print(solution([1, 3, 2, 1, 2, 1, 3, 1, 2]))

💂‍ 문제 3번(중하)

알고리즘은... 아마 구현인 것 같다.
물론 다른 유형일 수도 있지만 일단 난 구현으로 풀었다.

구현은 문제를 보고 바로 떠올린 방식대로 푸는 것보다
생각의 전환을 한다면 쉽게 답이 나오는 경우가 있다.
이 문제가 특히 그랬었다.

문제만 보면 각 위치별로 휴식/근무 정보를 담아서 검사하면 될 것 같지만
사실 경비병들의 정보를 모두 돌면서 정보를 갱신하는 것으로 가면 맨 아래 최종 코드처럼 간단해진다.
자꾸 시간초과가 나서 슬퍼하다가 이러면 어떨까?하는 생각으로
우다다 작성한 게 바로 정답처리가 되어서
꽤나 큰 쾌감을 느꼈었던 것 같다.

아무튼 프로그래머스 모의고사 통틀어서 가장 마음에 드는 문제와 코드였다.

'''
💂‍♀️
보행은 1m/s의 일정한 속도로 나아간다.
감시하는 경비병의 구간은 서로 겹치지 않고, 근무-휴식을 일정 시간을 주기로 반복
근무 중에 지나가면 발각, 휴식 중에는 지나갈 수 있음
경비병의 근무 정보를 모르고 쉬지 않고 전진,
현재 위치와 적군 기지 사이의 거리를 나타내는 정수 distance
각 경비병의 감시 구간을 담은 2차원 정수 배열 scope,
같은 순서로 각 경비병의 근무 시간과 휴식 시간을 담은 2차원 정수 배열 times가 주어질 때,
경비를 피해 최대로 이동할 수 있는 거리를 return
'''

# 시간 초과 35.7점
'''
def solution(distance, scope, times):
    answer = 0
    isWorking = []
    for i in range(len(scope)):
        work, rest = times[i]
        tempRotate = []
        for _ in range(work):
            tempRotate.append(True)
        for _ in range(rest):
            tempRotate.append(False)
        tempRotate = tempRotate*((distance//(work+rest))+1)
        a, b = sorted(scope[i])
        for j in range(0, a-1):
            tempRotate[j] = 0
        for j in range(b, distance):
            tempRotate[j] = 0
        isWorking.append(tempRotate)
    isWorkingSlice = map(lambda x:x[:distance], isWorking)
    movingDistance = distance
    for soldier in isWorkingSlice:
        try:
            index = soldier.index(True) + 1
        except:
            index = distance
        movingDistance = min(movingDistance, index)
    answer = movingDistance
    return answer
'''

# 21.4점
'''
def solution(distance, scope, times):
    answer = 0
    isWorking = []
    for i in range(len(scope)):
        work, rest = times[i]
        a, b = sorted(scope[i])
        tempRotate = []
        for _ in range(work):
            tempRotate.append(True)
        for _ in range(rest):
            tempRotate.append(False)
        tempRotate = tempRotate*((distance//(work+rest))+1)
        for idx in range(len(tempRotate)):
            if idx < a-1 or b-1 < idx:
                tempRotate[idx] = 0
        print(tempRotate[:distance])
        isWorking.append(tempRotate[:distance])
    movingDistance = distance
    print(isWorking)
    for soldier in isWorking:
        try:
            index = soldier.index(True) + 1
        except:
            index = distance
        movingDistance = min(movingDistance, index)
    answer = movingDistance
    return answer
'''
# 64.3점 실패
'''
def solution(distance, scope, times):
    answer = distance
    for i in range(len(scope)):
        rangeA, rangeB = sorted(scope[i])
        work, rest = times[i]
        for j in range(rangeA, rangeB+1):
            if 0<j % ( work + rest) < work:
                answer = min(j, answer)
    return answer
'''
# 100점! 우앙!!
# ⭐️각 위치구간은 곧 화랑이의 시간대와 동일하다⭐️
def solution(distance, scope, times):
    # 한 번도 안 걸릴 경우
    answer = distance
    for i in range(len(scope)):
        # 각 경비병의 위치구간과 근무&휴식 주기를 추출
        rangeA, rangeB = sorted(scope[i])
        work, rest = times[i]
        # 각 위치 구간(==시간대)에서 근무/휴식하고 있는지 확인한다
        for j in range(rangeA, rangeB+1):
            # 화랑이가 지나갈 시점에 근무하고 있을 때 갱신하기
            if 0<j % ( work + rest) <= work:
                answer = min(j, answer)
            '''
            예시 1의 경우)
               X X 💂‍♀️ 💂‍♀️ 👮 👮 👮 👮 X X 
            💂‍♀️ W W  R  R  R  R R  W W R
            👮 W W  W  W  R  R R 'W' W W
                              (여기서 갱신)  
            '''

    return answer

print(solution(10, [[3, 4], [5, 8]], [[2, 5], [4, 3]]))
print(solution(12, [[7, 8], [4, 6], [11, 10]], [[2, 2], [2, 4], [3, 3]]))

🚨 문제 4번

분명히 BFS인데... 감이 잡히지 않았다.
다른 팀원들도 거의 손도 못 댔던 문제.
백준이나 leetcode에서 유사 문제를 찾고 있는데,
아직 큰 수확이 없다.

그래프는 테스트로 나오면 항상 어려운 것 같다.
아무리 백준 standard로 연습했어도
문제 조건이 조금이라도 달라지면 🤷‍♀️ 띠용 하게된다.

느낀 점

웬만한 코테 수월하게 합격하려면 3문제는 넘게 풀어야 할 것 같은데,
더 나아질 기미가 보이지 않아서 조금 아쉽다.

마지막 모의고사였으니 총 실전 모의고사에 대한 후기를 덧붙이자면,
주마다 3~4문제를 시간 제한 없이 풀다가
실제 코테를 보듯이 하는 경험을 해보니 환기가 되는 느낌이 들었다.

세 번의 모의고사를 끝내면서 내가 아직 부족한 유형을 정리하자면

• 그래프 탐색- 그 중 시간 초과 문제
• 탐색- 시간 초과

이제는 냅다 문제를 풀기 보다는 고급 알고리즘(비트마스킹, 다익스트라...)을 하나씩 보거나 시간복잡도를 줄일 수 있는 방법에 대해 더 고민을 해봐야 겠다.

한 달 후에 이 글을 봤을 때 그래, 나 이게 부족했었지!하는 마음이 들도록 열심히 다시 한 번 부족한 부분을 메워가보자.