Coding Test

전력망을 둘로 나누기 (완전탐색, BFS)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1.90ms import copy, sys def solution(n, wires): answer = sys.maxsize g=[[] for _ in range(n+1)] for s,e in wires: g[s].append(e) g[e].append(s) visited=[False]*(n+1) def BFS(v, e): del_wire=[[v,e], [e,v]] queue=[] visited[v]=True queue.append(v) while queue: now=queue.pop(0) visited[..

K번째수 (정렬)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(array, commands): answer = [] for i,j,k in commands: answer.append(sorted(array[i-1:j])[k-1]) return answer def solution(array, commands): return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))

퍼즐 조각 채우기 (BFS, 리스트 비교)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 퍼즐조각, 빈칸 리스트 구하는 방법 [17472] 다리 만들기2 (BFS, MST) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바 karla.tistory.com 풀이 전체 코드 import copy from collections import deque dr=[0,1,0,-1] dc=[1,0,-1,0] def solution(game_boa..

아이템 줍기 (BFS, 겹쳐진 사각형 테두리 구하기)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 테두리 좌표는 *2해서 구해야함 : 인접한 테두리가 구해지면 최단경로로 지나기 때문에 인접한 테두리가 생김 빨간 선과 같이 인접한 테두리를 최단경로로 지남 *2를 해서 구하는 경우 인접 테두리가 생기지 않음 풀이 from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def solution(rectangle, characterX, characterY, itemX, itemY): board=[[-1]*102 for _ in range(102..

단어 변환 (BFS, deque, 리스트 거쳐 target 단어로 변환하기)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(begin, target, words): answer = 0 v=[0]*len(words) # 단어 사용체크 리스트 q = deque() q.append([begin, 0]) while q: word, cnt = q.popleft() if word == target: answer = cnt break for i in range(len(words)): word2=words[i] temp_cnt = 0 if not v[i]: # 사용안한..

큰 수 만들기 (스택)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(number, k): stack = [] for x in number: while stack and stack[-1]0: k-=1 stack.pop() stack.append(x) return ''.join(stack[:len(stack)-k])

여행경로 (DFS, 모든 경로 사용해서 모든 노드 방문)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 무조건 알파벳 순서가 앞서는 곳을 향하도록 여행 경로를 구성하면 문제의 답을 올바르게 구할 수 있음을 보장하지 않음 ticket result [["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]] ["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"] 위 예시에서 처음에 "ICN"에서 출발하여 "AAA"를 먼저 방..

쿼드압축 후 개수 세기 (재귀)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 배열의 길이가 1이 될 때 까지 4개로 나눔 (재귀) 4개로 나누는 시작 좌표, 길이를 매개변수로 하는 함수 생성 풀이 def solution(arr): answer = [0, 0] def quad(r,c,n): if len(arr) == 1: answer[arr[r][c]] += 1 return else: tg = arr[r][c] for i in range(n): for j in range(n): if arr[r+i][c+j] != tg: n=n//2 quad(r, c, n) quad(r, c+n, ..

[Python] 삼각 달팽이 (리스트 반시계 방향으로 채우기)

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  분석삼각형 리스트 생성채울 숫자 변수 선언n번 회전하므로 n번 반복3으로 나눠서 방향 체크 : 세 방향(아래쪽, 오른쪽, 위쪽)으로 채워지기 때문회전하면서 채워지는 길이는  n, n-1, n-2, ... ,1n=5인 경우, 5번 회전하면서(1,2,3,4,5) 방향 하(6,7,8,9) 방향 우 (10,11,12) 방향 상(13,14) 방향 하(15) 방향 우순서로 채워짐 풀이def solution(n): answer = [[0 for j in range(1, i+1)] for i in range(1,..

단속카메라 (greedy)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 배열 정렬 첫번째 선으로 시작 이어져있다면 끝이 더 작은걸로 연결하고(겹쳐야 카운트하기 때문에), 끊어져있다면 카운트 한 후 새로 시작 [2170] 선 긋기 (선의 총 길이 구하기) 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 분 karla.tistory.com 풀이 def..