[programmers] K번째 수, 덧칠하기, 이진변환 반복하기
💡 오늘의 학습 키워드
- K번째 수
- 덧칠하기
- 이진변환 반복하기
🥉 K번째 수
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42748
문제 설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면,
1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때,
commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록
solution 함수를 작성해주세요.
제한 사항
1. array의 길이는 1 이상 100 이하입니다.
2. array의 각 원소는 1 이상 100 이하입니다.
3. commands의 길이는 1 이상 50 이하입니다.
4. commands의 각 원소는 길이가 3입니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
원하는 인덱스의 범위에 맞게 리스트를 자르고 정렬할 수 있으면 간단하게 풀리는 문제였습니다.
2차원 배열을 순회하며 값이 여러 개일 때 코드 한줄로 다음과 같이 여러 변수에 저장할 수 있습니다.
i, j, k = command
리스트를 다루는 문제이고 특별한 로직이 없어 다음과 같이 한줄로 코드를 개선할 수 있었습니다.
💡 내가 해결한 방식은?
def solution(array, commands):
answer = []
for command in commands:
i, j, k = command
answer.append(sorted(array[i-1:j])[k-1])
return answerdef solution(array, commands):
return [sorted(array[i-1:j])[k-1] for i, j, k in commands]
🥈 덧칠하기
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/161989
문제 설명
어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다.
벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가
철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다.
페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.
넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다.
이를 위해 벽을 1미터 길이의 구역 n개로 나누고,
각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다.
그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.
벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.
- 롤러가 벽에서 벗어나면 안 됩니다.
- 구역의 일부분만 포함되도록 칠하면 안 됩니다.
즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다.
현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.
한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만
다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다.
예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.
정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때,롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.
제한 사항
1. 1 ≤ m ≤ n ≤ 100,000
2. 1 ≤ section의 길이 ≤ n
2-1. 1 ≤ section의 원소 ≤ n
2-2. section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
2-3. section에서 같은 원소가 두 번 이상 나타나지 않습니다.
2-4. section의 원소는 오름차순으로 정렬되어 있습니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
처음에 문제 접근을 잘못해 n 크기로 순회하며 한칸 한칸 순회하며 풀게 되었는데,
반복문이 3중이 되는 순간 풀이를 멈추고 다른 풀이 아이디어를 고민해보았습니다.
처음에는 최소 값을 구하는 문제라 BFS를 생각했습니다.
BFS 풀이로 진행해 보았고, 큰 틀에서 문제 해결 과정은 다음과 같습니다.
- 롤러의 길이를 통해 페인트칠 할 수 있는 마지막 범위 값을 계산합니다.
- 롤러로 칠하는 경계를 벗어나면 새롭게 칠하는 영역으로 수정합니다.
- section 리스트의 모든 값을 순회한 후 위 조건에 최소 페인트 칠 횟수를 리턴합니다.
사실 입출력 예시에서 롤러로 칠하는 경계에 맞게 순회하며 최소 횟수를 구하지 않아
BFS 풀이 이상은 생각하지 않았는데, 코드를 보니 굳이 큐를 사용하지 않아도
section을 순회하며 해결할 수 있다는 것을 알았습니다.
비슷한 로직이지만 그리디 알고리즘을 통한 풀이 방법까지 구현해 보았습니다.
💡 내가 해결한 방식은?
BFS
from collections import deque
def solution(n, m, section):
answer = 0
queue = deque(section)
while queue:
end = queue.popleft() + m - 1
answer += 1
# 큐에 남아있는 구역 중 현재 구역 내 있는 구역들을 모두 처리
while queue and queue[0] <= end:
queue.popleft()
return answer
그리디 알고리즘
def solution(n, m, section):
answer = 1
# 롤러로 칠하는 경계
roller_end = section[0] + m - 1
# section 값들을 순회하여 롤러 길이의 끝보다 큰 값이 나오면 다음 영역부터 칠한다
for i in range(1, len(section)):
# 롤러로 칠하는 경계를 벗어나면 새롭게 칠하는 영역을 더해준다
if roller_end < section[i]:
roller_end = section[i] + m - 1
answer += 1
return answer
🥇 이진 변환 반복하기
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/70129
문제 설명
0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.
x의 모든 0을 제거합니다.x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.
0과 1로 이루어진 문자열 s가 매개변수로 주어집니다.
s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때,
이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아
return 하도록solution 함수를 완성해주세요.
제한 사항
1. s의 길이는 1 이상 150,000 이하입니다.
2. s에는 '1'이 최소 하나 이상 포함되어 있습니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
문제에서 풀이 과정을 명확하게 제시해 주어 바로 코드 구현으로 진행했습니다.
- 입력받은 문자열에서 0의 개수를 구합니다.
- 개수를 모두 세었으면 해당 문자열에서 0을 모두 제거해줍니다.
- 0이 제거된 문자열의 길이를 구합니다.
- 문자열의 길이 값을 다시 이진 값으로 변환해줍니다.
- 변환 횟수를 더하고 값에 0이 없을 때까지 반복합니다.
replace()
0을 제거하는 방법으로 replace 함수가 가장 간편했지만 초기 코드는 아래의 반복문으로 구현했습니다.
s = "".join([char for char in s if char != "0"])문자열 s를 순회하며 0이 아닌 경우를 리스트에 따로 저장하여 join 함수로 문자열 연결해주는 방식이었습니다.
bin()
이진 변환해주는 방법으로 bin( ) 함수를 사용했습니다. 초기 코드는 아래의 별도 함수로 구현했습니다.
def conversion_bin(num):
binary = ""
while num > 0:
binary = binary + str(num % 2)
num // 2
return binarybin( ) 함수 결과에는 "0b" 접두사가 앞에 포함됩니다. 이 부분을 알지 못해 몇 차례 에러를 겪었습니다.
예로 bin(10) 은 '0b1010' 이 출력됩니다.
따라서 접두사를 제외한 값을 출력하기 위해서는 bin( ~ )[2:] 로 표현해주어야 하는 것을 기억해야 합니다.
이와 같은 함수들을 몰라도 코드는 구현할 수 있었지만 알고 있다면 코드를 보다 간결하고 쉽게 작성할 수 있었습니다.
💡 내가 해결한 방식은?
def solution(s):
answer = []
zero_cnt = 0
convert_cnt = 0
while True:
# 문자열이 1일때 break
if s == "1":
break;
# 0 개수 더하기
zero_cnt += s.count("0")
# 0 제거하기
s = s.replace("0", "")
# 제거 후 길이 이진 변환하기
s = bin(len(s))[2:]
# 변환 횟수 더하기
convert_cnt += 1
answer.append(convert_cnt)
answer.append(zero_cnt)
return answerdef solution(s):
answer = []
zero_cnt = convert_cnt = 0
while s != "1":
# 문자열 내 0 개수 세기
zero_cnt += s.count("0")
# 문자열 내 0 제거, 길이 계산 후 이진 변환
s = bin(len(s.replace("0", "")))[2:]
# 변환 횟수 증가
convert_cnt += 1
return [convert_cnt, zero_cnt]
✍️ TIL
문제를 풀다보면 이 방법은 구현은 되더라도 분명 쉽게 풀수 있는 다른 함수나 로직이
있을 거라는 생각이 들 때가 있다. 좋은 코드를 많이 접하는게 우선이니 지금은 빠르게 다양한 접근 방법을
체득하려고 노력한다. 특히 파이썬 함수를 몰라서 코드가 길어지는 경우가 많다.
(이럴 때는 이렇게 TIL을 작성을 핑계로 빠르게 구글링(ㅋㅋ)_)
두 번째 문제에서 시간을 많이 잡아먹었는데 입출력 예시를 보고 거기에 맞춰 로직을 만들어내려다가 봉변을 당했다.
다음에는 핵심 문장을 추리고 해결 방식은 내 주관으로 먼저 구현해야겠다.
세 번째 문제는 문제가 너무 친절했다. 다만 활용해보지 못한 파이썬 함수를 많이 만날 수 있어서 에러가 많이 났다.
회고에는 작성안했는데 답이 튜플 형식이라면 굳이 리스트에 append 하지 않고 마지막 코드처럼
[a, b] 형식으로 리턴해야겠다.