본문 바로가기

Algorithm Practice18

[Programmers] 뒤에 있는 큰 수 찾기 (Java / Python) 문제링크 문제요약 정수 배열에서 각 원소들에 대해 자신보다 뒤에 있고 자신보다 큰 수 중에, 가장 가까운 수를 뒷 큰수라고 정의한다. 뒷 큰수가 존재하지 않는 경우, -1로 정의한다. 정수로 이루어진 배열 numbers가 있을 때, 모든 원소의 뒷 큰수를 차례로 담은 배열을 return하는 함수를 만들어 보자. 제한사항 4 ≤ numbers의 길이 ≤ 1,000,000 1 ≤ numbers[i] ≤ 1,000,000 문제풀이 1차원 적으로 보았을 때, 맨 첫 원소부터 순서대로 자신보다 큰 수를 찾으면 된다. 이런 풀이는 매우 간단하지만, 이중 for문을 사용하기 때문에 시간복잡도가 O(N^2)이 된다. 제한 사항을 확인해보면, 배열의 최대길이가 100만으로 매우 크기 때문에, 이러한 방법으로는 시간초과가.. 2023. 9. 1.
[Programmers] 무인도 여행 (Java/Python) 문제링크 문제요약 다음과 같은 조건을 만족하는 무인도의 지도가 있다. 지도는 1 x 1 크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있다. 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룬다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타낸다. 지도를 나타내는 문자열 배열 maps가 주어질 때, 각 섬에서 머물 수 있는 최대 일수를 배열에 오름차순으로 담아 return 하는 함수를 만들어보자. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 한다. 제한사항 3 ≤ maps의 길이 ≤ 100 .. 2023. 9. 1.
[Programmers] 호텔 대실 (Java/Python) 문제 링크 문제요약 최소한의 객실만을 사용하여 예약손님을 받으려고 한다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다른 손님들이 사용할 수 있다. 예약 시간이 문자열 형태로 담긴 2차원 배열 'booktime'이 매개변수로 주워질 떄, 최소 객실의 수를 return하는 함수를 만들어라. 제한사항 1 ≤ book_time의 길이 ≤ 1,000 book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열 [대실 시작 시각, 대실 종료 시각] 형태 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지. 예약 시각이 자정을 넘어가는 경우는 없음 시작 시각은 항상 종료 시각보다 빠름 입출력 예 book_time result [["1.. 2023. 9. 1.
[Programmers] 둘만의 암호 (Java / Python) 문제 링크 문제 요약 두 문자열 's'와 'skip', 그리고 자연수 index가 주어질 때, 다음 규칙에 따라 새로운 문자열을 만들어 보자. 문자열 s의 각 알파벳을 index만큼 뒤의 알파벳으로 바꿔준다. index만큼 뒤의 알파벳이 z를 넘어갈 경우, 다시 a로 돌아간다. skip에 있는 알파벳을 제외하고 건너뛰어야 한다. 제한사항 5 ≤ s의 길이 ≤ 50 1 ≤ skip의 길이 ≤ 10 s와 skip은 알파벳 소문자로만 이루어져 있습니다. skip에 포함되는 알파벳은 s에 포함되지 않습니다. 1 ≤ index ≤ 20 입출력 예 s skip index result "aukks" "wbqd" 5 "happy" 문제풀이 우선 s = "a", index = "3"이라 생각해보면, a의 만큼 뒤에있는 .. 2023. 9. 1.

티스토리툴바