프로그래머스

2024년 3월 28일 알고리즘 문제풀이 문제 다트 게임 난이도 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 def solution(dartResult): idx = 0 scores = [] # while문 1회 마다 1차례의 결과를 체크 while idx < len(dartResult): # 점수 부분을 담을 변수 tmp = 0 # 문자열이 숫자 부분이라면 점수를 의미 if dartResult[idx].isdigit(): # 그 다음 문자도 숫자라면 10이라는 의미이므로 2글자 모두 담는다. if dartResult[idx+1].isdigit(): tmp = int(dartResult[idx]+dartResult[idx+1]) # 다다음 글자를 보기위해 index 증가 idx += 2 # 아니면 1자리 숫자이므로 1글자만 담는다. else: tmp = int(dartResult[idx]) # 다음 글자를 보기위해 index 증가 idx += 1 # 알파벳이 나오면 보너스를 의미 if dartResult[idx].isalpha(): if dartResult[idx] == 'D': tmp = tmp**2 elif dartResult[idx] == 'T': tmp = tmp**3 # 다음 글자를 살피기 위해 idx 증가 idx += 1 scores.append(tmp) # 옵션은 없을수도 있음 # 마지막 차례에 옵션이 없어서 더이상 글자가 없을 경우를 고려하여 예외처리가 필요 if idx >= len(dartResult): break # 옵션이 있다면 if dartResult[idx] in ['*','#']: # 스타상의 경우 가장 최근 점수의 2배 증가 if dartResult[idx] == '*': scores[-1] = 2*scores[-1] # 첫번째 다트 기회에 스타상이 나올 경우에는 그 이전 점수는 증가시키지 않음 # 따라서 그 이전 점수가 존재할때만 그것도 2배 증가 if len(scores) > 1: scores[-2] = 2*scores[-2] # 아차상은 그 전점수의 부호를 변경 else: if scores: scores[-1] = -1*scores[-1] idx += 1 return sum(scores)

2024년 3월 28일 알고리즘 문제풀이 문제 서울에서 김서방 찾기 난이도 Lv.1 코드 1 2 3 4 def solution(seoul): answer = '' answer = str(seoul.index('Kim')) return f"김서방은 {answer}에 있다"

2024년 3월 26일 알고리즘 문제풀이 문제 압축 난이도 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 def solution(msg): answer = [] alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' arr = dict() for i in range(len(alphabet)): arr[alphabet[i]] = i+1 # 다음 추가될 색인 번호는 마지막보다 1 큰 수 last_num = len(alphabet)+1 # idx까지 볼때 idx-1 까지만 포함되므로 1로 설정 idx = 1 n = len(msg) while idx <= n: # 이미 있다면 다음이 더 긴지 확인하기 위해 idx만 1 증가 if msg[:idx] in arr: idx += 1 continue else: # 사전에 없다면, 길이가 1 작을 때가 가장 긴 단어이므로(2단계) 그 번호를 출력 answer.append(arr[msg[:idx-1]]) # 없는 단어와 색인 번호를 추가 arr[msg[:idx]] = last_num # 다음 추가될 색인 번호 1 증가 last_num += 1 # 찾아낸 가장 긴 단어는 삭제 msg = msg[idx-1:] # 인덱스 오류를 방지하기 위해 매 반복마다 길이 체크 n = len(msg) # 인덱스 초기화 idx = 1 # 마지막 반복 때 사전에 있는 단어로 끝났다면 추가되지 않는 단어가 생기므로 추가 # KAKAO에서 마지막 O는 별도로 추가해야함 if msg: answer.append(arr[msg]) return answer 매 번 느끼는 거지만, 문제가 길 때(특히 카카오)는 차근차근 시키는대로 하는게 정답이다. ...

