본문 바로가기

알고리즘 삽질장

 (228)
[프로그래머스] 오픈채팅방 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 사고과정 해쉬인 딕셔너리를 이용해야 하는 문제인 것 같았다. 그런데 입력 파라미터에서 출력결과로 어떻게 변환시켜 내뱉을지에 대한 고민이 매우 많았다.. 이런저런 시도를 해보다가 아이디어가 잘 떠오르지 않아서 구글링해서 소스코드는 보지 않고 어떤 아이디어만 사용한건지 보았다. 그래서 key는 ID로, value는 닉네임으로 하는 딕셔너리를 정의하고 Ent..
[프로그래머스] 문자열 내 마음대로 정렬하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12915 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱 programmers.co.kr 사고과정 문제에서 n번째 인덱스로 정렬하고 난 후에 사전순으로 정렬하라고 입출력 예시를 주어서 무조건 정렬 순서를 입출력 예시로만 생각해서 구현하려 했다.. 그러다보니 테스트케이스를 통과하지 못했고.. 머리를 쥐어싸매도 도저히 아이디어가 잘떠오르지 않았다.. 정렬 알고리즘 같은 것을 직..
[프로그래머스] 두 정수 사이의 합 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12912 코딩테스트 연습 - 두 정수 사이의 합 두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, solution을 완성하세요. 예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다. 제한 조건 a와 b가 같은 경우 programmers.co.kr 사고과정 단순이 리스트 컴프리헨션을 사용한 것보다 제네레이터를 활용해서 구현했다. 풀이 def solution(a, b): if a == b: return a elif a < b: return sum(x for x in range(a, b+1)) else: return sum(x fo..
[프로그래머스] 나누어 떨어지는 숫자 배열 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12910 코딩테스트 연습 - 나누어 떨어지는 숫자 배열 array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하 programmers.co.kr 사고과정 단순한 구현 문제였다. 배열 원소 하나씩 돌면서 divisor과 나누어떨어지는지 확인하면 됨. 단, 마지막에 나누어떨어지는 숫자를 append 한 리스트 길이가 0이면 -1을 반환하는 처리만 추가해주면 된다. 풀이 def solution(arr, divisor): answer ..
[프로그래머스] 같은 숫자는 싫어 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12906 코딩테스트 연습 - 같은 숫자는 싫어 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 programmers.co.kr 사고과정 스택을 활용하는 전형적인 문제이다. 스택이 비어있을 때는 바로 숫자를 넣고, 다음 배열의 원소를 돌때마다 스택의 가장 상위값을 확인하고 가장 상위값과 같으면 넣지말고 다르면 넣는 방식으로 구현하면 된다. 풀이 def solution(arr): stack = [] for a in arr: if not stack: sta..
[프로그래머스] 다트 게임 문제설명 https://programmers.co.kr/learn/courses/30/lessons/17682# 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 사고과정 문제가 스택을 활용해야 하는 듯한 문제인 게 감이 팍왔다.. 조건이 상당히 까다로웠다.. 시간이 좀 오래 걸리긴 했지만 구현에 성공했다... 중간에 많이 헤맨 부분이 잘 구현했는데 *(스타상) 일 때, 스택에서 뽑아낸 2개의 데이터를 다시 넣어줄 때 뽑아낸 순서 반대로 넣어줬어야 했는데 뽑아낸 순서대로 넣어주어서 테스트 케이스에서 자꾸 오류를 발생시켰다.. 그래도 디버깅해서 다행이다.. 스택에서 빼고 넣어줄 때 순서에 유의해야겠다! 풀이 def solution(dartResult): stack1 = [] # 숫자넣..
[프로그램스] 가운데 글자 가져오기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12903 코딩테스트 연습 - 가운데 글자 가져오기 단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다. 재한사항 s는 길이가 1 이상, 100이하인 스트링입니다. 입출력 예 s ret programmers.co.kr 사고과정 홀수 일 경우는 문자길이를 2로 나누었을 때의 인덱스를 가져오면 된다. 짝수 일 경우는 문자길이를 2로 나누었을 때의 인덱스 -1 부터 +1 인덱스까지의 슬라이싱으로 가져오면 된다. 풀이 def solution(s): mid = len(s) // 2 if len(s) % 2 != 0: return s[mi..
[프로그래머스] 비밀지도 문제설명 https://programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 사고과정 십진수를 이진수로 DFS 함수로 바꾸어주는 것이 가장 핵심이었다. 즉 암호화된 10진수 값을 이진수 값으로 부호화한다. 그리고 n길이 만큼 이진수 길이가 나오지 않은 값들은 모두 왼쪽에다가 0을 빈자리에 모두 추가해주어야 한다. 그리고 난 후 두 맵의 동일한 원소끼리 합쳤을 때 값이 1 이상이면 벽이고 0이면 공백으로 최종 맵을 갱신해주..
[프로그래머스] 부족한 금액 계산하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/82612 코딩테스트 연습 - 부족한 금액 계산하기 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 사고과정 count 만큼 반복해서 money에서 price를 빼주되 count할 때마다 price에 1배씩 증가시켜 빼준다. 결과 money값이 음수면 부족하다는 의미이므로 절댓값을 취해 부족한 금액을 반환하고 만약 양수라면 부족하지 않다는 것이므로 0을 반환하면 된다. 풀이 def solution(price, money, co..
[프로그래머스] 나머지가 1이 되는 수 찾기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/87389 코딩테스트 연습 - 나머지가 1이 되는 수 찾기 자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다. 제한사항 입 programmers.co.kr 사고과정 그냥 단순히 1부터 N+1까지 loop를 돌면서 N이랑 나누었을 때, 나머지가 1이 되는 수가 발견되는 순간 바로 리턴하면 된다! 풀이 def solution(n): for i in range(1, n+1): if n % i == 1: return i
[프로그래머스] 최소 직사각형 문제설명 https://programmers.co.kr/learn/courses/30/lessons/86491 코딩테스트 연습 - 최소직사각형 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 사고과정 모든 명함들을 다 넣을 수 있는 최소 지갑 크기를 구해야 한다. 명심해야 할 점은 주어진 명함의 가로, 세로를 바꾸어서 수납이 가능하다는 점! 그래서 우선은 각 명함마다 길이를 오름차순으로 모두 정렬하면서 가로, 세로 길이를 오름차순으로 재정렬한다. 그리고 난 뒤의 가로 길이의 최댓값, 세로길이의 최댓값을 구한 후 넓이를 구해주면 된다! 풀이 de..
[프로그래머스] 2016년 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12901 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 사고과정 이런 문제가 더 어려운 듯 하다... 우선 2016년 한정으로 문제가 주어지기 때문에 2016년의 월마다 일수를 리스트로 정의했다. 그리고 2016년 1월 1일이 금요일이기 때문에 금요일부터 시작해서 목요일까지 순서로 리스트를 정의했다. 그리고 만약 문제에서 1월달 날짜로 주어진다면 그냥 바로 일수(b)에..
[프로그래머스] 두 개 뽑아서 더하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 사고과정 N개 중 2개를 뽑는 조합의 경우의 수를 탐색하면서 그 경우의 수를 합한 결과값을 집합 자료구조형에 담아서 unique한 원소들만 남도록 구현했다. 한 가지 배운점이 있는데, 그 동안 nested function(중첩 함수)에서 바깥 함수에서 정의한 변수를 inner 함수에서 사용할 때 어떻게 해..
[프로그래머스] 예산 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12982 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr 사고과정 최대한 많은 부서의 물품을 구매해 줄 수 있도록 이라는 문장에서 그리디 유형이라는 것을 예상했다. 그리고 그리디는 정렬 과 자주 연계되기 때문에 정렬도 같이 생각함! 문제에서 부서별로 신청한 금액이 d 배열로 주어지는데, 예산 안에서 최대한 많은 부서에 지원해야 하니까 d 배열을 오름차순으로 정렬한 뒤 d를 for loop를 돌면서 예산을 차감하다..
[프로그래머스] 3진법 뒤집기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 사고과정 10진수를 n진수로 만드는 방법은 재귀함수로 활용해서 쉽게 구현했다. 그런데 n진수로 만든다음 뒤집은 후 다시 이를 10진수로 변환하라고 해서, '뒤집는 것까지' 10진수에서 n진수로 만들 때 적용했다. 그런데 이렇게 하면 10진수로 변환하는 로직을 적용하면, 변환 이전의 10진수값으로 다시 돌아..
[프로그래머스] 약수의 개수와 덧셈 문제설명 https://programmers.co.kr/learn/courses/30/lessons/77884 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr 사고과정 소수 판별이나 소수의 개수를 구하는 에라토스테네스의 체 처럼 제곱근을 활용해서 탐색하는 시간 복잡도를 줄일 수 있지 않을까를 계속 파고들었다.. 하지만 결국 구현을 하지 못해서 그냥 1부터 X까지 선형적으로 약수를 탐색했다. 다른사람 풀이를 보니 약수가 홀수개인 모든 수는 제곱수라는 것을 이용..
[프로그래머스] 폰켓몬 문제설명 https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 사고과정 set 자료구조를 활용했다. 어차피 요구하는 사항은 폰켓몬 종류 최대 개수만 리턴하면 되기 때문에 구현이 간단했다. 풀이에 비해 문제가 길어서...살짝 쫄은 상태에서 읽었다..쫄지말자.. 풀이 def solution(nums): monster = len(set(nums)) n = len(nums) if monster
[프로그래머스] 체육복 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 사고과정 예전에 비슷한 문제를 풀어본 적이 있던 것 같았다.. 그리디 유형이였는데 풀지 못했다.. 내가 놓친 점은 도난당한 사람과 여분의 옷이 있는 사람 모두 동일할 때를 놓쳤다.. 그래서 이 동시 조건을 만족하는 사람을 도난당한 사람이 있는 리스트 lost 와 여분 옷 있는 사람들이 있는 리스트 reserve에서 빼주고 시작해야 한다.. 그런 후 여분 ..
[프로그래머스] 모의고사 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 사고과정 완전탐색 문제라고 해서 DFS를 수행해야 하나 싶었지만 DFS를 활용하지 않아도 되었다. 그냥 주어진 찍는 방식 3가지 패턴을 주어진 문제 개수만큼 늘린 후 정답이 일치하는지 선형적으로 탐색하면서 맞은 정답 개수를 세면 되었다. % 나누기 연산 기호를 적절히 활용해서 구현할 수 있을 듯 해서 활용했다. 문제를 풀은 후, 다른 사람 풀이를 하나 ..
[프로그래머스] K번째 수 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 사고과정 문제 설명대로만 잘 구현하면 된다! 간단한 구현 문제 풀이 def solution(array, commands): answer = [] for i, j, k in commands: res = array[i-1:j] res.sort() answer.append(res[k-1]) return answer

티스토리툴바