프로그래머스

2024년 1월 11일 알고리즘 문제풀이 문제 자릿수 더하기 난이도 Lv. 1 코드 1 2 3 4 5 6 def solution(n): answer = 0 arr = list(str(n)) for x in arr: answer += int(x) return answer

2024년 1월 2일 알고리즘 문제풀이 문제 N-Queen 난이도 Lv.2 코드 그 어렵다고 소문난 N-Queen 문제. 정글 때 공부했던 문제였는데 그새 까먹었나보다. 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 69 70 def solution(n): answer = 0 def check_width_row(p,q,arr): for i in range(n): if arr[i][q] == '0': arr[i][q] = False if arr[p][i] == '0': arr[p][i] = False def check_right_down(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n: if arr[p+i][q+i] == '0': arr[p+i][q+i] = False i += 1 def check_left_up(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n: if arr[p+i][q+i] == '0': arr[p+i][q+i] = False i -= 1 def check_right_up(p,q,arr): i = 0 while p-i >= 0 and p-i < n and q+i >= 0 and q+i < n: if arr[p-i][q+i] == '0': arr[p-i][q+i] = False i += 1 def check_left_down(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q-i >= 0 and q-i < n: if arr[p+i][q-i] == '0': arr[p+i][q-i] = False i += 1 def check(p,q,arr): check_width_row(p,q,arr) check_right_down(p,q,arr) check_right_up(p,q,arr) check_left_up(p,q,arr) check_left_down(p,q,arr) arr[p][q] = True def search(x,arr): for i in range(n): if arr[x][i] == '0': check(x,i,arr) flag = True break else: flag = False return flag for i in range(n): w = [['0' for _ in range(n)] for _ in range(n)] w[0][i] = True check(0,i,w) k = 1 while k < n: tmp = search(k,w) if tmp: k += 1 else: break if k == n: print(w) answer += 1 return answer 보드판을 string ‘0’을 배치시켜 만들었다. 원래 숫자로 넣었는데 False일 떄와 0일때가 같이 취급되어서 따로 만들었다. 아무 선택되지 않은 좌표는 ‘0’, 공격당할 수 있기 때문에 놓을 수 없는 곳은 False, 퀸이 위치한 곳은 True로 설정하였다. 우선 임의의 좌표 (p,q)에 퀸을 놓았을 때 퀸이 공격할 수 있는 곳을 False 처리하는 코드를 작성했다. 임의의 좌표의 좌 우 대각선을 바꿔주는 함수를 각각 만들고 하나의 함수로 합쳤다(check). search는 특정 행에서 퀸을 놓을 수 있는 열을 찾아 존재하면 boolean값을 반환해주는 함수이다. ...

2024년 1월 1일 알고리즘 문제풀이 문제 최솟값 만들기 난이도 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 from heapq import heappop, heappush def solution(A,B): n = len(A) arr_A = [False for _ in range(n)] arr_B = [False for _ in range(n)] arr = [] def dfs(tmp,arr_A,arr_B): if arr and tmp > arr[0]: return if not arr_A.count(False) and not arr_B.count(False): if not arr or tmp < arr[0]: heappush(arr,tmp) for i in range(n): if arr_A[i]: continue for j in range(n): if arr_B[j]: continue arr_A[i] = True arr_B[j] = True dfs(tmp+(A[i]*B[j]),arr_A,arr_B) arr_A[i] = False arr_B[j] = False dfs(0,arr_A,arr_B) return arr[0] 처음엔 DFS로 시도했다. 여러 case가 규칙성 없이 나타날 수 있다고 생각했기 때문이다. 하지만 시간초과가 발생했다. 불필요한 탐색을 줄이기 위해, 값을 최소힙에 저장하도록 했다. DFS 과정 상 재귀 중에 이미 최소힙에 존재하는 최솟값을 넘어선 경우 탐색을 중단하도록 했다. 하지만 시간초과가 계속 발생했다. ...

2023년 12월 29일 알고리즘 문제풀이 문제 신규 아이디 추천 난이도 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 53 54 55 56 57 def solution(new_id): arr = ['1','2','3','4','5','6','7','8','9','0','-','_','.'] # 1단계 new_id = new_id.lower() # 2단계 tmp = [] for i in new_id: if i.islower() == True or i in arr: tmp.append(i) new_id = ''.join(tmp) # 3단계 if len(new_id) >1: tmp = [] for i in range(len(new_id)-1): if new_id[i] == '.' and new_id[i+1] == '.': continue tmp.append(new_id[i]) tmp.append(new_id[-1]) new_id = ''.join(tmp) # 4단계 if new_id: if new_id[0] == '.': if len(new_id) == 1: new_id = '' else: new_id = new_id[1:] # 4단계 if new_id: if new_id[-1] == '.': if len(new_id) == 1: new_id = '' else: new_id = new_id[:len(new_id)-1] # 5단계 if new_id == '': new_id = 'a' # 6단계 if len(new_id) >= 16: new_id = new_id[:15] # 6단계 if new_id[-1] == '.': new_id = new_id[:len(new_id)-1] # 7단계 if len(new_id) <= 2: while len(new_id) < 3: new_id = new_id + new_id[-1] return new_id 문제에 주어진 대로, 순차적으로 해결하면 큰 어려움은 없는 문제였다. 다만 중간중간, 문자열이 존재하지 않게 되는 상황이 발생할 수 있기 때문에 이를 따로 처리하는 로직이 필요하다. 시간 많이 잡아먹는 문제라 좋은 연습이 됐다. ...

2023년 12월 28일 알고리즘 문제풀이 문제 문자열 내 p와 y의 개수 난이도 Lv.1 코드 1 2 3 4 def solution(s): a = s.count('p') + s.count('P') b = s.count('y') + s.count('Y') return a == b 이 문제에선 p 와 y만 포함됐지만, 대문자나 소문자 자체를 어떻게 셀 지 궁금해져서 찾아보니 islower() 와 isupper() 를 사용하면 boolean 값으로 반환된다고 한다.

2023년 12월 26일 알고리즘 문제풀이 문제 줄 서는 방법 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import math def solution(n, k): answer = [] arr = list(range(1,n+1)) while n>0: tmp = math.factorial(n-1) a = k//tmp k = k%tmp if k: answer.append(arr[a]) arr.pop(a) else: answer.append(arr[a-1]) arr.pop(a-1) n -= 1 return answer 순열에 정의를 알면 접근방식 자체는 그리 어렵지 않지만, 코드로 구현하는 게 꽤나 까다로웠다. 순열은 결국 앞에서부터 올 수 있는 경우의 수를 정해주고 곱하는 방식이다. 4명이 줄을 서는 방법은 4! = 4 x 3 x 2 x 1이다. 왜 이렇게 나오냐면, 맨 앞에 올 수 있는 후보는 4개 이고, 그 다음은 3개, 2개, 1개 이기 때문이다. ...

2023년 12월 25일 알고리즘 문제풀이 문제 최댓값과 최솟값 난이도 Lv.2 코드 1 2 3 4 5 def solution(s): answer = '' arr = list(map(int,s.split())) answer = str(min(arr)) + ' ' + str(max(arr)) return answer 문자를 공백을 기준으로 쪼개 숫자형으로 변환하여 배열에 저장하였다. 최댓값과 최솟값만 다시 문자열로 변환한 쉬운 문제.

2023년 12월 22일 알고리즘 문제풀이 문제 성격 유형 검사 난이도 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 def solution(survey, choices): answer = [] board = {'R':0, 'T':0, 'C':0, 'F':0, 'J':0, 'M':0, 'A':0, 'N':0} n = len(survey) for i in range(n): idx = survey[i] if choices[i] < 4: board[idx[0]] += abs(4-choices[i]) elif choices[i] >4: board[idx[1]] += (choices[i]-4) if board['R'] >= board['T']: answer.append('R') else: answer.append('T') if board['C'] >= board['F']: answer.append('C') else: answer.append('F') if board['J'] >= board['M']: answer.append('J') else: answer.append('M') if board['A'] >= board['N']: answer.append('A') else: answer.append('N') return ''.join(answer) 각 경우를 딕셔너리를 이용했다. 점수를 그대로 더해줘선 안되고 알맞게 변환해줘야 하는 부분이 조금은 신경써야할 부분. ...

2023년 12월 21일 알고리즘 문제풀이 문제 약수의 합 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 def solution(n): answer = 0 for i in range(1,int(n**(0.5))+1): if not n%i: answer += (i+n//i) if i == n//i: answer -= i return answer 공약수는 대칭이기 때문에 절반만 반복해주었다. 단 제곱수는 똑같은 수가 2번 더해지니 해당 부분만 뺴주었다. ...

2023년 12월 19일 알고리즘 문제풀이 문제 숫자 블록 난이도 Lv.2 코드 첫 생각 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution(begin, end): answer = [] for n in range(begin,end+1): if n == 1: answer.append(0) elif not n%2: answer.append(n//2) else: for i in range(3,n//2): if not n%i: answer.append(n//i) print(n,n//i) break else: answer.append(1) return answer 최대공약수와 관련된 문제라고 생각했다. 최초 0으로 설정되있는 각 숫자는 1부터 하나씩 업데이트되겠지만, 마지막으로 업데이트될 때는 최대공약수로 될 것이다. 따라서 짝수는 절반값으로 된다. 2는 1, 4는 2, 6은 3, 8은 4 가 그 예시이다. 문제는 홀수였는데.. 홀수는 2로 나눠질 수 없는 것은 확실하니 3부터 1씩 커지면서 나누어주었다. 나누어 떨이질때, 그 몫이 최대 공약수이다. 하지만 이 경우가 자기 자신 뿐이라면 그때는 소수이므로 1로 설정해줬다. ...