2024년 3월 25일 알고리즘 문제풀이 문제 대충 만든 자판 난이도 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 def solution(keymap, targets): answer = [] arr = dict() idx = 0 # 각 글자를 입력하기 위한 버튼 누르는 횟수의 최솟값을 저장하는 배열 arr을 만드는 과정 # 각 버튼의 0번 index 부터 하나씩 참조 while True: # 모든 키의 입력 범위를 넘어갔는지 확인하기 위한 플래그 flag = False # 모든 버튼 순회 for button in keymap: # 예를 들어, 버튼을 5번 누를 수 있는데 idx가 6이라면 그 버튼은 더이상 조사할 필요가 없으므로 넘어감 if idx >= len(button): continue # 어떤 버튼을 참조했음을 플래그에 표시. 이 과정이 없으면 keymap중 가장 긴 버튼의 길이를 구하느 과정이 따로 필요 flag = True # idx번 눌렀을 때 해당 버튼에서 입력되는 글자 letter = button[idx] # 지금 입력되는 글자가, 아직 입력된적 없는 글자라면 배열에 추가 if letter not in arr: arr[letter] = idx+1 # 이미 입력된적 있다면, idx를 작은 값으로 바꿔줌. 각 글자를 누르는 최소 방법만 알면 되기 때문 # 0번 인덱스는 1번 눌러야 하므로 idx+1을 저장 else: arr[letter] = min(arr[letter],idx+1) # 아무 버튼도 탐색하지 않았다면 무한루프 종료 if not flag: break idx += 1 for target in targets: cnt = 0 # 타겟을 하나씩 탐색하며 글자를 확인 for i in range(len(target)): # 만약 글자를 입력할 방법이 있다면 해당 키의 값을 추가 if target[i] in arr: cnt += arr[target[i]] # 글자를 입력할 방법이 없다면 -1로 지정하고 종료 else: cnt = -1 break answer.append(cnt) return answer

2024년 3월 18일 알고리즘 문제풀이 문제 다리를 지나는 트럭 난이도 Lv.2 코드 1차 42.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 from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 # 다리를 표현하기 위한 덱 in_bridge = deque() # 다리의 길이와 트럭의 위치를 표현하기 위해 트럭이 없는 곳은 0인 원소로 채운다. for _ in range(bridge_length): in_bridge.append(0) for truck in truck_weights: # 현재 다리에 지금 주목하는 트럭이 올라가면 무게 제한을 초과할 경우 # 가장 끝에 있는 원소를 빼낸다. 트럭일 수도, 빈 값(0)일 수도 있다. # 0번 인덱스가 빠지고 하나가 추가되기 때문에 모든 원소들의 index는 1씩 줄어든다. # 따라서 다리 위의 모든 트럭이 1칸 움직이는 것을 의미한다. while sum(in_bridge)+truck > weight: outgoing_truck = in_bridge.popleft() in_bridge.append(0) answer += 1 # 만약 실제로 트럭이 빠졌다면, 이와 동시에 새로운 트럭이 올라올 수 있다. # 새로운 트럭이 올라오는 행위는 동시에 일어나므로 시간이 흐르지 않은것으로 치기 위해 뺸다. if outgoing_truck: answer -= 1 # 다리에 새로운 트럭이 올라올 수 있다면 올려준다. if sum(in_bridge)+truck <= weight: # 잘못된 부분: 위에서 동시에 올라온다고 해놓고 여기서 또 하나의 트럭을 빼주었다. 여기서 오답이 발생 in_bridge.popleft() in_bridge.append(truck) answer += 1 # 모든 트럭을 다리 위에 올렸더라도, 도착까지 계산해야 한다. # 가장 도착지에서 먼 트럭이 도착지까지 걸리는 시간을 더해준다. for i in range(len(in_bridge)-1,-1,-1): if in_bridge[i]: answer += (i+1) break return answer 덱을 이용해야겠다는 생각은 보자마자 들었다. 배열에서 한 쪽으론 트럭을 빼내야 하고 한 쪽으론 집어 넣어야 해서 입구와 출구가 정해져있는 덱이 유리하겠다고 생각했다. 덱의 길이를 항상 bridge_length 만큼으로 유지하기 위해 항상 빈 곳은 0의 값을 채워 넣어 주었다. 다리의 길이가 1이 아니기 때문에, 다리 위에서 트럭이 움직일 떄도 시간이 흐르기 때문이다. 시간이 흐를 때마다 0번 index 값을 빼주고(popleft), 맨 뒤에 새로운 값을 삽입하면(append) 다리 위에 있는 모든 트럭의 index는 1씩 감소하게 된다. 따라서 1칸 씩 전진한 셈이 된다. 현재 트럭의 위치를 index로 설정하기 위해선 트럭이 있지 않은 공간을 0으로 설정하는 것은 내가 생각해도 잘한 것 같다. 특히나, 이렇게 하면 다리 길이보다 더 많은 트럭이 올라올 일은 걱정하지 않아도 된다. ...

