Problem solving
-
문제 확인하기 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 나의 풀이 팰린드롬은 앞으로 읽어도, 거꾸로 읽어도 똑같은 단어다. 문제에선 뒤에 몇 글자를 추가해야 팰린드롬이 되는지 확인하고 싶어한다. 이를 위해선 현재 단어 중 어느 부분까지가 팰린드롬인지 체크해야 한다. 결국 i를 바꿔가며 순 방향, 역 방향 문자열이 동일한지 확인하면 된다. S = input() for i in range(len(S)): if S[i:] == S[i:][::-1]: palindrome = S + S[:i][::-1] print(..
[Python] 백준 1254번 팰린드롬 만들기 풀이문제 확인하기 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 나의 풀이 팰린드롬은 앞으로 읽어도, 거꾸로 읽어도 똑같은 단어다. 문제에선 뒤에 몇 글자를 추가해야 팰린드롬이 되는지 확인하고 싶어한다. 이를 위해선 현재 단어 중 어느 부분까지가 팰린드롬인지 체크해야 한다. 결국 i를 바꿔가며 순 방향, 역 방향 문자열이 동일한지 확인하면 된다. S = input() for i in range(len(S)): if S[i:] == S[i:][::-1]: palindrome = S + S[:i][::-1] print(..
2023.05.26 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 들은 멜로디와 실제 곡을 비교하기 위해선, 재생 시간 만큼 곡의 멜로디를 늘려줘야 한다. 곡을 늘릴 때 # 이 있으면 개수를 세기 어려우니, 먼저 # 이 붙은 음을 변경해준다. 나머지 부분은 문제의 조건에 맞춰서 구현하면 된다. 재생 시간이 동일할 경우, 먼저 입력된 음악을 반환하라고 돼 있는데, 입력 시간을 기준으로 정렬하지 않아도 똑같이 정답으로 나온다. 이미 입력 시간 기준으로 입력된 거 같다. # 끝부분-처음 부분 연결돼 헷갈릴 수 있음 / 중간 멜로디만 겹칠 수 있음 # 재생 시..
[Python] 프로그래머스 [3차] 방금그곡 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 들은 멜로디와 실제 곡을 비교하기 위해선, 재생 시간 만큼 곡의 멜로디를 늘려줘야 한다. 곡을 늘릴 때 # 이 있으면 개수를 세기 어려우니, 먼저 # 이 붙은 음을 변경해준다. 나머지 부분은 문제의 조건에 맞춰서 구현하면 된다. 재생 시간이 동일할 경우, 먼저 입력된 음악을 반환하라고 돼 있는데, 입력 시간을 기준으로 정렬하지 않아도 똑같이 정답으로 나온다. 이미 입력 시간 기준으로 입력된 거 같다. # 끝부분-처음 부분 연결돼 헷갈릴 수 있음 / 중간 멜로디만 겹칠 수 있음 # 재생 시..
2023.04.06 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 기존 컨베이어 벨트와 보조 컨베이어 벨트를 각각 Queue와 Stack으로 만든 뒤, 주어진 조건에 만족하도록 구현했다. # 1 ~ n 까지의 택배를 재 배열 # 기존 컨베이어 : queue -> 작은 수부터 빼낼 수 있음 # 보조 컨베이어 : Stack -> 큰 수부터 빼낼 수 있음 # 몇 개의 상자를 실을 수 있는지 # order의 상자가 나올 때 까지 pop from collections import deque def solution(order): order = deque(order..
[Python] 프로그래머스 택배상자 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 기존 컨베이어 벨트와 보조 컨베이어 벨트를 각각 Queue와 Stack으로 만든 뒤, 주어진 조건에 만족하도록 구현했다. # 1 ~ n 까지의 택배를 재 배열 # 기존 컨베이어 : queue -> 작은 수부터 빼낼 수 있음 # 보조 컨베이어 : Stack -> 큰 수부터 빼낼 수 있음 # 몇 개의 상자를 실을 수 있는지 # order의 상자가 나올 때 까지 pop from collections import deque def solution(order): order = deque(order..
2023.04.05 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 Orders 배열의 원소 크기가 작고, 조합을 확인해야 하는 Course의 크기 또한 크지 않다. 따라서 모든 세트 조합을 구하더라도 시간 초과가 발생하진 않는다. 세트 조합을 구하는 과정에서 주의할 점은 알파벳 순서가 다르더라도 동일한 세트로 처리해야 한다는 점이다. 이후엔 문제에서 주어진 조건에 맞게 필터링하면 된다. # 각 손님들이 주문할 때, 가장 많이 함께 주문한 단품 메뉴를 코스 요리 메뉴로 구성 # 코스 요리 : 최소 2 가지 단품 + 최소 2 명의 손님이 주문했던 제품 만 ..
[Python] 프로그래머스 메뉴 리뉴얼 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 Orders 배열의 원소 크기가 작고, 조합을 확인해야 하는 Course의 크기 또한 크지 않다. 따라서 모든 세트 조합을 구하더라도 시간 초과가 발생하진 않는다. 세트 조합을 구하는 과정에서 주의할 점은 알파벳 순서가 다르더라도 동일한 세트로 처리해야 한다는 점이다. 이후엔 문제에서 주어진 조건에 맞게 필터링하면 된다. # 각 손님들이 주문할 때, 가장 많이 함께 주문한 단품 메뉴를 코스 요리 메뉴로 구성 # 코스 요리 : 최소 2 가지 단품 + 최소 2 명의 손님이 주문했던 제품 만 ..
2023.03.31 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가짓수를 동일하게 케이크를 분리해야 한다. 앞 케이크 분리 시, 뒷 케이크의 일부 성분이 없어져 가짓수가 바뀔 수 있다는 것을 주의해야 한다. 이 생각을 안하고 이분 탐색으로 접근해서 풀었고, 결국 스스로 푸는데는 실패했다. 아래는 다른 사람의 코드를 보고 이해한 내용이다. 각 케이크 가짓수를 따로 저장해서 관리 우선 각 케이크의 idx 별 가짓수를 pt1_cnt, pt2_cnt에 저장한다. 모두 저장이 끝나면 pt1_cnt[i]와 pt2_cnt[i + 1] 이 동일한 지 확인하고, 그 ..
[Python] 프로그래머스 롤케이크 자르기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가짓수를 동일하게 케이크를 분리해야 한다. 앞 케이크 분리 시, 뒷 케이크의 일부 성분이 없어져 가짓수가 바뀔 수 있다는 것을 주의해야 한다. 이 생각을 안하고 이분 탐색으로 접근해서 풀었고, 결국 스스로 푸는데는 실패했다. 아래는 다른 사람의 코드를 보고 이해한 내용이다. 각 케이크 가짓수를 따로 저장해서 관리 우선 각 케이크의 idx 별 가짓수를 pt1_cnt, pt2_cnt에 저장한다. 모두 저장이 끝나면 pt1_cnt[i]와 pt2_cnt[i + 1] 이 동일한 지 확인하고, 그 ..
2023.03.30 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 x에서 y 까지의 최소 이동 횟수를 구하기 위해서 BFS를 활용했다. 이때 x와 y가 같은 경우엔, 이동 횟수가 0으로도 도달 가능하기에 미리 예외 처리를 해줬다. # 최소 연산 횟수? # y 까지의 위치를 저장하는 배열 생성 후 BFS from collections import deque def bfs(map_info: list, start: int, end: int, n: int) -> int: queue = deque() queue.append(start) # BFS 시작 while..
[Python] 프로그래머스 숫자 변환하기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 x에서 y 까지의 최소 이동 횟수를 구하기 위해서 BFS를 활용했다. 이때 x와 y가 같은 경우엔, 이동 횟수가 0으로도 도달 가능하기에 미리 예외 처리를 해줬다. # 최소 연산 횟수? # y 까지의 위치를 저장하는 배열 생성 후 BFS from collections import deque def bfs(map_info: list, start: int, end: int, n: int) -> int: queue = deque() queue.append(start) # BFS 시작 while..
2023.03.24 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 재귀를 활용한 풀이 : 코드 작성 실패 n 이 3 보다 클 경우, 전체 삼각형은 외부 삼각형, 내부 삼각형으로 분리할 수 있다는 점을 주목해 풀이를 시도했다. 코드 작성엔 실패했고, 다른 사람이 작성한 아래 코드를 보고 이해한 뒤 주석을 작성했다. arr = [] def draw(x, y, cnt, num): if cnt < 1: return number = num # 삼각형의 좌측 대각선 for i in range(cnt): arr[x + i][y] = number number += 1..
[Python] 프로그래머스 삼각 달팽이 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 재귀를 활용한 풀이 : 코드 작성 실패 n 이 3 보다 클 경우, 전체 삼각형은 외부 삼각형, 내부 삼각형으로 분리할 수 있다는 점을 주목해 풀이를 시도했다. 코드 작성엔 실패했고, 다른 사람이 작성한 아래 코드를 보고 이해한 뒤 주석을 작성했다. arr = [] def draw(x, y, cnt, num): if cnt < 1: return number = num # 삼각형의 좌측 대각선 for i in range(cnt): arr[x + i][y] = number number += 1..
2023.03.23 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 완전 탐색으로 접근할 경우 $O(N^2)$ 이고, numbers의 길이는 최대 100만이기 때문에 시간 초과가 발생한다. 뒷 큰수는 앞에서 부터 값을 보관해 뒀다가, 더 큰 값이 나오면 제거하고, answer 정보를 업데이트하는 방식으로도 얻을 수 있다. 이 경우 스택에 값 numbers의 idx를 저장해두고, numbers의 숫자가 가장 최근에 입력된 값과 유사한 지 비교하면 된다. # 자신보다 뒤 + 크면서 가장 가까이 있는 수 : 뒷 큰수 # 뒷 큰수가 없으면 -1 # 완전 탐색 불..
[Python] 프로그래머스 뒤에 있는 큰 수 찾기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 완전 탐색으로 접근할 경우 $O(N^2)$ 이고, numbers의 길이는 최대 100만이기 때문에 시간 초과가 발생한다. 뒷 큰수는 앞에서 부터 값을 보관해 뒀다가, 더 큰 값이 나오면 제거하고, answer 정보를 업데이트하는 방식으로도 얻을 수 있다. 이 경우 스택에 값 numbers의 idx를 저장해두고, numbers의 숫자가 가장 최근에 입력된 값과 유사한 지 비교하면 된다. # 자신보다 뒤 + 크면서 가장 가까이 있는 수 : 뒷 큰수 # 뒷 큰수가 없으면 -1 # 완전 탐색 불..
2023.03.22 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 DFS를 활용한 풀이 : 시간 초과 문자 조합을 구성하기 위해서 DFS를 활용했다. 조합 구성 시, 순서를 유지하기 위해서 start 변수를 도입해 탐색 범위를 제한했다. 시간 초과가 발생했다. 풀이의 시간 복잡도는 ${n \choose k}$ 인데, n과 k가 최대 100만 까지 가능하기 때문이다. 더보기 DFS 함수의 시간 복잡도 T(dfs) = (n-k) choose (k-1) + (n-k+1) choose (k-1) + ... + n choose (k-1) = (n+1) choos..
[Python] 프로그래머스 큰 수 만들기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 DFS를 활용한 풀이 : 시간 초과 문자 조합을 구성하기 위해서 DFS를 활용했다. 조합 구성 시, 순서를 유지하기 위해서 start 변수를 도입해 탐색 범위를 제한했다. 시간 초과가 발생했다. 풀이의 시간 복잡도는 ${n \choose k}$ 인데, n과 k가 최대 100만 까지 가능하기 때문이다. 더보기 DFS 함수의 시간 복잡도 T(dfs) = (n-k) choose (k-1) + (n-k+1) choose (k-1) + ... + n choose (k-1) = (n+1) choos..
2023.03.09 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 쿼드 압축은 매 시행 마다 압축이 가능한 지 확인하고, 불가능하다면 4개의 동일한 부분을 나눠서 다시 확인한다. 압축 시도 → 분할 후 압축 재 시도의 과정이 반복되기 때문에 재귀 함수를 활용할 수 있다. 압축의 형태를 비교하는 과정에서, 2차원 리스트 슬라이싱이 필요했다. 리스트를 2차원 슬라이싱 하려면, 다음과 같이 리스트 컴프리헨션을 사용하면된다. [row[j : j + n // 2] for row in arr[i : i + n // 2]] # (0의 개수, 1의 개수) # 재귀? ..
[Python] 프로그래머스 쿼드압축 후 개수 세기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 쿼드 압축은 매 시행 마다 압축이 가능한 지 확인하고, 불가능하다면 4개의 동일한 부분을 나눠서 다시 확인한다. 압축 시도 → 분할 후 압축 재 시도의 과정이 반복되기 때문에 재귀 함수를 활용할 수 있다. 압축의 형태를 비교하는 과정에서, 2차원 리스트 슬라이싱이 필요했다. 리스트를 2차원 슬라이싱 하려면, 다음과 같이 리스트 컴프리헨션을 사용하면된다. [row[j : j + n // 2] for row in arr[i : i + n // 2]] # (0의 개수, 1의 개수) # 재귀? ..
2023.03.07 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 문자열을 구성하기 위한 방법으로는 순열, 백트래킹을 활용한 DFS가 있다. DFS 과정에서 각 종이(숫자)가 한 번만 활용돼야 하기 때문에 is_used 라는 변수를 활용했다. # 가능한 문자열 구성하기 def dfs(numbers, n_len, num): global cnt, is_used, num_uniq # 문자열 길이 최대일 경우 if n_len == len(numbers): return for i in range(len(numbers)): if not is_used[i]:..
[Python] 프로그래머스 소수 찾기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 문자열을 구성하기 위한 방법으로는 순열, 백트래킹을 활용한 DFS가 있다. DFS 과정에서 각 종이(숫자)가 한 번만 활용돼야 하기 때문에 is_used 라는 변수를 활용했다. # 가능한 문자열 구성하기 def dfs(numbers, n_len, num): global cnt, is_used, num_uniq # 문자열 길이 최대일 경우 if n_len == len(numbers): return for i in range(len(numbers)): if not is_used[i]:..
2023.03.06 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 섹션이 이미 순서대로 정렬돼 있다. 그래서 앞에서부터(뒤에서부터) 차례로 칠하기만 해도 최소 덧칠 횟수가 만족된다. # N 개의 구역 (1 ~ N 라벨) # M 미터 -> 구역 초과 X # 반복해도 되지만, 최소화해야 함 # 끝에서 부터 확인하면 될 듯 -> 윈도우가 범위 안 넘어가면 색칠 # 순서 유지돼야 함 -> 윈도우 내 최소 값 보다 마지막 성분이 큰 경우 pop() def solution(n, m, section): cnt = 0 # 모든 영역을 다 칠할 때 까지 반복 while..
[Python] 프로그래머스 덧칠하기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 섹션이 이미 순서대로 정렬돼 있다. 그래서 앞에서부터(뒤에서부터) 차례로 칠하기만 해도 최소 덧칠 횟수가 만족된다. # N 개의 구역 (1 ~ N 라벨) # M 미터 -> 구역 초과 X # 반복해도 되지만, 최소화해야 함 # 끝에서 부터 확인하면 될 듯 -> 윈도우가 범위 안 넘어가면 색칠 # 순서 유지돼야 함 -> 윈도우 내 최소 값 보다 마지막 성분이 큰 경우 pop() def solution(n, m, section): cnt = 0 # 모든 영역을 다 칠할 때 까지 반복 while..
2023.03.06