NAIAHD

출처 : 

https://school.programmers.co.kr/learn/courses/30/lessons/181832

오른방향 -> 아래방향 -> 왼쪽 방향 -> 윗방향 -> 오른방향 .. 이런식으로 진행한다 

다음의 값이 0이 아닌 것을 체크하여 진행한다.

def solution(n):
    answer = [[0 for i in range(n)] for j in range(n)]
    num = 1
    i,j = 0,0
    dir = "right"
    while num < (n * n + 1):
        answer[i][j] = num
        # 오른쪽으로 진행 
        if dir == "right":
            if (j < n - 1) and (answer[i][j+1] == 0):
                j += 1
            else:
                dir = "down"
                i += 1
        elif dir == "down":
            if (i < n - 1) and (answer[i+1][j] == 0):
                i += 1
            else:
                dir = "left"
                j-= 1
        elif dir == "left":
            if (j > 0) and (answer[i][j-1] == 0):
                j -= 1
            else:
                dir = "up"
                i -= 1
        else:
            if (i > 0) and (answer[i-1][j] == 0):
                i -= 1
            else:
                dir = "right"
                j += 1
        num += 1
        #print(answer)
        
            
    return answer

출처 : 프로그러머스

문제 설명

프렌즈4블록

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

mnboardanswer

4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

해설 보러가기

문제를 보고 3가지 부분으로 나누었다. 

1. 4개 짜리 있는 부분 list에 담기

2. 4개 있는 list를 순환하여 그 부분 ' ' 으로 채우기 

3. 마지막에 중요하다고 느낀 것은 이부분이다. 아래로 미루는 부분에서 많이 틀린 경우가 많다. 이 경우 초반에 잘못해서 5,10이 틀렸다. 

def solution(m, n, board):
    answer = 0
    board = [[j for j in i ] for i in board ]
    while True:
        list_= []
        # 4개 있는 점 찾기 
        for i in range(m-1):
            for j in range(n-1):
                if board[i][j] != ' ' and (board[i][j] == board[i+1][j] == board[i+1][j+1] == board[i+1][j+1]== board[i][j + 1]):
                    list_.append((i+1,j+1))
                    list_.append((i+1,j))
                    list_.append((i,j+1))
                    list_.append((i,j))        

        # 4개 있는 곳 지워주기 
        answer += len(set(list_))
        if len(list_) == 0:
            return answer
        for i,j in list_:
            board[i][j] = ' '
        
        # 보드를 아래 루 내리기
        while True:
            moved = False
            for i in range(1, m):
                for j in range(n):
                    if board[i-1][j] != ' '  and board[i][j] == ' ':
                        board[i][j] = board[i-1][j]
                        board[i-1][j] = ' '
                        moved = True
            if not moved:
                break
    return answer

m = 4
n = 5
board = ["CCBDE", "AAADE", "AAABF", "CCBBF"]
solution(m, n, board)

5점 

출처 : 프로그래머스

문제 설명

answer = 0
def enter_dungen(dungeons, k, idx, visited):
    global answer
    k -= dungeons[idx][1] # 소모 피로도를 줄인다. 
    answer = max(answer, sum(visited))
    
    for idx_2, val_2 in enumerate(dungeons):
        #print(idx, idx_2, val_2)
        if not visited[idx_2] and  k >= val_2[0]:  # 방문하지 않고 소모도가 클 경우 
            visited[idx_2] = 1
            enter_dungen(dungeons, k, idx_2, visited)
            visited[idx_2] = 0
    return answer
    
def solution(k, dungeons):
    for idx, val in enumerate(dungeons):
        visited = [0] * len(dungeons) # 합을 계산하기 쉽게 하였다 
        if k >= val[0]:# 처음이여서 소모도가 클 경우 
            visited[idx] = 1
            enter_dungen(dungeons, k, idx, visited)
            visited[idx] = 0
    return answer


k = 80
dungeons = [[80,20],[50,40],[30,10]]
solution(k, dungeons)

출처 : 프로그래머스

• H-Index

위키백과 의 h-index의 정의를 보는 것이 잴 빠르다. 

예에서 [3, 0, 6, 1, 5] 정렬 후 처리 

def solution(citations):
    citations.sort(reverse = True)

    answer = 0
    for idx, val in enumerate(citations):
        if idx + 1 <= citations[idx]:
            print(idx+1, idx, citations[idx])
            answer = idx + 1
    return answer

citations = [3, 0, 6, 1, 5]
print(solution(citations))

 출처 : 프로그래머스

def solution(operations):
    answer = []
    operations_after = []
    for operation in operations:
        opr, number = operation.split(" ")
        if opr == "I":
            operations_after.append(int(number))
        elif opr == "D" and number == "-1" and len(operations_after) > 0:
            operations_after.remove(min(operations_after))
        elif opr == "D" and number == "1" and len(operations_after) > 0:
            operations_after.remove(max(operations_after))
    opr_max = 0
    opr_min = 0
    if len(operations_after) >= 2:
        opr_max, opr_min = max(operations_after), min(operations_after)
    elif len(operations_after) == 1:
        if max(operations_after) < opr_max:
            opr_min = max(operations_after)
        else:
            opr_max = max(operations_after)
    answer.append(opr_max)
    answer.append(opr_min)
    return answer

#operations = ["I 16","D 1"]
operations = ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]
print(solution(operations))
#operations= ["I 7","I 5","I -5","D -1"]
operations = 	["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
print(solution(operations))

출처 : 프로그래머스

• 디스크 컨트롤러

문제 설명

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

예를들어

- 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 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예jobsreturn

[[0, 3], [1, 9], [2, 6]]

9

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

import heapq

def solution(jobs):
    answer = 0
    # [작업이 요청되는 시점, 작업의 소요시간]
    heapq.heapify(jobs)
    jobs_sort = sorted(jobs , key=lambda x : (x[1]))
    
    start = 0
    while jobs_sort:
        for idx, val in enumerate(jobs_sort):
            if jobs_sort[idx][0] <= start:
                start += jobs_sort[idx][1]
                answer += start - jobs_sort[idx][0]
                jobs_sort.pop(idx)
                break

            if idx == len(jobs_sort) - 1:
                start += 1

    return answer // len(jobs)

jobs = 	[[0, 3], [1, 9], [2, 6]]
solution(jobs)
# 테스트 20 만 성공

https://codermun-log.tistory.com/305

출처 : 프로그래머스 

문제 설명

from collections import deque
def solution(prices):
    answer = []
    queue = deque(prices)
    while queue:
        price = queue.popleft()
        cnt = 0
        for i in queue:
            cnt += 1
            if i < price:
                break
        answer.append(cnt)
    return answer

prices = [1, 2, 3, 2, 3]
solution(prices)

출처 : 프로그래머스

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn

출처

※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.

# bridge_length 다리 길이 2일 경우 2
def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge_truck = [0] * bridge_length # 다리를 건너는 트럭
    while len(bridge_truck) != 0:
        answer += 1
        bridge_truck.pop(0)
        if truck_weights:
            if sum(bridge_truck) + truck_weights[0] > weight:
                bridge_truck.append(0)
            else:
                truck_weight = truck_weights.pop(0)
                bridge_truck.append(truck_weight)
            #print(bridge_truck)
    return answer

bridge_length = 2
weight = 10
truck_weights = [7,4,5,6]
solution(bridge_length, weight, truck_weights)

참조 :

https://donis-note.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A4%EB%A6%AC%EB%A5%BC-%EC%A7%80%EB%82%98%EB%8A%94-%ED%8A%B8%EB%9F%AD-python-8d03d1ac2a45