문제출처 생각 0에 가까운 두 수의 합을 구해 각 수를 구하는 문제 주어진 리스트를 오름차순으로 정렬한 다음 양 끝에서 투포인터로 계산한다. 0에 가까운 값을 찾는 것이므로 두 수의 합을 절대값으로 변환하여 최소값을 찾는다. 코드 import sys N = int(input()) min_val = sys.maxsize lst = list(map(int, input().split())) lst.sort() start = 0 end = len(lst) - 1 al = 0 san = 0 while start < end: part_sum = lst[start] + lst[end] if abs(part_sum) < min_val: al = lst[start] san = lst[end] min_val = abs(p..

문제출처 생각 전형적인 투포인터 문제라고 한다. 투포인터란 N개의 리스트를 순회할 두개의 포인터위치를 기록하며 처리하는 알고리즘이다. 정렬되어있는 문제는 보통 이진탐색으로 답을 구하지만 투포인터로도 적용할 수 있다. 핵심은 다음과 같다. start, end의 포인터를 첫 시작점으로 잡아놓고 찾아야하는 기준점(부분합)을 계속 더해나간다. 만약 기준보다 더해진 값이 작다면 end를 오른쪽으로 이동시킨다. 기준보다 커지면 반복문을 탈출하고 찾아야하는 기준에 부합하는지 확인한다. 그리고 start를 오른쪽으로 한칸 옮기며 반복을 이어나간다. 시간복잡도는 start는 0 ~ N까지 순회하기에 O(N)이고 end도 마찬가지로 0 ~ N까지 돌기에 O(N)이다. 결론은 O(N)의 시간복잡도를 갖는다. 문제에서 부합하..

문제출처 생각 처음에 완전 복잡하게 생각했다. 상하좌우로 나누어서 각각 시작점, 끝점을 구해서 상, 하는 n크기로, 좌, 우는 m크기로 쪼개고 바뀔 2차원 배열의 전체를 갈아끼우는 방식으로 접근했는데 너무 복잡해지고 코드도 난해해졌다. 한칸씩 밀고 내리기만 하면 되므로 좌상단의 값을 기억해두었다가 왼쪽 열을 위로올리고 아랫 행을 왼쪽으로 당기고 우측 열을 아래로 내리고 마지막으로 최상단 행을 오른쪽으로 미는 식으로 구현하면 해결할 수 있었다. 코드 const makeMatrix = (rows, columns) => { let matrix = [] for (let i = 0; i < rows; i++){ matrix.push([]); } let num = 1; for (let i = 0; i < rows ..

문제출처 생각 장르당 최대 2개의 노래를 answer에 담아서 반환하는 문제 담길 조건은 첫째, 해당 특정 장르의 노래의 재생수가 가장 높은 장르의 노래를 두개 담음 둘째, 해당 장르에서도 먼저 높은 재생수의 노래가 먼저 담김 장르별 최대 두개까지만 담길 수 있음 먼저 최대재생수의 장르를 찾기위해 반복문을 통해 장르별 재생수를 구했고 그 다음 재생수를 기준으로 내림차 정렬했다. 이후, 장르별 재생수가 높은 순서대로 dic를 만들었다. 그러면 재생수가 높은 장르 순대로 반복을 시켜서 해당 장르에 해당하는 노래 index를 참조해 정답배열에 넣으면 된다. 장르별 노래의 최대 카운트가 2이므로 cnt를 두는 조건을 추가 풀이 def solution(genres, plays): answer = [] genre_..

문제출처 생각 input 숫자를 2진수로 변환해서 나온 1의 갯수와 input보다 큰 숫자의 1의갯수랑 같은 숫자를 찾으면 된다. reverse로 안해줘도 됐다. 풀이 코드 # 2진수 변환함수 def dec2bin(n): binary = "" while(n != 0): left = n % 2 n //= 2 binary += str(left) return binary def solution(n): bin_val = list(dec2bin(n)[::-1]) comp = n + 1 n_count = bin_val.count("1") while(list(dec2bin(comp)).count("1") != n_count): comp += 1 return comp

문제출처 생각 주어지는 문자열이 사전의 몇번째에 있는지 리턴하는 문제 총 5개의 알파벳이고 각 글자당 5개의 가짓수가 생김 5^5 =>3125갯수의 사전단어가 생기고 모든 경우를 탐색해야함 dfs로 모든 경우 탐색 풀이 코드 order = 0 def solution(word): answer = 0 dic = {} lst =["A","E","I","O","U"] def dfs (s): global order if len(s) > 5: return dic[s] = order; order += 1 for i in lst: if(len(s+i) > 5): return dfs(s + i) dfs("") return dic[word]

문제 출처 영어 끝말잇기를 하는데 탈락하는 사람의 번호와 그 사람 기준 몇번째 턴에 탈락했는지를 구하는 문제이다. 3명의 사람이 있을 때, 4번째 순서에 탈락했다고 하면 1번은 자기의 2번째에 탈락한 것이므로 [1,2]를 반환하면 된다. 탈락 조건은 끝말잇기의 규칙인 마지막글자와 첫 글자가 다를때와 이미 사용한 단어를 재사용했을 때 탈락처리된다. 나는 현재와 이전을 나눠 맨 앞글자, 그리고 이전 단어의 마지막글자를 비교했고 dic에 등장단어를 추가해 재등장했을 때 탈락되도록 했다. 반환값은 총 두개로 현재 누가 탈락했는지, 그 사람의 몇번째 순서에서 탈락했는지이며 각각 현재 누가 탈락했는지 === 현재 순서에서 인원수를 나눈 나머지 + 1(전체 2명, 현재 5턴째 탈락 === (4 % 2 + 1)== 1..

https://www.acmicpc.net/problem/2638 상, 하, 좌, 우로 인접하고 값이 1인 치즈의 테두리값을 지워나가서 모든 치즈가 녹을 때까지 걸리는 시간을 구하는 문제다. 조건이 하나있는데 치즈 내부에 빈공간에 대해서는 노출된 면이 2면이어도 녹지 않는다는 것이다. 따라서 내부의 빈공간을 다른 값으로 마킹해야하는 것이 중요하다고 생각했다. 내부의 공간을 하는 것보다 외부의 값을 마킹하고 나머지 0부분을 내부값으로 쓰는 것이 좋다고 생각해서 외부값을 먼저 -1로 치환하고 난 다음, 치즈 테두리의 상하좌우값이 -1인것이 2개 이상이면 녹이고 나서 내부의 0을 다시 -1로 치환하는 방식으로 풀었다. 순서는 다음과 같다. 바깥에 이어져있는 0을 모두 -1로 치환한다. 각 치즈의 좌표에서 인접..

https://www.acmicpc.net/problem/2146 상하좌우로 이어진 섬에서 다른 섬으로 이동할 수 있는 최단거리를 구하는 문제다. 각 섬의 테두리에서 다른 섬의 테두리까지 도착하는 최단거리를 구하는 것으로 이해했고 이 풀이를 적용하기 위해 해야할 것은 다음과 같다. 각 섬을 숫자로 마킹한다. 테두리 좌표를 구해 해당 좌표에서 다른 섬의 테두리까지의 거리를 구한다. 모든 섬의 테두리에서 출발해 다른 섬의 테두리에 도착할 때까지의 거리 중 최단거리를 반환한다. 1번은 dfs로 상하좌우로 이어진 부분에 대해 1,2,3.. 숫자을 더하며 마킹을 했다. 그리고 해당 좌표로부터 상,하,좌,우로 이동했을 때 그 좌표의 값이 하나라도 0에 해당한다면 테두리이므로 섬의 숫자를 키로갖는 딕셔너리에 좌표를 ..

프로그래머스 타겟넘버 배열에 나열된 숫자를 더하거나 빼면서 타겟넘버가 될 수 있는 경우의 수를 구하는 문제 모든 경우 (배열원소 하나하나에 덧셈 또는 마이너스를 해야함)의 수를 찾아야 하기 때문에 완전탐색, 그중에 dfs로 해결 dfs는 재귀로 구현하고 재귀이기에 base case를 넣어주어야한다. 여기서 base case, 재귀가 종료되는 조건은 연산횟수가 배열의 길이와 같을 때 종료한다. 경우의 수를 찾는 조건은 연산된 sum이 타겟넘버와 같을 때 answer를 1 증가시킨다. 백트래킹으로 덧셈 후, 마이너스 연산을 수행하도록 작성한다. function solution(numbers, target) { var answer = 0; const dfs = (n, t, s, i) => { if (n.len..