Algorithm

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)

2024년 1월 30일 알고리즘 문제풀이 문제 뉴스 클러스터링 난이도 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 def solution(str1, str2): def check(x): if x[0].islower() and x[1].islower(): return True else: return False str1 = list(str1) str2 = list(str2) arr1 = [] arr2 = [] for i in range(len(str1) - 1): if str1[i].isupper(): str1[i] = str1[i].lower() if str1[i + 1].isupper(): str1[i + 1] = str1[i + 1].lower() if check(str1[i] + str1[i + 1]): arr1.append(str1[i] + str1[i + 1]) for i in range(len(str2) - 1): if str2[i].isupper(): str2[i] = str2[i].lower() if str2[i + 1].isupper(): str2[i + 1] = str2[i + 1].lower() if check(str2[i] + str2[i + 1]): arr2.append(str2[i] + str2[i + 1]) arr_all = arr1 + arr2 arr_set = set(arr_all) n_max = 0 n_min = 0 for i in arr_set: n_max += max(arr1.count(i), arr2.count(i)) if i in arr1 and i in arr2: n_min += min(arr1.count(i), arr2.count(i)) if str1 == str2: answer = 65536 elif not n_max and not n_min: answer = -1 else: answer = int((n_min / n_max) * 65536) return answer 우선 문자열을 배열로 만들었다. 이후 각 원소가 대문자라면 소문자로 만들어주었다. 대문자, 소문자 구별이 없기 때문에 비교를 수월하게 하기 위함이다. 리스트의 두 원소를 붙여서 check 함수를 통해 둘다 소문자로 이루어진 알파벳인지 확인한다. 앞서서 대문자를 모두 소문자로 바꿔서 대문자일 가능성은 없다. 굳이 두개를 나눠야 하는 이유는, “%a” 에게 islower() 메서드를 사용하면 a가 소문자라 True를 반환하기 떄문이다. 앞에 %는 무관하다. 물론 “%” 처럼 알파벳이 없다면 False를 반환하다. 따라서 둘 다 알파벳으로 이루어졌는지 확인하기 위해 check() 함수에서는 둘을 나눴다. 이후 합집합의 갯수와 교집합의 갯수를 확인하기 위해 알파벳 2개가 원소인 리스트를 합쳐 set로 만들었다. 중복된 원소를 제거하여 교집합과 합집합 계산에 경우의 수를 낮추기 위해서다. 둘 다 공집합이면 -1을 반환해야하는데, 합집합 교집합이 0일 떄로 확인했다. 다만 예시 3번처럼, “%a!” 와 “%A!” 는 실제로 2개씩 잘랐을 때 모두 알파벳 2개로 이루어지지 않아(%a, a!) 집합이 없게 표시되지만 자카드 유사도는 1이다. 알파벳의 대문자 소문자 여부를 따지지 않기 때문에 완전히 동일한 두 문자열이기 떄문이다. 이럴 때를 확인하기위해 소문자로 바꾸고 리스트화 한 이후 둘이 같다면 자카드 유사도가 1이라 66536을 곱하여 나눈 정수부분을 그대로 출력하도록 했다. ...

2024년 1월 25일 알고리즘 문제풀이 문제 N개의 최소 공배수 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 def solution(arr): num = max(arr) i = 1 while True: answer = num*i for x in arr: if answer%x: i += 1 break else: return answer 어떤 수들의 최소공배수는 모든 수의 배수라는 의미이다. 따라서 수 들중 가장 큰 수의 배수를 모두 탐색하여 어떤 수로도 나누어 떨어질 때가 최소공배수이다. 가장 큰 수로 하는 이유는, 그나마 횟수를 조금이라도 낮추기 위해서이다. ...

2024년 1월 26일 알고리즘 문제풀이 문제 문자열 나누기 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def solution(s): answer = 0 while s: x = s[0] num_x = 0 not_x = 0 for i in range(len(s)): if s[i] == x: num_x += 1 else: not_x += 1 if num_x == not_x: answer += 1 s = s[i+1:] break else: return answer+1 return answer

2024년 1월 25일 알고리즘 문제풀이 문제 정수 제곱근 판별 난이도 Lv.1 코드 1 2 3 4 5 6 7 def solution(n): tmp = int(n**(0.5)) if tmp**2 == n: answer = (tmp+1)**2 else: answer = -1 return answer 제곱근은 0.5제곱과 같음.

2024년 1월 22일 알고리즘 문제풀이 문제 JadenCase 문자열 만들기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 def solution(s): arr = [' '] + list(s) nums = ['1','2','3','4','5','6','7','8','9','0',' '] n = len(arr) for i in range(1,n): if arr[i-1] == ' ' and arr[i] not in nums: arr[i] = arr[i].upper() elif arr[i].isupper(): arr[i] = arr[i].lower() answer = ''.join(arr[1:]) return answer 단어의 가장 앞이 알파벳일 때, 대문자로 만들어줘야 한다. 처음엔 단어별로 끊어서 풀어보려 했지만 문제의 조건 상 연속된 공백문자가 나올 수 있어서 실패했다. 따라서 모든 글자를 잘게 쪼개서 공백문자 이후 알파벳이 나온다면, 단어의 시작인 알파벳이므로 대문자로 바꾸도록 했다. 그 외의 대문자가 나타날 경우 소문자로 바꿔주는 로직도 추가했다. ...

2024년 1월 19일 알고리즘 문제풀이 문제 키패드 누르기 난이도 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 def solution(numbers, hand): arr = [0 for _ in range(len(numbers))] position = [[3,1],[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2],[3,0],False,[3,2]] finger = [10,12] left = [1,4,7] right = [3,6,9] for i in range(len(numbers)): num = numbers[i] if num in left: arr[i] = 'L' finger[0] = num elif num in right: arr[i] = 'R' finger[1] = num else: number_position = position[num] left_finger = position[finger[0]] right_finger = position[finger[1]] distance_left = abs(number_position[0]-left_finger[0]) + abs(number_position[1]-left_finger[1]) distance_right = abs(number_position[0]-right_finger[0]) + abs(number_position[1]-right_finger[1]) if distance_left < distance_right: arr[i] = 'L' finger[0] = num elif distance_left > distance_right: arr[i] = 'R' finger[1] = num else: if hand == 'left': arr[i] = 'L' finger[0] = num else: arr[i] = 'R' finger[1] = num answer = "".join(arr) return answer 각 번호간의 거리를 어떻게 처리할지 고민하다가 키패드를 좌표라고 생각하고 각 숫자의 위치를 값으로 갖는 배열 position을 만들었다. ...

2024년 1월 18일 알고리즘 문제풀이 문제 자연수 뒤집어 배열로 만들기 난이도 Lv. 1 코드 1 2 3 4 5 def solution(n): answer = list(str(n)) answer.reverse() answer = list(map(int,answer)) return answer reverse와 map 함수의 형식이 은근히 헷갈린다.