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

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - 중간 지점을 W라고 하면 S=>W, W=>A, W=>B로 구간을 나눠서 생각한다. - 각 구간 별 최단 거리 구하기 문제 방법1. 플로이드 워샬 - 모든 노드에서 모든 노드까지 전체 최단 거리를 구한다. - S=>W, W=>A, W=>B까지 모두 더한 값이 최소인 값을 찾는다. (중복이 있든 말든 상관없지만, 최단거리의 결과는 아마 중복 없게 나올듯 => 왔던 길 ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 Dijkstra import java.util.*; //돌아오는 건 생각X = 재방문이 가능하므로 갔던 길 똑같이 되돌아오자 class Solution { LinkedList list[]; public int[] solution(int n, int[][] paths, int[] gates, int[] summits) { int[] answer = {999_999_999..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/17676 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 1. 밀리초로 변환 2. 끝나는 지점을 기준으로 정렬되어 있으므로 뒤에서부터 탐색 3. 끝나는 지점에서 1초뒤에 있는 걸 기준으로 count : 갯수가 변하는 지점이 끝나는 지점과 일치하므로 4. priority queue로 시작점이 큰 순으로 정리해놓고, 지금 보는 끝지점+1초보다 더 크면 poll() import java.util.*; class Solution { ..

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]*)"..