프로그래머스

2024년 3월 8일 알고리즘 문제풀이 문제 완주하지 못한 선수 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 def solution(participant, completion): arr = {} for runner in completion: if runner not in arr: arr[runner] = 1 else: arr[runner] += 1 for player in participant: if arr.get(player): arr[player] -= 1 else: return player n-1개의 참가자 목록을 길이가 n인 리스트에서 탐색할 때 최악의 경우 n*(n-1), O(n**2)의 수행시간이 걸린다. 길이가 n인 리스트에서 1개를 탐색할 때 최악의 경우 n만큼 반복해야 하기 때문. 하지만 dictionary에선 상수의 값이라 O(1)이 n번 소요된다. dictionary에서 in 연산자는 해당 key가 존재하는지 찾아주고 get은 value 값을 반환해준다. ...

2024년 3월 7일 알고리즘 문제풀이 문제 두 정수 사이의 합 난이도 Lv.1 코드 1 2 3 4 5 6 7 def solution(a, b): high = max(a,b) low = min(a,b) answer = 0 for i in range(low,high+1): answer += i return answer

2024년 3월 5일 알고리즘 문제풀이 문제 방금그곡 난이도 Lv.2 코드 언제나 카카오 문제는 일단 문제 이해가 힘들다. 1차 62.9/100 점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 def solution(m, musicinfos): # 정답 음악 제목 answer = '' # 정답 음악이 라디오에서 재생된 시간 answer_t = 0 for x in musicinfos: # 시작 시간, 종료 시간, 음악 제목, 악보 start,end,title,content = x.split(",") # 시작 시와 분 start_h, start_m = start.split(":") # 종료 시와 분 end_h, end_m = end.split(":") # 재생된 시간 계산 playtime = 60*(int(end_h)-int(start_h)) + (int(end_m) - int(start_m)) # 악보를 list화 tmp = list(content) # 재생된 시간이 악보보다 길다면, 악보를 반복한다. while len(tmp) < playtime: tmp += list(content) # 가장 처음부터 len(m)글자씩 보기 위한 반복 for i in range(len(tmp)-len(m)): # i번째글자부터 i+m번째 글자까지 합쳐, 길이가 m과 같은 글자를 만든다 k = "".join(tmp[i:i+len(m)]) if k == m: # 만든 글자가 m과 같지만, 맨마지막에 #이 온다면 정답이 아니다. # "ABC" 를 찾았지만 악보상 "ABC#"으로 되어있다면 찾은 것으로 되겠지만 실제론 찾은게 아니기 때문 # 첫번째 조건문은 그 다음이 #인지 확인할 때, 그 다음이 없을 경우를 위한 설정 if i+len(m)+1 < len(tmp) and tmp[i+len(m)] != "#": # 처음으로 찾은 음악이라면 정답으로 설정 if not answer_t: answer = title answer_t = playtime # 이미 찾은 음악이 있다면, 재생된 시간이 더 길 때만 업데이트한다. # 짧다면 업데이트할 필요가 없다. # 같다면 이미 찾은 음악이 더 먼저 재생되었기 때문에 업데이트할 필요가 없다. else: if answer_t < playtime: answer = title return answer 진짜 너무 복잡하다.. 풀면서도 이게 정답일 것 같지는 않다고 느꼈는데 역시나였다. 조건을 단순화해야한다. #이 붙었을 때를 제대로 처리하지 않은게 문제인듯 하다. ...

2024년 3월 4일 알고리즘 문제풀이 문제 점프와 순간 이동 난이도 Lv.2 코드 일반적인 DP문제라고 생각했다. 조금 어려운 편이긴 하지만, 기존에 충분히 풀어봤던 유형이라 금방 풀 수 있었다. 도착지로 이동하는 마지막 방법을 점프라고 고정하고 생각했다. 1차 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def solution(n): # 3칸까지는 고려할 필요 없음 if n <= 3: dp = [0, 1, 1, 2] return dp[n] # 그 이상일 때는 DP # 가장 최대 건전지 사용량은 그곳까지 점프로만 도달했을 때이므로 모든 곳을 최댓값으로 초기화한다. dp = [] for i in range(n + 1): dp.append(i) # 2,3일 때는 알맞게 초기화 dp[2] = 1 dp[3] = 2 # 4 이상일 때부터 DP for i in range(4, n + 1): # 반으로 나누었을 때 몫 k = i // 2 # 홀수여서 딱 절반인 곳이 존재하지 않을 때 if i % 2: # i까지 도달 비용 = 몫까지 도달하는 비용(dp[j]) + 몫부터 i까지 점프하는 비용(i-j) for j in range(k, i): dp[i] = min(dp[i], dp[j] + i - j) # 짝수여서 절반인 곳이 존재할 때 else: # 절반인 곳에서 순간이동하면 도착할 수 있으므로 절반에 도착하는 것과 같은 값 dp[i] = min(dp[i], dp[k]) for j in range(k + 1, i): dp[i] = min(dp[i], dp[j] + i - j) return dp[n] n칸 까지 갈 때, 절반인 n//2를 기준으로 생각하면 된다. 절반도 오지 못했을 떄 점프를 하는 것은 거기서 순간이동 하는 것보다 더 건전지 사용량이 소모될 것이기 때문이다. 예를 들어, 10 칸을 이동한다고 했을 때 ...

