Problem Solving (programmers)

LV2: 요격 시스템targets를 오름차순으로 정렬curr 변수를 이용해 count를 증가시켜야하는 지, 증가시키지 않아도 되는 지를 판별해준다\-> start가 curr보다 작다면, curr과 end값 중 더 작은 값으로 curr을 갱신\-> start가 curr보

LV 2: 두 원 사이의 정수 쌍한 사분면만을 구하고, \*4를 통해 최종 값을 구해야한다\-> 이 때, 2중 for문을 통해 계산하게 되면 r2, r1이 1000000 이하이기 때문에 TLE를 받는다x축을 기준으로 순회하는 방식으로 풀었다원의 방정식: y = sqrt

LV 2: 미로 탈출"출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러번 지나갈 수 있다." 라는 조건 때문에, bfs 한 번에 처리해주기가 쉽지 않았다1)시작점 -> 레버, 2)레버 -> 출구로 가는 경로를 설정해주고 bfs

LV 2: 연속된 부분 수열의 합투 포인터 알고리즘을 적용하여 풀었다start와 end가 0을 가리키도록 한다part_sum이 k보다 작다면 end를 1 증가시킨다part_sum이 k와 같다면, result에 수열의 길이와 start, end를 추가해준다part_sum

LV 2: 리코쳇 로봇예전에 백준에서 불었던 "구슬 탈출"문제와 비슷한 유형이었다한 방향으로 움직일 때 미끄러지듯이 이동하기 때문에, 각 방향으로 움직이는 부분을 move 함수를 통해 따로 구현해줬고, 최소 이동 횟수를 구해야하므로 bfs를 이용했다

LV 2: 숫자 변환하기간단한 bfs 문제였다queue에 값을 넣는 조건만 조금 생각해주면 된다visit을 set으로 정의하고, dest의 값이 visit에 없고, dest가 y 이하라면 그 다음 depth로 넘어갈 수 있다

LV 2: 뒤에 있는 큰 수 찾기스택으로 구현하려다가 시간초과가 나서 최소힙을 이용하여 구현해주었다numbers를 순서대로 순회하면서, 매 회마다 numbersi의 값을 heap에 넣어준다heap의 가장 작은 원소가 현재 numbersi보다 작을 때까지 heappop을

LV 2: 주식 가격2중 for문을 돌아서 풀었다바로 다음에 가격이 떨어져도 떨어지지 않은 기간이 1초가 되므로 자기자신과도 비교를 해준다\-> 마지막 원소는 어차피 0초이므로 비교 대상에서 제외해준다

LV 2: 무인도 여행 bfs로 풀어주었다

LV 2: 호텔 대실rooms라는 이름의 List를 이용해 현재 필요한 객실의 상황을 나타내주었다book_time을 오름차순으로 정렬하고 index 1부터 순회rooms의 길이만큼 rooms를 순회하며, 만약 존재하는 방을 이용할 수 있다면 해당 방을 이용하고 종료 시

LV 2: 시소 짝궁from collections import defaultdictdefaultdict(int) -> 초기값을 0으로 설정defaultdict(set) -> 초기값을 빈 set으로 설정defaultdict(list) -> 초기값을 빈 list로 설정we

LV 2: 디펜스 게임 최대 힙을 이용해서 만약 n이 0보다 작은 경우가 발생하면, 이전 라운드들 중 적의 수가 가장 큰 라운드에 대해서 무적권을 써주는 방식으로 풀어주었다 이전 라운드에 무적권을 써줄 때는, 해당 라운드의 적의 수만큼 n을 증가시켜주고, k를 1 감

LV 2: 게임 맵 최단 거리 bfs로 풀어주었다

LV 2: 귤 고르기"크기":"개수" 형식으로 count 딕셔너리를 완성count.items()를 list로 변환한 후, 내림차순 정렬count를 순회하는 과정에서 k가 0이하가 될때까지 넘어가는 index+1이 구하고자하는 정답이 된다

LV 2: 행렬 테두리 회전하기백준에서 자주 다뤘던 내용이다위쪽, 오른쪽, 아래쪽, 왼쪽 순서대로 queue에 extend 메소드를 이용해 껍데기를 채워준다위쪽, 오른쪽, 아래쪽, 왼쪽 순서대로 for문을 돌며 queue에서 popleft한 결과를 arr에 채워준다조금

LV 2: 마법의 엘리베이터처음에 backtracking으로 풀려했으나, recursion limit error가 발생했다이 문제는 storey의 자릿수를 줄여가며 1)6~9라면 올려주고, 2)0~4라면 내려주고, 3)5라면 다음 자릿수를 기준으로 올릴지 내릴지 정

LV 2: 다음 큰 숫자처음에 규칙을 찾아서 조건문 분기로 풀어보려 했으나, 쉽지 않았다이 문제는 그냥 1) 1의 개수가 이진수의 길이와 같은 경우(이진수가 모두 1로 이루어짐), 2) 1의 개수가 이진수의 길이와 같지 않은 경우(이진수가 0과 1로 이루어짐)로 나누어

