url : https://programmers.co.kr/learn/courses/30/lessons/60062

✔️ 문제 내용

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.

레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

❌ 제한사항

• n은 1 이상 200 이하인 자연수입니다.
  • weak의 길이는 1 이상 15 이하입니다.
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
  • weak의 원소는 0 이상 n - 1 이하인 정수입니다.
  • dist의 길이는 1 이상 8 이하입니다.
  • dist의 원소는 1 이상 100 이하인 자연수입니다.
  • 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.

🖐풀이 방법

• 프로그래머스에서 LEVEL 3으로 나와있다.
• 각 weak 외벽들은 모두 순환 구조이다.
• n과 같은 weak 지점은 0이다.
• weak 지점을 node라고 생각한 뒤 class를 만들어 처리해 주면 될 것 같다.

  Node에 들어갈 정보들
  1) 자신의 weak point 지점
  2) 가장 가까운 오른쪽 node지점과 거리
  3) 가장 가까운 왼쪽 지점과 node의 거리
  4) 완전탐색으로 순회할 것이기 때문에 방문 체크하는 flag

• 모든 weak지점에서 시작을 가정으로 완전 탐색을 이용한다.

  완전 탐색
  1) 지정된 노드 부터 시작하며, 왼쪽 오른쪽 순회를 각각 실행한다.
  2) 주어진 방향으로 하여 누적된 거리가 주어진 거리 중 최댓값과 =,>,< 일때를 각각 체크해준다.
   >
   - 주어진 거리 중 최댓값과 누적 거리가 같을 때 (=)
     -> 최댓값을 삭제하고 해당 노드와 옆에 있는 노드를 방문 체크 해준다.
     -> 다음 체크 대상을 옆의 노드의 옆 노드로 정의한다.
     -> 누적 거리를 초기화 시킨다
     -> 필요한 친구를 +1 한다.
   >
   - 주어진 거리 중 최댓값이 누적 거리보다 클때 (>)
     -> 다음 체크 대상을 옆의 노드로 정의한다.
     -> 누적 거리를 더해준다.
     -> 현재 노드를 방문 체크 해준다.
   >
   - 주어진 거리 중 최댓값이 누적 거리보다 작을 때(<)
     -> 현재까지의 누적 거리 중 주어진 거리와 가장 값의 차이가 없는 값을 삭제한다.
     -> 다음 체크 대상을 옆의 노드로 정의한다.
     -> 누적 거리를 초기화 시킨다
     -> 필요한 친구를 +1 한다.
  >
  이렇게 모든 정보를 최신화 했을 때 만일 모든 노드를 방문하지 않았다면 dist의 길이 +1을 리턴해준다
  이는 모두 외벽 청소를 할 수 없는 경우이며 dist의 길이 +1을 한 이유는 친구가 최대로 많을 때보다 크다면 모든 경우에서 외벽청소를 할 수 없으므로 -1을 리턴하기 위함이다.

  • 이렇게 정의해 놓고 오른쪽과 왼쪽으로 갔을 때 결과 값을 모두 최소값으로 초기 화 함으로써 해당 문제를 풀 수 있다.
  • 물론 answer값의 초기값은 101 = (dist의 최대 길이 +1)로 설정해 두어 마땅한 값이 나오지 않으면 -1을 리턴한다.
  • 해당 문제는 원형 연결 리스트를 생각하며 풀었다.
  • 조건을 복잡하게 풀었지만.. 많이 어려운 문제는 아니였다...

📃 CODE

from copy import deepcopy
class Node:
    def __init__(self,me,right,left,n):
        self.me = me # 자기 자신 노드
        # 자신의 오른쪽 왼쪽 노드의 정보를 담을 공간 idx ->0 오른쪽 / 1 ->왼쪽
        # next 정보에는 오른쪽과 왼쪽 노드의 주소 정보와 거리 차이가 들어간다
        self.info = [[right],[left]]
        self.flag = False # 방문 확인을 위한 코드
        if self.me == 0: #제일 정가운데라면
            self.info[0].append(right)
            self.info[1].append(n-left)

        else:
            self.info[0].append(
                min(
                    abs(right-me),abs(right + (n-me))
                )
            )
            self.info[1].append(
                min(
                    abs(me-left),abs(me+(n-left))
                )
            )

#최소 근접한 거리 구하는 함수
def f_del_idx(f_dist,check_dis):
    value = 300
    idx =-1
    for i in range(len(f_dist)):
        if f_dist[i]>check_dis and f_dist[i]-check_dis<value:
            idx = i
            value = f_dist[i]-check_dis
    return idx

def find_(idx,f_nodes,distances,direct):
    need_friend = 0
    check_dis = 0

    while 1:
        root = f_nodes[idx]

        if root.flag == True:
            if check_dis>0:
                need_friend+=1
            break

        if len(distances)==0:
            break

        if check_dis+root.info[direct][1] == max(distances):
            need_friend +=1
            distances.remove(check_dis + root.info[direct][1])
            check_dis =0 
            f_nodes[root.info[direct][0]].flag = True
            f_nodes[root.me].flag = True
            idx = f_nodes[root.info[direct][0]].info[direct][0]

        elif check_dis+root.info[direct][1] < max(distances):
            check_dis+=root.info[direct][1]
            f_nodes[root.me].flag = True
            idx = root.info[direct][0]

        else:
            f_nodes[root.me].flag = True
            idx = root.info[direct][0]
            del_idx = f_del_idx(distances,check_dis)

            del distances[del_idx]
            check_dis =0
            need_friend+=1

    for i in f_nodes.values():
        if i.flag == False:
            return 1001

    return need_friend

def solution(n, weak, dist):
    answer = 101
    nodes = {}
    for i in range(len(weak)):
        if i == len(weak)-1:
            nodes[weak[i]] = Node(weak[i],weak[0],weak[i-1],n)
        else:
            nodes[weak[i]] = Node(weak[i],weak[i+1],weak[i-1],n)

    for i in nodes.keys():
        right = find_(i,deepcopy(nodes),deepcopy(dist),0)

        left = find_(i,deepcopy(nodes),deepcopy(dist),1)
        ans = min(right,left)
        answer = min(answer,ans)

    if answer >len(dist):
        return -1
    return answer

url : https://programmers.co.kr/learn/courses/30/lessons/60061

✔️ 문제 내용

