꾸준한 연습장

31423번: 신촌 통폐합 계획첫 번째 줄에 대학교의 개수 $N$이 주어진다. $(2 \leq N \leq 500 \, 000)$ 다음 $N$개의 줄의 $i$번째 줄에 대학교 이름을 의미하는 알파벳 소문자로 이루어진 문자열 $s_i$가 주어진다. 주어지는 대학교www.acmicpc.net 문제극단적인 출산율 감소로 인해 신촌 지역 N개 대학교가 하나의 학교로 통합되었다.기나긴 회의 끝에, 통합된 학교의 이름은 N개 대학교의 이름을 이어 붙여서 정해졌다. 회의에서 통합된 학교의 이름을 정한 방법은 다음과 같다. N개 대학교의 이름 s1,s2,⋯,sN을 일렬로 나열한다. 이후 다음의 과정을 N−1번 반복한다. si,sj가 빈 문자열이 아닌 서로 다른 두 정수 i,j를 고른다. si의 뒤쪽에 sj를 이어 붙인..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  풀이 goal에 있는 단어를 순회하며 두 카드 뭉치의 맨 앞에 있는 단어가 일치하는 경우 꺼내서 사용한다.두 카드 뭉치 모두에서 일치하는 단어가 없다면 No를 반환한다.goal을 모두 성공적으로 순회했다면 Yes를 반환한다. 두 카드 뭉치의 맨 앞에 있는 것부터 순차적으로 사용해야 하므로 스택으로 변형하여 pop()을 활용하였다. def solution(cards1, cards2, goal): cards1 = cards1[::-1] cards2 = cards2[::-1] for word ..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  풀이 그리디하게 접근해야 하는 문제이다. 알고리즘은 다음과 같다. 처음 주어진 수의 1의 자리 숫자부터 순회한다.1의 자리 숫자와 다음 자리 숫자를 추출1의 자리 숫자가 5보다 크거나, 5이고 다음 자리 숫자가 5 이상이면 올림 처리그 외의 경우에는 내림 처리결과 반환 def solution(storey): result = 0 while storey > 0: num = storey % 10 # 1의 자리 수 추출 next_digit = (storey // 10) % ..

1082번: 방 번호스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해www.acmicpc.net 문제스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.예를 들어, N = 3, M ..

1662번: 압축압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이www.acmicpc.net 문제압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오. 입력첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다. 출력첫째 줄에 압축되지 않은 문자열의 길이..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   풀이 제한사항이 매우 작으므로 특별한 알고리즘 없이 구현이 가능하다. 알고리즘은 다음과 같다. skip에 있는 문자열을 제외한 알파벳 목록을 구한다. 이를 skipped 라 칭한다.s를 순회하며 skipped에서 현재 알파벳의 인덱스를 찾아 index 만큼 더해준다. 이 때, skipped 의 총 길이를 초과한다면 그 나머지를 구한다.result에 2에서 구한 인덱스의 알파벳을 더한다. def solution(s, skip, index): skipped = [chr(i) for i in range(97,..

16120번: PPAP첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.www.acmicpc.net 문제bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.P는 PPAP 문자열이다.PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr ↓ 문제 열기더보기   풀이 제한사항 100,000 및 타일 문제이므로 DP를 활용해야 함을 쉽게 유추할 수 있다.어떤 점화식을 도입할 수 있을지 살펴보도록 하자.  tops 의 원소가 하나 추가될 때, 회색 부분은 기존(dp[n-1])의 모든 경우의 수가 고려된 부분이므로 흰 부분에 대해서 타일링을 채우는 방법을 고민해야 한다. 흰 부분은 다음과 같은 방법으로 채울 수 있다.  따라서 tops에 따라 총 3가지 경우의 수로 구분할 수 있다(현재 고려할 top 이 0이라면, 세 번째 경우는 제외하면 된다).  하..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   풀이 숫자를 하나씩 올려갈 때, 이진수로 변환 시 1의 개수가 일치하는 것을 찾으면 된다. def solution(n): ans = n num1 = bin(n).count("1") while True: ans += 1 if num1 == bin(ans).count("1"): break return ans

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   풀이 각 이모티콘의 할인율을 적절하게 정하여 최대의 이모티콘 플러스 가입자를 유치하고, 그 때 최대의 이익을 출력해야 한다.  알고리즘이 필요하다기 보다는 단순무식한 구현 문제였다. 완전탐색으로 문제를 해결하려고 할 때, 제한 사항이 시간복잡도를 만족하는지 확인해보자.  이모티콘의 총 길이는 7이고 할인율은 10, 20, 30, 40 총 4개이다. 그리고 최대 유저는 100명이다. 이 때 생각할 수 있는 완전탐색 알고리즘은 다음과 같다. 존재할 수 있는 모든 할인율의 조합을 이모티콘의 길이만큼 구한다.할인율의..