Algorithm Problem

[python] 프로그래머스 - 110 옮기기(월간 코드 챌린지 시즌2)

🤔문제 해결 1. 모든 110 찾기 2. 나머지에 0이 있으면 그 0뒤에 110 다 붙이고 3. 0이 없으면 앞에 110을 다 붙인다 월코챌 해설지 보고 풀었는데 답 구하는게 헷갈려서 많이 고민한 문제 💻소스 코드 def solution(s): answer = [] for x in s: # 모든 110 찾기 # 110 찾으면 변형된 x에서 또 찾기 one_one_zero_cnt = 0 stack = [] for x_one in x: if x_one == '1': stack.append(x_one) else: if len(stack) >= 2 and stack[-1] == '1' and stack[-2] == '1': stack.pop() stack.pop() one_one_zero_cnt += 1 els..

[python] 프로그래머스 - 스타 수열(월간 코드 챌린지 시즌1)

🤔문제 해결 1. 주어진 배열의 숫자의 개수를 센다. -> Counter 라이브러리 이용 2. 주어진 배열에서 꺼낸 숫자의 인덱스를 구한다. 3. 구한 인덱스의 왼쪽 or 오른쪽의 숫자를 적절하게 사용할 수 있는지 판단하고 스타 수열을 만든다. 💨 Counter 라이브러리 대신 { 1: [0, 3, 6, 9], ... } 이런식으로 인덱스를 넣어줘서 길이와 인덱스를 한꺼번에 알기 쉽게하는 방법도 봤다. 💨 중간 중간 길이가 짧은 애들을 끊어주지 않으면 시간초과 날 것 같다. 💻소스 코드 from collections import Counter def solution(a): # 주어진 배열의 숫자의 개수를 구한다. number_cnt = Counter(a) answer = 0 # 구한 숫자를 하나 씩 꺼내..

[python] 프로그래머스 - 교점에 별 만들기(위클리 챌린지)

🤔문제 해결 💨 교점 구하기 -> 문제에서 주어진 공식으로 모든 교점을 구한다. 💨 배열 크기 정하기 -> x, y 의 최대 최소값으로 💨 배열 만들기 -> 배열을 만든다. 💨 별 찍기 -> 왜 좌표가 (y_max - y, x - x_min) 인지 헷갈릴 수 있다. 수학 좌표랑 배열로 나타내는 좌표의 0점이 다르기 때문에 적절하게 바꿔줘야한다. 💻소스 코드 def solution(line): dot_list = [] for i in range(len(line)): A, B, E = line[i] for j in range(i + 1, len(line)): C, D, F = line[j] bunja = A * D - B * C if int(bunja) == 0: continue x = (B * F - E ..

[python] 프로그래머스 - 빛의 경로 사이클(월간 코드 챌린지 시즌3)

🤔문제 해결 💨 문제에서 시키는대로 그대로 풀었다. (구현) 💫 visited 라는 3차원 배열을 만든다. 제일 안쪽의 원소에는 'U','D','R','L' 이 들어갈 수 있는데 해당 위치(i, j) 에서 이동한 방향을 담고 있다. 싸이클이 다르면 절대로 이동경로가 하나라도 똑같은게 나올 수 없기 때문에. 이동할 때 UDRL 이 있는지 확인을 하고 이동한다. 💻소스 코드 def solution(grid): answer = [] N, M = len(grid), len(grid[0]) visited = [[set() for _ in range(M)] for _ in range(N)] # U, D, L, R for i in range(N): for j in range(M): for k in 'UDLR': cn..

[python] 프로그래머스 - n^2 배열 자르기(월간 코드 챌린지 시즌3)

🤔문제 해결 💨 규칙을 찾아내는 수학문제? 같은 느낌, 문제의 설명대로 풀면 10^7 이므로 시간초과 발생.... 좌표를 활용하여 문제풀이 💫 빈 배열에 숫자를 넣는 공식은 행(i), 열(j) 의 최대값 + 1 💫 ex) 0행 2열의 값은 3, 1행 0열의 값은 2 💫 그림(4 x 4 행렬)에서 left(7) 부터 right(14) 는 [1,3] 부터 [3,2] 💫 좌표를 구하는 방법은 left = [7//4, 7%4] = [1, 3] 💫 결국 풀이는 좌표를 구해서 그 지점의 숫자를 결과 배열에 넣어주면 된다. 💻소스 코드 def solution(n, left, right): answer = [] for i in range(left, right + 1): answer.append(max(i // n, i..

[python] 프로그래머스 - 피로도(위클리챌린지)

🤔문제 해결 💫 던전의 길이가 최대 8개 이므로 permutation으로 탐험하는 순서의 모든 경우의 수를 구했다. 💫 탐험 순서대로 던전을 탐험하며 피로도 조건에 맞는 동굴만 탐험하며 갯수를 세어준다. 💫 각각의 사이클마다 탐험가능한 동굴의 갯수를 최대값으로 업데이트 해준다. 💻소스 코드 from itertools import permutations def solution(k, dungeons): answer = -1 for perm in (permutations(dungeons, len(dungeons))): cur_k = k expol_cnt = 0 for dungeon in perm: if cur_k >= dungeon[0]: expol_cnt += 1 cur_k -= dungeon[1] answ..