빙하가 깨지면서 스노우타운에 떠내려 온 "죠르디"는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. "죠르디"는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다. 프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
  단, 바닥은 벽면의 맨 아래 지면을 말합니다.
  2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다. 다음은 기둥과 보를 설치해 구조물을 만든 예시입니다.

예를 들어, 위 그림은 다음 순서에 따라 구조물을 만들었습니다.

1. (1, 0)에서 위쪽으로 기둥을 하나 설치 후, (1, 1)에서 오른쪽으로 보를 하나 만듭니다.

2. (2, 1)에서 위쪽으로 기둥을 하나 설치 후, (2, 2)에서 오른쪽으로 보를 하나 만듭니다.

3. (5, 0)에서 위쪽으로 기둥을 하나 설치 후, (5, 1)에서 위쪽으로 기둥을 하나 더 설치합니다.

4. (4, 2)에서 오른쪽으로 보를 설치 후, (3, 2)에서 오른쪽으로 보를 설치합니다.

   만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다. 기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.

   벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성해주세요.

   ❌ 제한사항

   • n은 5 이상 100 이하인 자연수입니다.

• build_frame의 세로(행) 길이는 1 이상 1,000 이하입니다.
• build_frame의 가로(열) 길이는 4입니다.
• build_frame의 원소는 [x, y, a, b]형태입니다.
• x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
• a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
• b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치를 나타냅니다.
• 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.
• 바닥에 보를 설치 하는 경우는 없습니다.
• 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.
• 구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.
• 최종 구조물의 상태는 아래 규칙에 맞춰 return 해주세요.
• return 하는 배열은 가로(열) 길이가 3인 2차원 배열로, 각 구조물의 좌표를 담고있어야 합니다.
• return 하는 배열의 원소는 [x, y, a] 형식입니다.
• x, y는 기둥, 보의 교차점 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
• 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음을 나타냅니다.
• a는 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
• return 하는 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬해주세요.
• x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 3으로 나와있다.
• 문제를 처음 읽었을 때 숨이 막혔다...
• 먼저 알아두고 가야 할 점!

  ```

1. 벽을 뚫는 기둥이나 보는 없다. (이상한 좌표가 주어지지 않는다.)
2. 좌표점으로 풀 문제이다. (좌표점 -> 웬만하면 배열이 아닌 좌표로 풀 것)

   * n = 1000 이라서 n^2의 시간 복잡도가 가능하다.
   * 해당 명령 ( 삭제 / 설치 )를 한 뒤 그 결과가 조건에 부합하는지 확인 하는 풀이로 풀면 된다.
   * 그럼 결과가 부합한지는 어떻게?

   해당 기둥이나 보를 설치 하였을 때 되는가? 보려면 조건과 같이 처리해 주면 된다.
   1. 판별 물체 = 기둥

   • 자신이 가장 맨 밑 바닥일 때 -> x-1 <0
   • 자신 밑에 기둥이 있는지 확인 -> (x,y-1,0)이 현재 갱신 된 frame에 있는지?
   • 자신의 밑을 받추어 주는 보가 있는지 ->(x,y,1) or (x-1,y,1) 갱신 된 frame에 있는지?

      이 세가지 조합이 만족 하면 된다 (x,y,1)은 기둥 기준 오른쪽 /(x-1,y,1) 왼쪽

   2. 판별 물체 = 보

   • 갱신 된 frame에서 자신을 받추어 주는 기둥이 오른쪽 이나 왼쪽에 있는지 ? ->(x,y-1,0), (x+1,y-1,0) in frame?
   • 갱신 된 frame에서 보가 양 옆에 있는지 ? -> ((x-1,y,1) in frame_ and (x+1,y,1) in frame_): ```

     이렇게 판별이 끝나서 모두 가능한 위치이면 명령을 그냥 가져가고 아니면 다시 되돌린다.

   • 마지막에는 정렬을 해서 풀어준다.

📃 CODE

def can(frame_):
    for x,y,a in frame_:
        if a == 0:
            if y-1 <0 or (x,y-1,0) in frame_ or (x,y,1) in frame_ or (x-1,y,1) in frame_:
                continue
            return False
        else:
            if (x,y-1,0) in frame_ or (x+1,y-1,0) in frame_ or ((x-1,y,1) in frame_ and (x+1,y,1) in frame_):
                continue
            return False

    return True

def make_ans(data,answer):

    for x,y,z in data:
        answer.append([x,y,z])
def solution(n, build_frame):
    answer = []
    ans = list()

    for x,y,a,b in build_frame:

        if b== 0:
            ans.remove((x,y,a))
            if can(ans) == False:
                ans.append((x,y,a))
        else:
            ans.append((x,y,a))
            if can(ans) == False:
                ans.remove((x,y,a))
    make_ans(ans,answer)

    return sorted(answer,key = lambda x : (x[0],x[1],x[2]))

추가 !!!

해당 문제는 list를 사용하여 같은 방식으로 풀어도 상관없다. 하지만 시간에서 엄청난 차이를 보이는데, 그 이유는 remove시 set은 O(1) list는 O(n)이기 때문이다. -> set은 중복값 없이 저장하는 것이 차이점이다.

url : https://programmers.co.kr/learn/courses/30/lessons/72414

✔️ 문제 내용

카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 "죠르디"는 요청을 받아들였고 광고효과를 높이기 위해 시청자들이 가장 많이 보는 구간에 공익광고를 넣으려고 합니다. "죠르디"는 시청자들이 해당 동영상의 어떤 구간을 재생했는 지 알 수 있는 재생구간 기록을 구했고, 해당 기록을 바탕으로 공익광고가 삽입될 최적의 위치를 고를 수 있었습니다. 참고로 광고는 재생 중인 동영상의 오른쪽 아래에서 원래 영상과 동시에 재생되는 PIP(Picture in Picture) 형태로 제공됩니다.

다음은 "죠르디"가 공익광고가 삽입될 최적의 위치를 고르는 과정을 그림으로 설명한 것입니다.

• 그림의 파란색 선은 광고를 검토 중인 "죠르디" 동영상의 전체 재생 구간을 나타냅니다.

