네발로 코딩하는 포메라니안

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - bfs + 비트마스킹 - 입력이 8개이하이므로 비트마스킹(32bit)을 사용 class Solution { int n, answer; public void bfs(int k, int[][] dungeons, int visit, int cnt){ answer = Math.max(answer, cnt); for(int i=0; i

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - 끊었을 때 한 쪽 전력망 개수만 cnt해서 (전체)-cnt와 차이를 구한다. => dfs를 시작할 때, 제거할 선과 연결된 노드는 방문처리하여 다시 방문하지 않게 함으로써 "끊어짐"을 고려한다. - n-1개의 선으로, 전체 가능한 간선(n*(n-1))에 비해 매우 적은 편이므로 LinkedList로 구현 import java.util.*; class Solution ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 1. 균형 잡힌 괄호 문자열 + 올바른 괄호 문자열을 동시에 확인한다. - 열린 괄호가 오면 +1, 닫힌 괄호가 오면 -1 => 중간에 한 번이라도 음수가 되면, 올바른 괄호 문자열이 아니다. 2. u가 올바른 괄호 문자열인지에 따라, 다르게 처리하고 재귀함수를 돌린다. - '올바른'이면, u + 재귀(v) - '올바른'이 아니면, ( 재귀(v) ) + 뒤집은 u cla..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 1. game_board의 빈칸과 table의 퍼즐을 dfs로 탐색 1) 각 덩어리의 좌표들을 저장 2) 각 덩어리의 개수를 저장 3) 각 덩어리의 시작값 저장 2. 평행이동을 이용하여 같은 블럭인지 확인 & 회전을 반복한다. *회전은 블럭 하나하나를 생각하지 않고, 판 전체를 돌린다는 생각으로 좌표를 이동시켰다. import java.util.*; class Block{..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 2. 풀이과정 dfs문제 + 문자열 정렬 1) 문자열을 정렬하기 위해서 지역 이름들을 하나의 문자열로 concat해서 사용 2) 사전순 정렬 3) 공항 이름이 모두 3자리이므로, 3개씩 잘라서 배열에 담아서 반환 import java.util.*; class Solution { static int N; static A..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 2. 풀이과정 0~distance 범위를 이진탐색을 통해 답을 찾는다. 매 loop마다 중간값보다 작으면 합치고, cnt를 센다. 1) cnt가 n개 이상이면, 값을 줄여야 하므로 right = m-1 2) cnt가 n개 이하면, 값을 늘려야 하므로 left = m+1 3) cnt == n이 되는 중간값은 여러 개 있을 수 있다. 그 중 ..

1. 문제 2. 풀이 과정 Python 정규 표현식을 이용하여 parsing을 하였다. 여기서 사용된 정규표현식만 살펴보자면 아래와 같다. import re #1. findall text = "hello my id is a1" #문자로 이루어진 문자 1개이상으로 구성된 것 모두 찾기 test = re.findall(r'[a-zA-Z]+',text) print(test) #['hello', 'my', 'id', 'is', 'a'] #2. search text = '' #다음 패턴으로 이루어진 문장 하나 찾기 #[^>]* = >이 아닌 것 0개 이상으로 구성된 것 #[\S]* = 공백이 아닌 것 0개 이상으로 구성된 것 url_str = re.search(r']*content="https://([\S]*)"..

1. 문제 2. 풀이 과정 방법 1) 배열로 tree를 구성한 후, 순회 import sys sys.setrecursionlimit(10**6) class Node(object): def __init__(self, i, data_set): self.left_idx = -1 self.idx = i self.right_idx = -1 self.num = data_set[0] self.x = data_set[1] self.y = data_set[2] def pre_order(t, i, result): if i == -1: return result.append(t[i].num) pre_order(t, t[i].left_idx, result)#왼 pre_order(t, t[i].right_idx, result)#..

1. 문제 2. 풀이 과정 from collections import Counter def solution(food_times, k): food_num = len(food_times) #현재 음식 개수 counting = Counter(food_times) #시간별 음식 개수 time_list = list(counting.keys()) #시간 목록 time_list.sort() pre_time = 0 for time in time_list: if k

1. 문제 2. 풀이 과정 from itertools import combinations def solution(relation): row = len(relation) col = len(relation[0]) answer = set() for i in range(1, col+1): for com in combinations(range(col), i): #속성들의 조합 #최소성 검사 minimality = True for a_tup in answer: if set(a_tup) & set(com) == set(a_tup): minimality = False break #최소성을 만족, 유일성 검사 if minimality: temp = set() for k in range(row): temp.add(tupl..