스터디윗민

[Python] 프로그래머스 Lv3. 가장 긴 팰린드롬

문제https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약문자열 "s"가 주어졌을 때, 문자열의 부분문자열 중에서 앞에서 읽으나 뒤에서 읽으나 똑같은 팰린드롬을 찾는다.그중 가장 긴 팰린드롬의 길이를 return하면 된다.풀이처음에는 부분문자열을 하나씩 잘라서 뒤집은 값이 같은지 확인해야 하나...? 생각했는데 그러면 경우의 수가 너무 많아진다.결국 팰린드롬은 가운데를 기준으로 양쪽 문자가 같은지 확인하면서 늘려가면 된다.예를 들어"abcba"라면 가운데에 있는 "c"를 기준으로"b == b""a ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약A, B 두 배열이 주어진다.이때 배열에 들어간 값들은 해당 사원들(index)이 가지고 있는 숫자의 값이다. 1대1로 숫자 게임을 진행할 건데, 이때 상대보다 큰 값을 갖고 있다면 이기는 게임 규칙이다. (같으면 무승부다.)B팀이 최고로 많이 이길 수 있는 경우의 수를 구하라.풀이문제에서는 A팀의 순서가 고정된 것처럼 말하는데, 사실상 그냥 정렬해버리고 비교해버리면 되는 문제였다. 왜냐하면... 그걸 맞춰서 하든 다 정렬해버리고 하든 어차피..

문제https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약배열 A, B가 주어지고 해당 배열에서 하나씩 꺼내서 곱한 값의 합 중 가장 작은 값을 구하면 되는 문제.풀이이 문제도 쉽다. 그냥 가장 큰값이랑 가장 작은 값을 곱했을때가 다 더했을때 가장 작아지는 경우이기 때문에, A랑 B를 각각 반대로 정렬한다음에 맨 뒤에서부터 곱하고 result에 더해준 다음에 pop을 했다. def solution(A,B): n = len(A) result = 0 A.sort() B.sort(r..

문제https://school.programmers.co.kr/learn/courses/30/lessons/12939 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약공백으로 숫자가 구분된 문자열 s가 주어지면 최소값과 최대값을 반환하면 되는 문제.풀이푸는 건... 뭐 간단하다. 정렬하고 그냥 잘 반환만 하면 된다.파이썬이라 쉬웠을지도?def solution(s): nums = list(map(int,s.split(" "))) nums.sort() return " ".join(map(str, [nums[0], nums[-1]])) 시간복잡도sort 시간복잡도가 O(nlogn)이기 때문에 O..

문제https://school.programmers.co.kr/learn/courses/30/lessons/468373 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약1~n번까지 번호가 붙은 n개의 배양체. n-1개의 파이프들이 각각 연결하고 있고, 이 파이프들의 종류는 [A,B,C]이다.한 종류의 파이프만 열어둘 수 있고다시 닫기 전에 다른 종류의 파이프를 열 수는 없다.열어둔 파이프를 통해 감염된 배양체의 인접한 배양체들은 모두 감염된다. (이 말은 파이프가 열려있는 한 끝까지 다 감염된다는 뜻이다.)이 열고 닫는 행동을 최대 k번 반복했을때, 최대한 많은 배양체에 바이러스를 감염시키면 몇 개 인가..

문제https://school.programmers.co.kr/learn/courses/30/lessons/468371 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제요약초록불 -> 노란불 -> 빨간불 순서대로 반복될때,모든 신호등이 동시에 노란불을 키는 가장 작은 시간대가 언제인가?풀이아~ 유독 어렵게...느껴진 문제. 결국에는 초+노+빨 시간이 반복되고 그 시간들의 최소공배수를 구하면 된다. 왜냐하면 그 이후에도 노란색이 겹치지 않는다면, 경우가 있을 수 없다는 이야기이기 때문에(이전에 계산하면서 봤던 같은 상황이 한 번 더 일어난다고 생각하면 쉽다) 때문에 먼저 각 신호등의 사이클 최소공배수를 구하고 그..

문제https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제요약n시간 동안 작업을 1씩 줄일 수 있을 때, 남은 작업량의 제곱합을 최소로 만들면 되는 문제였다.큰 것부터 줄여야 한다는 것만 알면 풀린다!풀이야근 피로도를 줄이기 위해서는 제일 큰 걸 깎아서 일정값으로 맞추면 된다. 이때 cost(x) x까지 깎고 남은 시간은 x짜리를 x-1로 한 칸씩 더 내리는 데 쓴다. x가 최소값이라 남은 시간이 x짜리 개수보다 항상 작아서 개수 걱정은 안 해도 된다.n이 전체 작업량보다 크면 0으로 바로 리턴해줘야 한..

문제https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제요약0과 1로 이뤄진 배열에서 1로만 이루어진 정사각형 중 가장 큰걸 구하면 되는 문제풀이시간초과가 나서 흠... 어떻게 풀까 고민하다가 dp로 풀면 되겠다 싶어서 오른쪽 아래로 계속 내려가서 이전값은 저장되어있기 때문에 위로 올라갈 필요없이 쭉쭉 내려가면서 가장 큰값을 바꿔가면서 진행하면 된다.이때 정사각형이기 때문에 오른쪽 아래를 기점으로 위, 왼쪽, 대각선이 모두 k-1이상이어야하고 (한 변의 길이가 k라고 한다면) 하나라도 짧으면 거기서 막..

문제https://school.programmers.co.kr/learn/courses/30/lessons/17680 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 요약도시가 들어오고 캐시 크기가 정해져 있을때, LRU 방식으로 내보내고 들어오고를 반복한다고 하면 얼마나 걸리는지 측정하면 되는 문제였다.LRU를 안다면, 쉽게 풀 수 있는 문제!풀이LRU는 가장 오래 전에 사용한 것을 자리가 부족할때 먼저 빼내는 방식이다.때문에 새로 들어오는 값들이 이미 캐시 안에 있다면 remove한 다음에 새로 뒤에 넣어주는 방식으로제일 앞에 있는게 가장 오래 전에 사용했고 끝에 있는 게 최근에 사용한 것이다.있을때는 +..

문제https://school.programmers.co.kr/learn/courses/30/lessons/468370 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제요약카톡 스포 방지 걸린 메시지가 오는데, 이걸 왼쪽부터 하나씩 클릭해서 열어본다.열었을 때 1. 스포 걸린 단어이고 2. 스포 안 걸린 구간에 나온 적 없고 3. 앞에서 이미 열린 단어랑 안 겹치면 중요한 단어. 이런 단어가 몇 개인지 세면 되는 문제였다.풀이글자 단위로 구간이 주어진다는 게 어려웠던 문제...단어 기준으로 생각하면 좀 더 편하다.1. 먼저 글자마다 몇번째 스포 구간에 해당하는지 미리 칠해둔다. 구간이 겹치지 않고 정렬돼서 오니..