2024년 3월 1일 알고리즘 문제풀이 문제 둘만의 암호 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def solution(s, skip, index): answer = [] alphabet = list('abcdefghijklmnopqrstuvwxyz') n = len(alphabet) def check(num,x): idx = alphabet.index(x) while num: idx += 1 # 알파벳의 끝에 도달하면 맨 처음으로 보냄 if idx == n: idx = 0 result = alphabet[idx] # skip에 포함되지 않을때만 갯수를 셈 if result not in skip: num -= 1 return result arr = list(s) for i in arr: answer.append(check(index,i)) return ''.join(answer)

2024년 2월 29일 알고리즘 문제풀이 문제 하샤드 수 난이도 Lv.1 코드 1 2 3 4 5 6 7 def solution(x): answer = True arr = list(map(int, str(x))) tmp = sum(arr) if x % tmp != 0: answer = False return answer 반복문보단 map 함수를 이용하려고 했다.

2024년 2월 27일 알고리즘 문제풀이 문제 프렌즈4블록 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 def solution(m, n, board): answer = 0 # 시계방향으로 90도 회전하는 함수 # 따라서 n x m 인 배열이 된다. # 블록의 추락도 아래가 아닌 왼쪽으로 발생해야 한다. arr = [[] for _ in range(n)] for k in range(n): for i in range(m-1,-1,-1): arr[k].append(board[i][k]) # 점을 기준으로 오른쪽, 아래, 오른쪽 아래가 모두 동일한지 확인하는 함수 def check(a,b): result = False tmp = arr[a][b] if arr[a+1][b] == tmp and arr[a][b+1] == tmp and arr[a+1][b+1] == tmp: result = True return result # 점을 기준으로 오른쪽, 아래, 오른쪽 아래 4개를 지우는 함수. # 지워지는 블록이 다른 곳과 겹칠 경우를 대비하여, 실제 지워진 갯수를 계산하여 반환 def delete(a,b): result = 0 if arr[a][b] != '0': arr[a][b] = '0' result += 1 if arr[a+1][b] != '0': arr[a+1][b] = '0' result += 1 if arr[a][b+1] != '0': arr[a][b+1] = '0' result += 1 if arr[a+1][b+1] != '0': arr[a+1][b+1] = '0' result += 1 return result # 90도 회전하였기 때문에, 왼쪽으로 블록이 떨어지는 함수 구현 # 각 행마다, 비어있는 열을 발견할 경우 오른쪽을 탐색하여 떨어질 블록을 찾아 바꿔준다. # 한 칸씩 떨어뜨리면, 여러 블록을 떨어뜨리는 경우가 복잡해진다. def fall(): for i in range(n): for j in range(m): if arr[i][j] == '0': for k in range(j+1,m): if arr[i][k] != '0': arr[i][j] = arr[i][k] arr[i][k] = '0' break # '0'이 아니라는 조건을 추가하지 않으면 무한루프가 실행된다. while True: delete_list = [] for i in range(n-1): # 여기가 1,m 이면 테스트 5가 실패함 for j in range(m-1): if arr[i][j] != '0' and check(i,j): delete_list.append([i,j]) if not delete_list: break for a,b in delete_list: tmp = delete(a,b) answer += tmp fall() return answer 겁나 힘들게 풀었다… 기존에는 위와 같이 풀되, 90도로 회전하지 않았다. 이떄 발생하는 어려움은 블록을 부수고 떨어뜨리는 것을 구현하기 힘들었다. 위에서 아래로 떨어뜨릴 경우 같은 열이지만 다른 행인 원소들간의 비교가 이루어져야 한다. 위 각주에서도 말했지만 한 칸씩 옮길 경우 2개가 같이 떨어질 떄나, 여러 칸을 떨어뜨리는 경우의 수는 상당히 복잡하기 때문에 구현이 힘들었다. 추락을 같은 List 안에서 발생하도록 하면 훨씬 편해질 것이라고 생각해서 배열을 90도 회전하였다. ...

2024년 2월 26일 알고리즘 문제풀이 문제 크레인 인형뽑기 게임 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 def solution(board, moves): n = len(board) stk = [] answer = 0 # 열에서 가장 위에 있는 인형을 찾는 함수 # 찾으면 board에서 0으로 바꾸고 반환 def first_target(row): for i in range(n): if board[i][row]: result = board[i][row] board[i][row] = 0 break else: result = False return result # 인형이 있을 때, 이미 들어있는 인형과 동일하면 2개 제거, 아니면 추가 for x in moves: row = x-1 tmp = first_target(row) if tmp: if stk: if stk[-1] == tmp: stk.pop() answer += 2 continue stk.append(tmp) return answer

2024년 2월 23일 알고리즘 문제풀이 문제 짝지어 제거하기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(s): arr = list(s) stk = [] for i in range(len(s)): if not stk: stk.append(arr[i]) continue else: if stk[-1] == arr[i]: stk.pop() else: stk.append(arr[i]) if not stk: answer = 1 else: answer = 0 return answer

2024년 2월 22일 알고리즘 문제풀이 문제 정수 내림차순으로 배치하기 난이도 Lv.1 코드 1 2 3 4 5 6 7 def solution(n): arr = list(str(n)) map(int,arr) arr.sort(reverse=True) map(str,arr) answer = ''.join(arr) return int(answer)