2024년 3월 18일 알고리즘 문제풀이 문제 캐시 난이도 Lv.2 코드 1차 80점 / 100점 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(cacheSize, cities): answer = 0 if not cacheSize: answer = 5 * len(cities) return answer arr = [] for i in cities: city = i.lower() if len(arr) < cacheSize: answer += 5 arr.append(city) continue if city in arr: answer += 1 arr.remove(city) arr.append(city) continue else: answer += 5 arr.pop(0) arr.append(city) return answer 캐시에 여유공간이 있을 때는 우선적으로 채워주었다. 캐시가 가득 찼을 때, 가장 사용된지 오래된 캐시가 삭제되야 하므로 이에 대한 구별이 필요했다. 따라서 사용한 캐시는 배열에서 삭제후 다시 추가하였다. 이렇게 되면 캐시 배열의 0번 index의 값이 1순위로 삭제될 캐시가 된다. 테스트 케이스가 몇개 있어 실패하였는데, 생각해보니 캐시가 가득 차지 않았을 때도 이미 캐시에 존재하여 추가할 필요가 없는 경우가 있었다. 예를 들어, 첫 번째 두 번쨰 도시가 같다면 내 로직에선 둘 다 캐시에 들어 가버린다. 이 경우를 위해 조건을 추가했다. ...

2024년 3월 15일 알고리즘 문제풀이 문제 체육복 난이도 Lv.1 코드 1차 93.3점 / 100점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(n, lost, reserve): lost.sort() reserve.sort() arr = set() for loser in lost: if loser in reserve: reserve.remove(loser) continue if loser - 1 in reserve: reserve.remove(loser - 1) elif loser + 1 in reserve: reserve.remove(loser + 1) else: arr.add(loser) return n - len(arr) 2개의 테스트 케이스에서 오답처리 되었다. 생각해보니 이렇게 작성할 경우 여벌이 있었으나 도둑맞은 사람의 것을 다른사람에게 빌려주게 될 수도 있다는 생각이 들었다. 따라서 우선, 여벌이 있었으나 도둑 맞아 더이상 빌려줄 여력이 없으며 다른 사람의 것도 필요 없는 사람을 제외하도록 수정했다. ...

2024년 3월 14일 알고리즘 문제풀이 문제 음양 더하기 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 def solution(absolutes, signs): answer = 0 for i in range(len(signs)): if signs[i]: answer += absolutes[i] else: answer -= absolutes[i] return answer

2024년 3월 12일 알고리즘 문제풀이 문제 파일명 정렬 난이도 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 67 68 def seperate(name): # head와 number를 분리하는 함수 idx = 0 head = "" number = "" # 처음 숫자가 나오기 전까지가 head while True: if name[idx] in "0123456789": head = name[:idx] break idx += 1 # idx는 number의 첫글자로 유지된 상태에서 시작 # 숫자가 나오면 계속 number로 추가 # 5자리가 넘어가거나, tail이 존재하지 않으면 종료 while len(number) < 5 and idx < len(name): if name[idx] in "0123456789": number += name[idx] idx += 1 else: break # head는 소문자로 변환 return head.lower(), number def solution(files): # 정답을 담을 배열 answer = [] # 각기 다른 head만 담을 배열 # 첫번째 정렬을 위해 사용 head_order = [] # 동일한 head를 가진 number들을 담을 배열 # 두번째 정렬을 위해 사용 # key는 head로, value는 list로 만들 것. # 원소는 [number, index] 형태로 만들어 number로 정렬한다. # index는 files 내에서 index를 뜻하며 원래 파일 이름을 찾을 수 있도록 한다. arr = dict() for i in range(len(files)): file = files[i] # 파일명에서 head, number 추출 head, number = seperate(file) # 이번 파일의 head가 이전에 나온 적 있는 head라면? if arr.get(head): # dict에서 head가 key인 value를 찾아 추가 arr[head].append([int(number), i]) else: # 처음 나온 head라면 dict에 추가 arr[head] = [[int(number), i]] # 새로운 head 이므로 head 배열에도 추가 head_order.append(head) # head 배열을 사전순으로 정렬 head_order.sort() # 가장 먼저 나와야할 head 선택 for head in head_order: # 선택된 것을 head로 가지는 number 들을 정렬 arr[head].sort() for num, idx in arr[head]: # 순서대로 원래 파일 이름을 정답 배열에 추가 answer.append(files[idx]) return answer

2024년 3월 11일 알고리즘 문제풀이 문제 예상 대진표 난이도 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 def solution(n,a,b): answer = 0 # 다음 라운드로 진출하여 새로운 번호를 부여하는 함수 def victory(num): if num%2: tmp = num//2 + 1 else: tmp = num//2 return tmp # 만났는지 확인하는 함수 def check(p,q): if abs(p-q) == 1 and p//2 != q//2: return True else: return False cnt = 1 while True: if check(a,b): return cnt a = victory(a) b = victory(b) cnt += 1 return cnt 두 사람의 번호가 1 차이가 나지만 2로 나누었을 때 몫이 달라야 한다. 한 사람의 번호가 3일 때, 1 차이가 나는 수는 2와 4지만, 실제로 만나는건 몫이 다른 4이기 때문이다 ...