• 위 그림에서, "죠르디" 동영상의 총 재생시간은 02시간 03분 55초 입니다.
• 그림의 검은색 선들은 각 시청자들이 "죠르디"의 동영상을 재생한 구간의 위치를 표시하고 있습니다.
• 검은색 선의 가운데 숫자는 각 재생 기록을 구분하는 ID를 나타냅니다.
• 검은색 선에 표기된 왼쪽 끝 숫자와 오른쪽 끝 숫자는 시청자들이 재생한 동영상 구간의 시작 시각과 종료 시각을 나타냅니다.
• 위 그림에서, 3번 재생 기록은 00시 25분 50초 부터 00시 48분 29초 까지 총 00시간 22분 39초 동안 죠르디의 동영상을 재생했습니다. 1
• 위 그림에서, 1번 재생 기록은 01시 20분 15초 부터 01시 45분 14초 까지 총 00시간 24분 59초 동안 죠르디의 동영상을 재생했습니다.
• 그림의 빨간색 선은 "죠르디"가 선택한 최적의 공익광고 위치를 나타냅니다.
• 만약 공익광고의 재생시간이 00시간 14분 15초라면, 위의 그림처럼 01시 30분 59초 부터 01시 45분 14초 까지 공익광고를 삽입하는 것이 가장 좋습니다. 이 구간을 시청한 시청자들의 누적 재생시간이 가장 크기 때문입니다.
• 01시 30분 59초 부터 01시 45분 14초 까지의 누적 재생시간은 다음과 같이 계산됩니다.
• 01시 30분 59초 부터 01시 37분 44초 까지 : 4번, 1번 재생 기록이 두차례 있으므로 재생시간의 합은 00시간 06분 45초 X 2 = 00시간 13분 30초
• 01시 37분 44초 부터 01시 45분 14초 까지 : 4번, 1번, 5번 재생 기록이 세차례 있으므로 재생시간의 합은 00시간 07분 30초 X 3 = 00시간 22분 30초
• 따라서, 이 구간 시청자들의 누적 재생시간은 00시간 13분 30초 + 00시간 22분 30초 = 00시간 36분 00초입니다.
  "죠르디"의 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.

❌ 제한사항

• play_time, adv_time은 길이 8로 고정된 문자열입니다.

• play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01 이상 99:59:59 이하입니다.
• 즉, 동영상 재생시간과 공익광고 재생시간은 00시간 00분 01초 이상 99시간 59분 59초 이하입니다.
• 공익광고 재생시간은 동영상 재생시간보다 짧거나 같게 주어집니다.
• logs는 크기가 1 이상 300,000 이하인 문자열 배열입니다.

  • logs 배열의 각 원소는 시청자의 재생 구간을 나타냅니다.

• logs 배열의 각 원소는 길이가 17로 고정된 문자열입니다.
• logs 배열의 각 원소는 H1:M1:S1-H2:M2:S2 형식입니다.
• H1:M1:S1은 동영상이 시작된 시각, H2:M2:S2는 동영상이 종료된 시각을 나타냅니다.
• H1:M1:S1는 H2:M2:S2보다 1초 이상 이전 시각으로 주어집니다.
• H1:M1:S1와 H2:M2:S2는 play_time 이내의 시각입니다.
• 시간을 나타내는 HH, H1, H2의 범위는 0099, 분을 나타내는 MM, M1, M2의 범위는 0059, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다.
• 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11:12:78, 123:12:45 등)
  return 값의 형식 공익광고를 삽입할 시각을 HH:MM:SS 형식의 8자리 문자열로 반환합니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 3으로 나와있다.