LV 2: 연속 부분 수열 합의 개수완전 탐색으로 풀어주었다처음에는 3중 for문으로 구현해주었는데, elements의 길이가 1000 이하여서 TLE를 받았다elements를 인덱스 0부터 순회하면서, sum_set에 연속 부분 수열 합을 add 해주는 방식으로 구현

평범한 dfs를 이용한 brute force 문제이다 프로그래머스에서 전역변수(global) 사용하려면 solution 함수 밖에서 한번 쓰고자하는 변수를 define 해줘야한다

LV 2: N-Queen이전에 백준에서 풀었던 N-Queen 문제와 동일하다프로그래머스에서 다시 풀 때 조금 억까였던게, dfs에서 다음 depth로 넘어가야할 지 말아야할 지를 판별하는 부분을 adjacent(r) 함수로 빼서 코드를 짜면 테케 11번에서 TLE을 받

LV 2: 테이블 해시 함수문제에서 요구하는 대로 해시 값을 구해주면 된다

LV 2: 피로도len(dungeons)가 1이상 8이하이기 때문에 permutations를 이용해서 완전 탐색으로 풀었다

LV 2: 점 찍기k가 1이고, d가 1,000,000인 경우에 2중 for문을 돌면 TLE를 받는다순회를 x축 기준으로 한다면 1중 for문으로 구현할 수 있음\-> x값에 따른 y는 int(sqrt(abs(d\*\*2 - x\*\*2))로 구할 수 있고, 해당 값을

LV 2: 택배상자 무지성 조건문 분기로 풀었다 일단 order의 길이가 1,000,000 이하이기 때문에 1중 for문으로 구현해주어야 한다o_idx는 order의 상자 번호를 가리키고, order를 순회하는 for문을 기준으로 잡았다 belt를 1, 2, 3, 4,

LV 2: 더 맵게 두 개의 음식을 섞는 방법: 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) -> 정렬된 순서를 유지해야하는 경우이므로 최소힙을 이용해 풀어주었다

LV 2: 최솟값 만들기가장 큰 수가 가장 작은 수와 곱해지도록 해야한다\-> A를 오름차순으로, B를 내림차순으로 정렬한 후 이 둘을 순서대로 곱해주면 최적의 해가 된다

LV 2: 숫자의 표현자연수 n을 연속한 자연수들의 합으로 나타내주는 과정을 queue를 이용해 구현해주었다

LV 2: 모음사전규칙을 찾아보려 했으나 쉽지 않았다수가 증가하는 모양을 잘 보면, 재귀 형식임을 알 수가 있다따라서 dfs로 완전탐색 해주었다\-> count를 global로 선언하고 A부터 순서대로 dfs 호출하여 count 갱신. True가 반환된다면 바로 cou

