명이나물 라이브러리

프로그래머스 K번째수정렬 알고리즘을 공부한 뒤, 연습 문제로 프로그래머스 K번째수 문제를 풀어보았다.문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42748사용 언어: Java풀이 시간: 약 24분제한 시간: 30분결과: 성공남은 시간: 약 6분처음에는 단순히 배열을 자르고 정렬하면 되는 문제라고 생각했다.하지만 직접 풀어보니 Arrays.copyOfRange() 사용법, 인덱스 처리, 원본 배열 보존 여부가 중요한 문제였다.1. 문제 설명배열 array의 i번째 숫자부터 j번째 숫자까지 자른 뒤,자른 배열을 정렬했을 때 k번째에 있는 수를 구하는 문제이다.문제 흐름1. array의 i번째부터 j번째까지 자른다.2. 자른 배열을 정렬한..

할인 행사 - 고정길이 슬라이딩 윈도우로 풀기문제를 풀게 된 이유슬라이딩 윈도우를 공부한 뒤, 실제 문제에 적용해보기 위해 프로그래머스의 할인 행사 문제를 풀어봤다.이 문제는 10일 동안 할인하는 상품 목록을 확인해서, 내가 원하는 상품과 수량을 모두 구매할 수 있는 회원가입 날짜의 개수를 구하는 문제다.처음 문제를 봤을 때는 단순히 10일씩 잘라서 확인하면 될 것 같았다.하지만 직접 코드를 작성해보니, 단순 반복보다 고정길이 슬라이딩 윈도우로 푸는 게 더 깔끔하다는 걸 알게 됐다.문제 이해회원가입을 하면 가입한 날부터 10일 동안 할인 상품을 구매할 수 있다.예를 들어 내가 원하는 상품이 다음과 같다고 하자.want = ["banana", "apple", "rice", "pork", "pot"];num..

연속된 부분 수열의 합 Java 풀이 — 투포인터로 시간초과 해결하기1. 문제 소개이번에 풀어본 문제는 프로그래머스 Lv.2 문제인 연속된 부분 수열의 합이다.문제에서는 비내림차순으로 정렬된 정수 배열 sequence와 정수 k가 주어진다.이때 합이 k가 되는 연속된 부분 수열을 찾아, 해당 구간의 시작 인덱스와 마지막 인덱스를 배열로 반환해야 한다.조건은 다음과 같다.부분 수열의 합은 k여야 한다.합이 k인 부분 수열이 여러 개라면 길이가 가장 짧은 수열을 선택한다.길이도 같다면 시작 인덱스가 더 작은 수열을 선택한다.처음에는 단순히 모든 구간의 합을 구하면 되지 않을까 생각했다.하지만 제한사항을 보고 완전탐색으로는 풀기 어렵다는 것을 알 수 있었다.2. 제한사항 확인문제의 제한사항은 다음과 같다.5 ..

https://www.acmicpc.net/problem/10026문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하..

https://www.acmicpc.net/problem/1049 문제 Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다. 끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 ..

문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 나의 풀이 풀이1 [BFS] # 10:42 ~ 11:28 A, B = map(int, input().split()) def multipy(x): return x * 2 def append(x): return int(str(x)+"1") from collections import deque q = deque([(A,1)]) r =-1 while..

https://www.acmicpc.net/problem/4796 문제 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V) 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고..

https://www.acmicpc.net/problem/4963 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개..

https://www.acmicpc.net/problem/1439 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가..