• 기본적으로 구현은 쉬우나 구현 방법을 잘 정해주어야 하는 문제이다.
• to_second() 함수는 문자열을 초 단위로 바꾸어 주는 역할을 한다.
• to_time() 함수는 수를 문자열로 바꾸어 HH:MM:SS형식에 맞게 바꾸어 주는 역할을 한다.
• 해당 조건 중 알아야 하는 것 중 주의할 부분! ``` 1) 광고 시간과 주어진 play시간이 같을 수 있다! -> 해당 경우는 무조건 처음에 틀어주면 된다. (최대한 많이 먹음) 2) 시청 시간에서 시작시간은 해당 시청자가 시청한 시점! 이지만 끝나는 시간은 시청 시간이 아니다.
• 2번을 통해 구간 더하기를 구할 때 끝나는 시간의 배열을 포함해주면 안된다.

  * 99:99:99 의 시간이 최대이 임으로 100*3600 = 360000 보다 작음으로 초단 위로 메모리 관리
  * 해당 메모리에서  시청 시간의 시작시간에는 +1 , 종료 시점에 -1을 해준다.

  이는 시작시간과 종료 시간의 구간을 표현하는데 가능하다.

  * 그 다음 으로 구간의 합을 더해 주는데, 혼자만 보는 것이 아니기 때문에 해당 초의 시청 인원을 구해주기 위해서이다.
  ~~종료 시점에  -1을 해준 것이 바로 이 구간을 위해서 인데, -1을 하여 해당 시간 시청한 사람을 이제 제외시켜주는 역할을 한다.~~
  * 다음에 i초부터 (광고 시간+i-1)시간 까지를 더한 값을 순회적으로 비교하면서 최대 시청인원인 구간의 시작점을 ans로 한다.
  * mid 값을 설정한 이유는 i-1을 해주며 비교 시간을 계속 갱신화 해주어야 하기 때문이다.
  
  
  
  

📃 CODE

def to_second(s):
    s_arr = s.split(':')
    return int(s_arr[0])*3600 + int(s_arr[1])*60 + int(s_arr[2])

def to_time(num):

    hour = "0"+str(num//3600)
    num %=3600
    minute = "0"+str(num//60)
    num %=60
    second = "0"+str(num)

    return hour[-2:]+":"+minute[-2:]+":"+second[-2:]

def solution(play_time, adv_time, logs):
    answer = ''
    play_ = to_second(play_time)
    adv_ = to_second(adv_time)
    period = [0 for _ in range(play_+1)]

    if play_ == adv_:
        return to_time(0)

    for i in logs:
        log_time = i.split("-")
        period[to_second(log_time[0])] += 1
        period[to_second(log_time[1])] -= 1


    for i in range(1,play_):
        period[i] +=period[i-1] # 구간 중복 유저 구함

    ans = 0 #처음 시작 
    max_period = sum(period[0:adv_])
    mid = max_period

    for i in range(1,play_+1-adv_):

        mid +=period[adv_+i-1] -period[i-1]

        if mid >max_period:
            max_period = mid
            ans = i




    return to_time(ans)

url : https://programmers.co.kr/learn/courses/30/lessons/42892

✔️ 문제 내용

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다. 그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다. 라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
  아래 예시를 확인해보자. 라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)
  이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다. 위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.
• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7
  다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다. 그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다. 이제 당신이 나설 때가 되었다. 곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

❌ 제한사항

• nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.

• nodeinfo의 길이는 1 이상 10,000 이하이다.
• nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
• 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
• 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
• 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 3로 되어있다.

  • 먼저 문제에 나온 전위순회와 후위 순회에 대해 알아보아야 한다.

  * 전위 순회는 [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회합니다.
  * 중위 순회는 [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회합니다.
  * 후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회합니다.

  • 주어진 값을 어떻게 2진 트리와 같은 형식으로 나타낼까? 라는 생각을 해보았는데 아래와 같은 생각이 들었다. ```
  • 주어진 수 중 Y축이 가장 큰 것은 가장 최상단 root이다. (가장 위에 있으므로)
  • 주어진 수 중 X축이 가장 작은 것은 최 왼쪽 / 가장 큰 것은 최 오른쪽에 있다고 생각할 수 있다.
  • 그러면 가장 큰 Y값을 찾아서 root node로 두고 해당 node에 왼쪽과 오른쪽을 x가 자신의 x보다 큰가 작은가로 나누어 줄 수 있다.
  • 만일 둘중에 자식 노드가 없다면 해당 node는 마지막 노드가 되는 것이다.
  • node class를 만들어서 위의 조건에 맞게 root node의 x를 기준으로 나누어 주면 이진 트리가 될 수 있다. ```
  • 이렇게 나누어진 class를 기준으로 전위 순회와 후위 순회를 처리해주면 된다.

📃 CODE

import sys
sys.setrecursionlimit(10**6)
class Tree:
    def __init__(self,datas):
        self.root = max(datas,key =lambda x: x[1])
        self.index = self.root[2]
        left_ = list(filter(
            lambda x:x[0]<self.root[0],datas
        ))
        right_ = list(filter(
            lambda x:x[0]>self.root[0],datas
        ))

        if left_ == []:
            self.left = None
        else:
            self.left = Tree(left_)

        if right_ ==[]:
            self.right = None
        else:
            self.right = Tree(right_)

def go(tree,postlist,prelist):
    postlist.append(tree.index)

    if tree.left is not None:
        go(tree.left,postlist,prelist)
    if tree.right is not None:
        go(tree.right,postlist,prelist)

    prelist.append(tree.index)

def solution(nodeinfo):
    answer =[]

    #index 정보 추가해주기
    for i in range(len(nodeinfo)):
        nodeinfo[i].append(i+1)

    first_tree = Tree(nodeinfo)
    postlist,prelist = [],[]
    go(first_tree,postlist,prelist)

    answer.append(postlist)
    answer.append(prelist)
    return answer

url : https://programmers.co.kr/learn/courses/30/lessons/17686?language=python3

✔️ 문제 내용

세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다.

버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되지만, 숫자 순으로 정렬된 ["img1.png", "img2.png", "img10.png", img12.png"] 순이 훨씬 자연스럽다. 무지는 단순한 문자 코드 순이 아닌, 파일명에 포함된 숫자를 반영한 정렬 기능을 저장소 관리 프로그램에 구현하기로 했다.

소스 파일 저장소에 저장된 파일명은 100 글자 이내로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다. 파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다.

• HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
• NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
• TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
  파일명을 세 부분으로 나눈 후, 다음 기준에 따라 파일명을 정렬한다.
• 파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. 이때, 문자열 비교 시 대소문자 구분을 하지 않는다. MUZI와 muzi, MuZi는 정렬 시에 같은 순서로 취급된다.
• 파일명의 HEAD 부분이 대소문자 차이 외에는 같을 경우, NUMBER의 숫자 순으로 정렬한다. 9 < 10 < 0011 < 012 < 13 < 014 순으로 정렬된다. 숫자 앞의 0은 무시되며, 012와 12는 정렬 시에 같은 같은 값으로 처리된다.
• 두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.
  무지를 도와 파일명 정렬 프로그램을 구현하라.

👇 입력 형식

입력으로 배열 files가 주어진다.

• files는 1000 개 이하의 파일명을 포함하는 문자열 배열이다.

• 각 파일명은 100 글자 이하 길이로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.

• 중복된 파일명은 없으나, 대소문자나 숫자 앞부분의 0 차이가 있는 경우는 함께 주어질 수 있다. (muzi1.txt, MUZI1.txt, muzi001.txt, muzi1.TXT는 함께 입력으로 주어질 수 있다.)

  👆출력 형식

  위 기준에 따라 정렬된 배열을 출력한다.

  🖐풀이 방법

  • 프로그래머스에서 LEVEL 2로 되어있다.

    • 이번 문제 해결의 키는 head/number/tail 나누는 것이 key로 동작할 것 같다.

📃 CODE

   def make_data(file,i):
    head =''
    number =''
    count = 0
    tail = ''
    for idx in range(len(file)):
        if count ==0 and (file[idx] <'0' or file[idx]>'9'):
            head+=file[idx]

        elif count <5 and (file[idx] >='0' and file[idx]<='9'):
            number +=file[idx]
            count+=1
        else:
            tail = file[idx:]
            break

    return (head,number,i,tail)


def solution(files):
    answer = []
    change_data = []

    for idx in range(len(files)):
        change_data.append(make_data(files[idx],idx))

    sorted_data = sorted(change_data,
                         key = lambda x:(x[0].lower(),int(x[1]),x[2]))

    for i in sorted_data:
        answer.append(i[0]+i[1]+i[3])
    return answer

➕다른 사람 풀이 참고 할 만한 내용

python libaray 중 re를 참고하여 문자의 추출을 하는데 사용하면 더 짧고 쉽게 풀 수 있다.

url : https://programmers.co.kr/learn/courses/30/lessons/17678

✔️ 문제 내용

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다. 이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

👇 입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10

• 0 ＜ t ≦ 60

• 0 ＜ m ≦ 45

• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.

• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

  👆출력 형식

  콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

  🖐풀이 방법

  • 프로그래머스에서 LEVEL 3로 되어있다.

• 꼭 인지하고 풀어야 할 것

1. 콘은 주어진 시간에서 가장 마지막에 타는 사람이다.
2. 셔틀의 첫 시간은 9:00이다.
3. 크루 중 셔틀이 끝나는 시간보다 늦게 줄을 서는 사람이 있다.

콘의 시간이 결정되는 조건

• 만일 버스 운행이 남았는데 더이상 남아있는 크루가 없다면?
• 만일 계산 중인 셔틀 오는 시간이 마지막 운행 셔틀 시간보다 늦는다면? = 마지막 셔틀 탑승

• 만일 줄을 서있는 크루 중 가장 빨리 나온 크루의 시간이 셔틀이 오는 시간보다 늦는다면? -> start_time은 다음 시간 조사 -> 셔틀 운행 수 -1 -> 크루 다시 대기열에 삽입 -> 태울 수 있는 크루 수 초기화 -> 만약에 해당 셔틀이 마지막이였다면 마지막 셔틀 시간에 콘이 나와있으면 된다.

*만일 줄을 서 있는 크루 중 셔틀을 탈 수 있는 사람이 있었다면? -> 탑승 인원 -1 ->가장 최근 탑승 크루 시간 최신화 ->만약에 방금 탄 1자리가 마지막 자리였다면 최근 탑승 크루보다 1분 빨리 나오는 시간 리턴 -> 만약에 방금 탄 자리가 해당 버스의 마지막 자리였다면 버스 출발 시키고 다음 셔틀로 연산

📃 CODE

   import heapq
def table(lis):
    arrs = []
    for i in lis:
        arr = i.split(":")
        crew_time = int(arr[0])*3600 + int(arr[1])*60
        heapq.heappush(arrs,crew_time)

    return arrs

def make_form(s1,s2):
    if len(s1) == 1:
        s1 = '0'+s1
    s1+=':'
    if len(s2) == 1:
        s2 = '0'+s2

    return s1+s2

def solution(n, t, m, timetable):
    answer = ''

    crew_time = table(timetable)
    start_time = 9*3600
    end_time = 9*3600 +(t*60)*(n-1)
    be = start_time
    mid = m
    while 1:

        if len(crew_time) ==0 :
            break

        if start_time > end_time:
            break
        crew = heapq.heappop(crew_time)


        if crew > start_time:
            start_time +=60*t
            n -=1
            heapq.heappush(crew_time,crew)
            mid = m
            if n == 0:
                return make_form(str(end_time//3600),str((end_time%3600)//60))


        else:
            mid -=1
            be = crew

            if mid == 0 and n ==1:
                return make_form(str((be-60)//3600),str(((be-60)%3600)//60))

            elif mid ==0:
                mid = m
                n-=1
                start_time +=t*60

    return make_form(str(end_time//3600),str((end_time%3600)//600))

url : https://programmers.co.kr/learn/courses/30/lessons/12904

✔️ 문제 내용

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

❌ 제한 사항

• 문자열 s의 길이 : 2,500 이하의 자연수

• 문자열 s는 알파벳 소문자로만 구성

  🖐풀이 방법

  • 프로그래머스에서 LEVEL 3로 되어있다.
  • 처음에는 팰린드롬인지 검사할 string의 크기를 늘려가며 검사하였다
  • 효율성 2번에서 오답이 났다
  • 해당 처럼 검사하면 최악의 경우 n^4의 시간 복잡도가 나오기 때문
  • 반대로 큰 것을 검사하고 해당 검사가 끝마녀 끝내주는 것이 어떨까?

  📃 CODE

   def isyes(s):
    for i in range(len(s)):
        if s[i] != s[len(s)-i-1]:
            return False
  
    return True
  def solution(s):
    answer = 0
  
    for i in range(len(s)):
        for j in range(len(s)-1,i-1,-1):
  
            if isyes(s[i:j+1]):
                answer = max(answer,len(s[i:j+1]))
                break
  
    return answer

url : https://programmers.co.kr/learn/courses/30/lessons/42627

✔️ 문제 내용

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어

• 0ms 시점에 3ms가 소요되는 A작업 요청

• 1ms 시점에 9ms가 소요되는 B작업 요청
• 2ms 시점에 6ms가 소요되는 C작업 요청
  와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.
  한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.
• A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
• B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
• C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)
  이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다. 하지만 A → C → B 순서대로 처리하면

  

• A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
• C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
• B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)
  이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다. 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

❌ 제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 3로 되어있다.

• 처음에는 작업이 짧은 것 부터 처리해주면 되는 것이라고 생각했는데. 그렇게 되면 (1,100) 와 (101,1) 작업이 들어올 때의 반례가 생긴다.

• 따라서 작업 시간을 고려해 주어 문제를 해결하면 된다.

• 작업을 작업 시간 별로 정렬한다.

• 주어진 가장 짧은 작업이 현재 시간에 종속되는지 확인한다.

• 만일 작업시간에 종속되지 않는다면 그 다음 짧은 작업이 종속되는지 확인한다.

• 모두 현재의 시간에 종속되지 않는다면 시간을 +1만큼 늘려주며 작업을 진행한다.

  📃 CODE

  def solution(jobs):
   answer = 0
   jobs = sorted(jobs,key = lambda x:x[1])
   time = 0
   idx =0
   count = len(jobs)
   while len(jobs)>0:
       if idx>=len(jobs):
           idx = 0
           time+=1
       if jobs[idx][0]<=time:
           answer=answer+(time-jobs[idx][0])+jobs[idx][1]
           time += jobs[idx][1]
           del jobs[idx]
           idx = 0
  
       else:
           idx +=1
   return answer//count

url : https://programmers.co.kr/learn/courses/30/lessons/43105

✔️ 문제 내용

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

❌ 제한 사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 3로 되어있다.

• 배열의 크기가 작아서 완전 탐색으로 풀 수 있을까? 라는 생각을 해보았지만 1초 만에 접었다.

• 간단하게 주어진 배열과 크기가 같은 새로운 배열을 만들어서 해당 index에는 해당 점수를 무조건 갖는다는 기준을 세우고 처리하면 된다.

• 주의 사항은 행의 인덱스가 0 or -1(마지막)일 때는 무조건 한 곳에서만 내려 올 수 있다는 사실을 기준 세우고 수식을 세워주면 된다.

• 프로그래머스에 땅따먹기 문제의 업그레이드? 같아서 땅따먹기 제 velog url 공유 드립니당

• https://velog.io/@choi-montaunk/프로그래머스-땅따먹기

  📃 CODE

  def solution(triangle):
       answer = 0
       dp = [[0 for j in range(len(triangle[i]))]for i in range(len(triangle))]
  
       for i in range(len(triangle)):
           for j in range(len(triangle[i])):
               if j == 0:
                   dp[i][j] = dp[i-1][j]+triangle[i][j]
               elif j == len(triangle[i])-1:
                   dp[i][j] = dp[i-1][j-1]+triangle[i][j]
               else:
                   dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
  
  

    return max(dp[len(dp)-1])

url : https://programmers.co.kr/learn/courses/30/lessons/12913

✔️ 문제 내용

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

❌ 제한 사항

• 행의 개수 N : 100,000 이하의 자연수

• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• 행의 개수가 100000임으로 완전 탐색으로는 시간 초과가 걸린다.

• 위의 이유 때문에 문제 해결 접근을 DP를 사용하여 풀어야한다.

• 배열을 돌며 해당 위치의 땅을 밣았을 때를 기준으로 전의 땅(전의 열)에서 가장 큰 값을 더해준다.

• 땅의 행이 4임으로 본 풀이 방식을 4 x 4 x 100000 < 1억 임므로 해결 가능하다.

  📃 CODE

  def solution(land):
  
   dp = [[0,0,0,0] for i in range(len(land))]
  
   dp[0] = land[0]
  
   for i in range(1,len(land)):
       for j in range(4):
           for k in range(4):
               if j == k:
                   continue
               dp[i][j] = max(dp[i][j],dp[i-1][k]+land[i][j])
  
  

#print(dp)
return max(dp[len(land)-1])def solution(skill, skill_trees):
ans = 0
for s in skill_trees:
    mid = ''

    for check in s:
        if check in skill:
            mid+=check

    if len(mid)== 0:
        ans+=1

    elif mid in skill and skill[0:len(mid)] == mid:
        ans+=1
return ans

url : https://programmers.co.kr/learn/courses/30/lessons/49993

✔️ 문제 내용

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때

썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. > 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, > 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

❌ 제한 사항

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

• 스킬 순서와 스킬트리는 문자열로 표기합니다. (예를 들어, C → B → D 라면 "CBD"로 표기합니다)
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
• skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• 스킬트리로 온 값들과 skill 트리의 종속되어있는지 주어진 스킬트리 '순차적'으로 검사한다.

• 순차적으로 검사하는 이유는 스킬트리의 순서가 중요하기 때문

• 만일 스킬트리와 일치하는 것이 없다면 배우는데 상관없다 -> 스킬트리에 연관 되지 않기 때문

• 주어진 스킬트리의 순서와 스킬셋이 일치하는지 확인한다.

  📃 CODE

  def solution(skill, skill_trees):
   ans = 0
   for s in skill_trees:
       mid = ''
  
       for check in s:
           if check in skill:
               mid+=check
  
       if len(mid)== 0:
           ans+=1
  
       elif mid in skill and skill[0:len(mid)] == mid:
           ans+=1
   return ans

url : https://programmers.co.kr/learn/courses/30/lessons/12911

✔️ 문제 내용

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

❌ 제한 사항

• n은 1,000,000 이하의 자연수 입니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• +1씩 해주어가며 2진수의 1의 갯수를 비교해주면 간단히 해결 가능하다

  📃 CODE

  def solution(n):
   answer = 0 
   count = bin(n).count("1") 
   for num in range(n+1, 1000001): 
       if count == bin(num).count("1") : 
           answer = num 
           break 
   return answer

url : https://programmers.co.kr/learn/courses/30/lessons/12981

✔️ 문제 내용

문제 이미지가 많으므로 URL을 통해 문제를 읽어주세여:)

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.
   다음은 3명이 끝말잇기를 하는 상황을 나타냅니다. tank → kick → know → wheel → land → dream → mother → robot → tank 위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)
  끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다. 사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

❌ 제한 사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.

• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• 먼저 다음에 오는 단어가 타당한가 (끝말잇기 규칙에 맞는가 and 처음 나오는 단어인가)를 판별해 주는 함수 구현 -> 타당하다 : True / 타당하지 않다 : False return

• 만일 지속적으로 타당한 단어가 나오면 [0,0] 을 return 한다. (code에서 flag 이용)

• 만일 타당하지 않은 단어가 나온다면 나온 단어가 몇번째로 호출 되었는지 확인하여 답 도출

• 다른 분의 풀이를 보았는데 효율적으로 who와 when을 계산하여 처리 해주셨습니다. 저의 코드가 아니여서 확실하게 말은 못드리지만 n만큼 묶을 때 2번째 단어부터 묶어 처리해주셨습니다.

  📃 CODE

  def cancheck(i,be,wordcheck):
  
   if i[0] != be[-1]:
       return False
   if i in wordcheck:
       return False
   return True
  def solution(n, words):
  
   wordcheck = [words[0]]
   cnt = 1
   be = words[0]
   words = words[1:]
  
   flag = False
   for i in words:
       if cancheck(i,be,wordcheck) == False:
           cnt +=1
           flag = True
           break
       else:
           wordcheck.append(i)
           cnt+=1
           be = i
   if flag == False:
       return [0,0]
   who = cnt%n
   when = cnt//n
   if who == 0:
       who = n
   else:
       when +=1
  
   return [who,when]

url : https://programmers.co.kr/learn/courses/30/lessons/49994

✔️ 문제 내용

문제 이미지가 많으므로 URL을 통해 문제를 읽어주세여:)

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

❌ 제한 사항

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.

• dirs의 길이는 500 이하의 자연수입니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• (현재 좌표, 이동좌표)의 데이터를 방문 한 지점으로 체크해주면 된다.

• 경로에는 방향성이 없으므로 (이동 좌표, 현재 좌표)도 함께 처리해주어야 한다.

• 경로를 벗어나는 경우만 무시하고 아무 연산을 해주지 않으면 된다.

  📃 CODE

  def solution(dirs):
   answer = 0
   dic = {'U':[1,0],
         'D':[-1,0],
         'R':[0,1],
         'L':[0,-1]}
  
   start = [0,0]
   vst = [] 
   for s in dirs:
  
       dx = dic[s][0]
       dy = dic[s][1]
  
       if start[0]+dx<-5 or start[0]+dx>5:
           continue
       if start[1]+dy>5 or start[1]+dy<-5:
           continue
  
       trace = (start[0],start[1],start[0]+dx,start[1]+dy)
       retrace = (start[0]+dx,start[1]+dy,start[0],start[1])
  
       if trace not in vst or retrace not in vst:
           vst.append(trace)
           vst.append(retrace)
       start[0],start[1] = start[0]+dx,start[1]+dy
   print(vst)
   return len(vst)//2

url : https://programmers.co.kr/learn/courses/30/lessons/12971

✔️ 문제 내용

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다. 예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.해주세요.

❌ 제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.

• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• 먼저 제한사항에 N의 길이가 100000이하임으로 완전 탐색은 되지 않는다

• 순차적으로 수를 더하는 것이기에 DP 방법을 사용하려 한다.

• dp 배열에 각 index에 해당하는 것은 스티커 순번이고 값은 스티커가 무조건 띄어졌다 라는 가정으로 문제를 풀 예정인다.

  • 이때 일반적인 DP와 달리 맨 마지막과 맨 처음의 연관성이 있다.
  • 그래서 맨 처음스티커를 떼었다고 가정한 배열과 떼지 않았다고 가정한 배열 두개로 계산한다.
  • 맨 처음 스티커를 뗀 배열에서는 맨 마지막 스티커를 연산하지 않아준다.
  • 추가로 배열 크기가 1일 때는 그냥 스티커 하나를 무조건 떼는게 좋음으로 연산 없이스티커 값을 리턴한다.
  • off_zero[2]의 뜻은 첫번째 스티커를 떼지 않은 경우에 세번째 스티커를 뗄것인가 말것인가 라는 가정으로 푸는 것이다.
  • on_zero[2]의 뜻은 첫번째 스티커를 뗀 경우에 세번째 스티커를 뗄것인가 말것인가 라는 가정으로 푸는 것이다.
  • 수식은
  • (자신의 전전까지의 값+ 자신의 값) - 자신을 뜯음 과 (자신의 전 값) - 자신을 뜯지 않음 * 중 큰것으로 하면 된다.

  📃 CODE

  def solution(sticker):
   answer = 0
  
   if len(sticker)==1:
       return sticker[0] # 스티커 하나일 때
  
   off_zero = [0 for i in sticker] # 0번째 스티커를 떼지 않았을 때 배열
   on_zero = [0 for i in sticker] # 0번째 스티커를 떼었을 때 배열
  
   # 값 초기화 이 때 0번째 스티커를 떼지 않는 배열에서는 0번째 값을 0으로 한다.
   on_zero[0],on_zero[1]=sticker[0],sticker[0] 
   off_zero[1],off_zero[0]= sticker[1],0
  
  

for idx in range(2,len(sticker)):
    off_zero[idx] = max(off_zero[idx-1],off_zero[idx-2]+sticker[idx])

    if(idx == len(sticker)-1): # 맨 처음 스티커를 뗀 배열에서는 맨 마지막 스티커를 연산하지 않아준다.
        continue

    on_zero[idx] = max(on_zero[idx-1],on_zero[idx-2]+sticker[idx])


return max(max(on_zero),max(off_zero))

url : https://programmers.co.kr/learn/courses/30/lessons/77885

✔️ 문제 내용

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다. x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 예를 들어, f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수 비트 다른 비트의 개수 2 | 000...0010 | 3 | 000...0011 | 1

f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수 비트 다른 비트의 개수 7 | 000...0111 |
8 | 000...1000| 4 9 | 000...1001 | 3 10 | 000...1010 | 3 11 | 000...1011 | 2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

❌ 제한 사항

• 0 ≤ numbers의 길이 ≤ 100,000

• 0 ≤ numbers의 모든 수 ≤ 1015

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• 먼저 주어진 수가 짝수이면 bit는 해당 자리 빼고는 모두 0임으로 +1 ( 1개 변경 )

• 홀수이면 오른쪽 부터 가장 먼저 0이 나오는 수를 1로 변경해주고 1이 나오기 전 수를 0으로 변경 해줍니다. ( 2개 변경 )

• 그렇게 되면 변경 수는 2^n - 2^(n-1)만큼 증가하게 되는 것입니다. (n은 처음으로 나오는 0) 예를 들어 주어진 수가 5라면 이진법으로 변경하였을 때 101이 됩니다. 그럼 처음으로 0이 나오는 수는 나오는 수 (=n)은 2가 되고 2^2 - 2^1 을 기존 수에 더해준 값이 정답이 됩니다. 최대 바뀔 수 있는 비트는 2개 임으로 위의 조건이 가능 합니다.

  📃 CODE

  def solution(numbers):
   answer = []
   #list(bin(numbers[1]))
  
   for num in numbers:
       if num %2 == 0:
           answer.append(num+1)
       else:
           check= 1
           while True:
               if check & num == 0:
                   break
               check *=2
           answer.append(num+check-check/2)
           #사실 check는 2의 배수이기 때문에 num + check/2 로 해주어도 된다.
   return answer

url : https://programmers.co.kr/learn/courses/30/lessons/17679

✔️ 문제 내용

사진이 많으므로 URL 참조 부탁드립니다 : )

❌ 제한 사항

사진이 많으므로 URL 참조 부탁드립니다 : )

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

• 단순한 구현이다 아래의 순서에 맞게만 코드를 진행해주면 된다. 1 )겹쳐진 4개의 블록이 있는지 확인

  ```블록 확인 시 주의 할 점은 겹쳐서 터지는 블록도 있다는 것!```

  2 ) 겹쳐진 블록을 터트리며 터진 블록 수 세기

  ```겹쳐서 터지는 블록은 모두 1개로 취급되어야 함   만일 4의 배수로 답이 나온다면 겹치는 블록을 복수로 처리했는지 확인 해주세요```

  3 ) 문제의 조건처럼 블록 재정렬

  📃 CODE

   import copy
  

def change(check): xlen = len(check) ylen = len(check[0])

for j in range(ylen):

    idx = xlen-1
    for i in range(xlen-1,-1,-1):

        if check[idx][j] == '0' and check[i][j]!='0':    
            check[idx][j] = check[i][j]
            check[i][j]='0'
            idx-=1
        elif check[idx][j] !='0':
            idx-=1


return check

def cul(board,cnt): xlen = len(board) ylen = len(board[0]) check = copy.deepcopy(board)

for i in range(xlen-1):
    for j in range(ylen-1):
        if board[i][j] =='0':
                continue;
        if board[i][j] == board[i+1][j] and board[i][j] == board[i+1][j+1] and board[i][j] == board[i][j+1]:

            if check[i][j] != '0':
                cnt +=1
                check[i][j] = '0'
            if check[i][j+1] != '0':
                cnt +=1
                check[i][j+1] = '0'
            if check[i+1][j] != '0':
                cnt +=1
                check[i+1][j] = '0'
            if check[i+1][j+1] != '0':
                cnt +=1
                check[i+1][j+1] = '0'

board = change(check)

return cnt,board

def tolist(get): result = [] for string in get: mid = [] for s in string: mid.append(s) result.append(mid) return result def solution(m, n, board): answer = 0 cnt = 0 becnt = -1 board = tolist(board)

while (becnt != cnt):
    becnt = cnt
    cnt ,board= cul(board,becnt)


return cnt

cul 함수 그냥 for문으로 처리면 되는데 뭔가 귀찮다고 구현 안했더니 코드가 더러워졌다....
다음부턴 그러지말자..

url : https://programmers.co.kr/learn/courses/30/lessons/42883

✔️ 문제 내용

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

❌ 제한 사항

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.

• k는 1 이상 number의 자릿수 미만인 자연수입니다.

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

1. 제한사항에 number =< 1,000,000 임으로 완전탐색은 될 수 없다.(시간초과)
2. 처음에는 two pointer를 활용하려 했으나, 생각해보니 그냥 스택 성질을 이용해 내 앞의 자리가 나보다 작은 수이면 저장된 수를 삭제해주는 방식으로 풀면 될 것 같았다.
3. 위 2번의 조건에서 아래의 조건을 신경써주어야 한다.

• k가 0이 될 때까지만 내 앞의 수가 작은지 봐주어야 한다.

4. 히든 케이스로 뒤의 n개의 숫자가 모두 같아 k가 줄어들지 않는 경우는 따로 처리해주었다 ex(211111, k=2)

   📃 CODE

   def solution(number, k):
   answer = ''
   stack = []
   remain = []
   for s in number:
   
       if k ==0:
           remain.append(s)
           continue
   
       while(1):
           if k == 0:
               stack.append(s)
               break
   
           if len(stack) == 0:
               stack.append(s)
               break
   
           elif int(stack[-1]) < int(s):
               del stack[-1]
               k-=1
           elif int(stack[-1])>= int(s):
               stack.append(s)
               break
   
   

for s in stack:
    answer+=s
for s in remain:
    answer+=s

if k > 0:
    answer = answer[:len(answer)-k]
return answer

url : https://programmers.co.kr/learn/courses/30/lessons/81302

✔️ 문제 내용

제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어 수신 탑(높이)

• 'I 숫자' 큐에 주어진 숫자를 삽입합니다.
• 'D 1' 큐에서 최댓값을 삭제합니다.
• 'D -1' 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

❌ 제한 사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.

• operations의 원소는 큐가 수행할 연산을 나타냅니다.

• 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.

• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

  🖐풀이 방법

  • 프로그래머스에서 LEVEL 2로 되어있다.

  1. 조건에 따라 문제를 정리 하여 풀어주면 된다.
  2. DATA class에 sort가 들어가 있는데 아마 최악의 경우 (명령어가 모두 I일때) 시간이 터질 것이다. (운이 좋았음) heapq를 써서 동기화 시켜서 풀어보는 것이 좋다

  📃 CODE

    class Data:
  
    def __init__(self):
        self.data = []
  
  

def __lt__(self, other):
    return self.data < other.data

def append(self, data):
    self.data.append(data)
    self.data.sort()

def dels(self,idx):
    del self.data[idx]

def solution(operations): answer = [] lis = Data()

for check in operations:
    mid = check.split()

    first = mid[0]
    second = mid[1]

    if first == 'I':
        lis.append(int(second))

    else:
        if len(lis.data)==0:
            continue

        if second == '1':
            lis.dels(-1)
        else:
            lis.dels(0)
if len(lis.data) == 0:
    return [0,0]
return [lis.data[-1],lis.data[0]]

url : https://programmers.co.kr/learn/courses/30/lessons/81302

✔️ 문제 내용

발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다 (정확한 그림까지는 url 확인 부탁드립니다.!)

❌ 제한 사항

• places의 행 길이(대기실 개수) = 5

    - places의 각 행은 하나의 대기실 구조를 나타냅니다.

• places의 열 길이(대기실 세로 길이) = 5

• places의 원소는 P,O,X로 이루어진 문자열입니다.

  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.

• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.

• return 값 형식

  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

  🖐풀이 방법

  • 프로그래머스에서 LEVEL 2로 되어있다.

  1. 단순히 조건을 신경쓰면서 구현해주면 되는 문제였다.
  2. 문제 조건을 아래 열거해보자!
     • X (=벽)은 통과 하지 못한다.
     • 확인하는 장소가 현재 기준이 되는 장소와의 맨허튼 거리가 2이하여야 한다.
  • ps. 조건을 잘못 생각해서 한번 꼬였는데 그때 부터 너무 헬이였다.

📃 CODE

    def check(inner,sx,sy):

    dx = [0,0,1,-1]
    dy = [-1,1,0,0]
    vst = [[0 for i in range(5)] for j in range(5)]

    q = []
    q.append((sx,sy))
    vst[sx][sy] = 1

    while len(q)>0:

        x = q[0][0]
        y = q[0][1]
        q.pop(0)

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx<0 or nx >=5 or ny <0 or ny >=5:
                continue

            if abs(nx-sx)+abs(ny-sy)>2:
                continue

            if vst[nx][ny]==1:
                continue
            if inner[nx][ny]=='X':
                continue

            vst[nx][ny] = 1

            if inner[nx][ny]=='P':
                return False

            q.append((nx,ny))

    return True

def solution(places):
    answer = []

    for place in places:

        flag = True
        for i in range(5):
            if flag == False:
                break

            for j in range(5):

                if flag == False:
                    break

                if place[i][j] =='P':
                    flag = check(place,i,j)


        if flag == False:
            answer.append(0)
        else:
            answer.append(1)

    return answer

• 풀이가 많이 더럽습니다... clean code 꼭하기..