Coding Test

가장 긴 팰린드롬 (2중 for문 인덱스, 투포인터, 문자열 길이)

https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1. 2중 for문 완전 탐색 Time: 3926.56 ms def solution(s): answer = 0 for i in range(len(s)): for j in range(i+1,len(s)+1): if s[i:j]==s[i:j][::-1]: answer=max(answer, len(s[i:j])) return answer "abacde" a ab aba abac abacd abac..

점 찍기 (피타고라스)

https://school.programmers.co.kr/learn/courses/30/lessons/140107 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 원점 (0,0)으로부터 반원에 들어가는 점 1 ≤ k ≤ 1,000,000이므로 완전 탐색하면 시간 초과 x축을 기준으로 y값 구하기 d² + x² = y² 풀이 import math def solution(k, d): answer = 0 for x in range(0, d+1, k): y= math.sqrt(d*d - x*x) # 피타고라스 answer += y//k + 1 return ..

배달 (플로이드 워셜)

https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 https://karla.tistory.com/29 [11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 karla.tistory.com 풀이 import sys def..

섬 연결하기 (MST, 최소신장트리)

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 https://karla.tistory.com/30 [1197번] 최소 신장 트리(MST, 크루스칼, 프림, 유니온파인드) 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이 karla.tistory.com ..

시소 짝꿍 (Counter)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 2 ≤ weights의 길이 ≤ 100,000이므로 조합으로 풀면 시간초과 풀이 from collections import Counter def solution(weights): answer = 0 counter = Counter(weights) for c in counter: answer += counter[c]*(counter[c]-1)//2 answer += counter[c]*counter[c*3/2] answer += counter[c]*counter[c*2] answer += counter[c..

요격 시스템 (그리디)

https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 끝값이 현재 시작값 보다 큰 경우 겹칩 끝값 유지 끝값이 현재 시작값보다 같거나 작은 경우 겹치지 않음 미사일 수 1 증가 시작값, 끝값 갱신 [[1, 4], [3, 7], [4, 5], [4, 8], [5, 12], [10, 14], [11, 13]] nowStart nowEnd end answer 4 1 3 7 4 1 4 5 5 2 4 8 5 2 5 12 12 3 10 14 12 3 1..

행렬 테두리 회전하기 (이차원 배열 회전)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(rows, columns, queries): answer = [] arr=[[0]*(columns+1) for _ in range(rows+1)] h=1 for i in range(1, rows+1): for j in range(1, columns+1): arr[i][j]=h h+=1 for x1, y1, x2, y2 in queries: tmp=arr[x1][y1] min_val=tmp for k in range(x1,x2): # 왼쪽으로 t = arr[k+1][y1] arr[k][y..

무인도 여행 (BFS)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 섬나라 아일랜드(BFS) 분석 [2667] 단지번호붙이기(BFS) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단 karla.tistory.com 더보기 [2667] 단지번호붙이기(BFS) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를..

124 나라의 숫자 (3진수, 0이 없을 때, 재귀)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 EX) 9는 124나라에서 24 3진법 계산 9 ÷ 3 = 3 ⋯ 0 3 ÷ 3 = 0 ⋯ 0 124나라 계산 9 ÷ 3 = 3 ⋯ 0 ➔ 0은 4로 치환, 몫에 -1을 빼서 재귀 2 ÷ 3 = 0 ⋯ 2 풀이 answer = '' def solution(n): def DFS(x): global answer if x == 0: return else: if x%3==0: DFS((x-1)//3) answer+='4' else: DFS(x//3) answer+=str(x%3) DFS(n) return ans..

최소직사각형 (정렬)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 큰값(가로)의 최댓값 * 작은값(세로)의 최댓값 def solution(sizes): return max(max(x) for x in sizes) * max(min(x) for x in sizes) [[60, 50], [30, 70], [60, 30], [80, 40]] [60, 50] [30, 70] [60, 30] [80, 40] max([60, 70, 60, 80]) * max(50, 30, 30, 40)) 80 * 50 = 4000 def solution(sizes): return max(sum(siz..