LV 2: JadenCase 문자열 만들기문제에서 하라는 대로 하면 된다string.upper() -> 문자열을 대문자로 변경string.lower() -> 문자열을 소문자로 변경string.isupper() -> 문자가 대문자인지 확인 (문자열의 모든 문자가 대문자인

LV 2: 짝지어 제거하기 처음 접근했을 땐 while문을 돌면서 처리해줘야하나? 싶었지만 문자열의 길이가 1,000,000 이하인 관계로 웬만하면 O(n)안에 처리를 해줘야한다 stack을 이용하면 1중 for문으로 해결할 수 있는데 조건문을 분기할 때 조금

LV 2: 숫자 카드 나누기먼저 arrayA의 최대공약수 gcdA, arrayB의 최대공약수 gcdB를 구해줌각각 arrayA와 arrayB를 순회하면서, gcdA가 arrayB의 원소를 나누는 경우가 있으면 flagA를 False로, gcdB가 arrayA의 원소를

LV 3: 아이템 줍기좌표 개념으로 바꿔서 탐색해야하기 때문에, 지형의 크기를 두배 늘려주었다board를 51\*2 \* 51\*2 크기의 bool type 리스트로 선언 (초기값: False)직사각형의 테두리 및 내부를 모두 True로 바꿔주고직사각형의 테두리만 남기

LV 3: 단어 변환bfs로 풀어주었다시간 제한 조건이 빡빡하진 않아서 한 큐에 통과됐다

LV 2: 롤케이크 자르기처음에 이렇게 짰는데 두개 빼고 다 TLE 뜸 (N도 1,000,000 이하라 통과될 줄 알았는데 list -> set type 변환이 시간이 오래걸리는 연산인듯)그래서 두 개의 dictionary를 이용해서 처리해주었다Counter()를 이용

LV 2: 튜플먼저, s는 문자열이기 때문에 이를 파싱해줘야함우선 s를 '},{'로 split 해줌s_set에 파싱한 결과를 할당s_set을 길이를 기준으로 오름차순으로 정렬s_set을 순회하며, result를 완성시킴{{2, 1, 3, 4}, {2}, {2, 1, 3

LV 2: 거리두기 확인하기 대기실(board)을 2중 for문으로 순회하며, boardi == 'P'인 경우에 check 함수를 호출한다

LV 2: n^2 배열 자르기처음에 2차원 배열 만들어서 slicing 했더니 TLE를 받음배열을 직접 만들지 말고 수식으로 풀어야함left ~ right까지 순회하면서 i%n과 i//n 중 큰 값을 result list에 append

LV 3: 네트워크무난한 find-union 문제이다주의해야할 점: union을 수행한다고해서, 항상 모든 parent에 항상 가장 작은 부모노드가 저장되는 것은 아님더 큰 부모에 작은 부모가 할당되었으니 작은 노드쪽으로 union이 수행된 건 맞으나, find()를

LV 2: 두 큐 합 같게 만들기while문을 돌면서, 1)queue1의 총합이 queue2의 총합보다 크다면 queue1에서 popleft, queue2에 append. 2)queue2의 총합이 queue1의 총합보다 크다면 queue2에서 popleft, queue

LV 3: 다단계 칫솔 판매전반적으로 find-union 형식으로 구현해주었다graph는 child를 key로, parent를 value로 설정하여 dictionary로 선언해주었고, all_profit 역시 dictionary로 선언해주었다distribute(node

LV 2: 전력망을 둘로 나누기brute force + find-union을 이용해서 풀어주었다wires의 길이만큼 for문을 돌면서 현재 위치의 wire를 끊어준다면 송전탑이 트리 형태로 연결되어 있기 때문에, 두 개의 전력망으로 나뉘게 된다전력망을 끊어준 후, 매

LV 3: 순위각 노드에서, 자신의 노드를 포함하여 자신을 이긴 노드와 자신에게 진 노드의 개수가 n+1이 된다면 정확하게 순위를 매길 수 있다는 아이디어를 참고했다win_graph는 key - value의 관게가 '이긴 선수 - 진 선수'인 그래프이다lose_grap

LV 2: 가장 큰 정사각형 찾기 처음에 좌표를 한 칸씩 이동하면서 backtracking 방식으로 풀어보려 하였으나, row와 column의 크기가 1000이하인 관계로 TLE가 떴다 dp를 이용해서 풀어주었다 row의 크기를 N, c

LV 2: 가장 큰 수처음에는 그냥 각 숫자를 list로 변환하고 nums.sort(reverse=True)로 sorting하면 될 줄 알았는데, 3, 0이 3보다 앞에 오는 게 문제였다\-> number가 1,000 이하의 수라는 점을 이용하여 3번 이어 붙인 값의

LV 2: 스킬트리문제에서 안내한대로 구현해주면 된다step_set (set type)을 이용해서 검사를 해야할지 안해도 될지를 판단해주었다possible_index를 이용해서 스킬순서에서 몇번째까지 배웠는지를 표시해주었다possible_flag를 이용해서 가능한 스킬

LV 2: H-IndexH-Index에 대한 설명이 이해하기 좀 머리아팠는데,그냥 citations의 최댓값( = H-Index의 후보중 최댓값)부터 0까지 역순으로 for문을 돌면서, h값이 H-Index의 조건을 만족하는 지 확인해주면 된다. 만족한다면 역

LV 2: 방문 길이문제에서 안내한대로 구현해주면 된다d라는 dictionary를 이용해 각 명령어 'U', 'D', 'R', 'L'를 해당하는 변위값으로 바로 변환할 수 있게 해주었다visit라는 set을 이용해 해당 길이 처음 걸어본 길인지 아닌지를 판별해주었다이

LV 2: 괄호 회전하기stack을 이용하는 무난한 구현문제이다list 회전은 그냥 deque의 rotate 메소드를 사용했다 (반시계방향: .rotate(-1))처음에 TC 13번에서 통과가 되지 않았는데, 마지막에 stack이 비어있는 지를 확인해줘야했다

LV 3: 부대복귀destination에서 각 source로 가는 방향으로 bfs를 수행해주었다양방향 그래프를 생성하기 위해 edges라는 이름의 dictionary를 이용했다중복 방문 노드 제거를 위해 visit이라는 이름의 set을 이용했다

LV 3: 인사고과 scores를 근무태도점수에 대해 내림차순, 동료평가점수에 대해 오름차순으로 정렬 -> 이렇게 해주면, 뒤에 나온 학생의 동료평가점수가 앞에 나온 어떤 학생의 동료평가점수(max_b)보다 크거나 같을 때에만 인센티브를 받을

LV 3: 여행경로dfs(백트래킹)을 이용해서 풀어주었다visit 처리가 좀 중요했는데, visit을 tickets 크기의 1차원 배열로 선언해주고 매번 tickets를 순회해주면서 조건에 만족하는 경우 재귀 호출 해주었다

LV 3: 경주로 건설처음에 그냥 bfs로 풀으려하였으나, 최단거리만 찾아질 뿐 최소비용이 구해지지 않았다이 문제는 bfs+dp 문제이다.dp table을 3차원으로 선언해주었다방향마다 dp table을 나누어, directiony 형식으로 생성해줌처음에 queue에