[programmers] 2016년, 뒤에 있는 큰 수 찾기, 공 이동 시뮬레이션
💡 오늘의 학습 키워드
- 2016년
- 뒤에 있는 큰 수 찾기
- 공 이동 시뮬레이션
🥉 2016년
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12901
문제 설명
2016년 1월 1일은 금요일입니다.
2016년 a월 b일은 무슨 요일일까요?
두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요.
요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다.
예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.
제한 조건
1. 2016년은 윤년입니다.
2. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
요일과 월 별 일수를 저장한 리스트 세팅을 기본으로 풀이가 진행됩니다.
입력 받은 월, 일에 해당하는 요일을 알기 위해서 진행해야 하는 풀이 로직은 다음과 같습니다.
- 입력 받은 월, 일을 총 일 수로 변환합니다.
- 총 일 수에 주 단위인 7로 나눈 나머지가 해당 요일의 인덱스 값으로 리턴됩니다.
다만 주의해야 할 점은 1월 1일이 금요일이라는 점입니다.
이 점을 고려하여 요일이 저장된 리스트를 금요일부터 시작되도록 설정합니다.
그리고 리스트의 인덱스는 0부터 시작하므로 -1 을 해주면 올바른 결과 값을 리턴할 수 있습니다.
💡 내가 해결한 방식은?
반복문을 통한 풀이
def solution(a, b):
answer = ''
days_sum = 0
# 기본 요일과 월 별 일수를 리스트로 저장
days = ["FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU"]
month_days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
# 총 일수 계산하기
for i in range(a-1):
days_sum += month_days[i]
days_sum += b
# (총 일수를 주 단위(7)로 나눈 나머지) - 1) 인덱스에 해당하는 요일 저장하기
answer = days[(days_sum % 7) -1]
return answer개선한 코드
def solution(a, b):
days_sum = 0
days = ["FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU"]
month_days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
return days[(sum(month_days[:a-1])+(b-1)) % 7]
🥈 뒤에 있는 큰 수 찾기
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539
문제 설명
정수로 이루어진 배열 numbers 가 있습니다.
배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers 가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을
return 하도록 solution 함수를 완성해주세요.
단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.
제한 사항
4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
numbers의 크기가 1,000,000 이므로 시간 복잡도가 O(n^2)이 되지 않도록 주의해야 합니다.
다시 말해 각 원소에 대해 자신보다 큰 값을 찾는 과정에서 시간복잡도가 O(1)이 되는 접근법을 발견해야 합니다.
단순 리스트로 문제 해결 과정을 세팅하면 TC 일부만 통과하고 시간 초과되는 것을 확인할 수 있습니다.
이를 확인하기 위해 먼저 리스트 인덱스 순서로 반복문을 순회하며 코드를 작성해보았습니다.
numbers 이후 값을 저장한 리스트를 numbers[i+1:] 로 구현해 기존 값과 반복 비교할 수 있도록 했습니다.
여기서 매번 numbers를 순회할 때마다 numbers[i+1:] 리스트를 새로 생성하고,
또 범위 반복으로 중복 순회를 하게 되는데, 이 과정에서 O(n^2) 시간복잡도가 발생하는 것을 알 수 있습니다.
제출해보니 대부분 TC에서 시간 초과가 발생하는 것을 확인할 수 있었습니다.
numbers[i+1:] 범위의 새로운 리스트를 생성하여 반복 순회하지 않도록 다른 접근법이 필요했습니다.
그전에 먼저 이중 반복문으로 여전히 O(n^2)이지만 numbers[i+1:] 부분 리스트를 생성하지 않는
역순으로 반복 순회하는 방법이 어느정도 효율성을 가지는지 확인해보았습니다.
다음은 역순을 통한 풀이 코드를 구현하면서 새롭게 알게 된 리스트 활용법입니다.
answer[::-1]
이는 answer 리스트의 요소들을 역순으로 반환하는 것을 의미합니다.
역순을 통해 부분 리스트 생성과정이 없어 전체적인 실행 시간을 단축시킬 수 있었습니다.
하지만 여전히 O(n^2) 시간복잡도의 한계로 일정 크기에 다다르면 시간 초과가 발생했습니다.
이를 해결하기 위해 각 원소에 대한 탐색 과정이 최악의 경우도 O(1)을 유지하는 stack을 사용했습니다.
stack을 사용하면 내부 반복문에서 stack의 top 원소와 비교하며 최대 한번씩만 pop 해주게 됩니다.
즉, stack에 numbers의 인덱스를 넣어 연산을 진행하게 되면 내부 반복문에서 매번 전체 순회를 하지 않습니다.
(구해야하는 numbers의 인덱스 위치가 append 된) stack top에 위치한 값부터 외부 반복문 순회에 맞춰
전체 리스트 인덱스와의 비교를 반복하는데, 여기서 만약 큰 수에 해당되지 않는다면 stack에서 pop 되지 못하고
해당 인덱스 값은 -1로 초기화한 값 그대로 유지되는 것입니다.
💡 내가 해결한 방식은?
이중 반복문을 통한 큰 수 탐색 (시간 초과)
def solution(numbers):
answer = []
# numbers 리스트를 순회
for i, num in enumerate(numbers):
# numbers 이후 값을 저장하는 next 리스트를 생성
found = 0
for next_num in numbers[i+1:]:
if num < next_num:
answer.append(next_num)
found = 1
break
# numbers 보다 큰 수가 없을 경우 -1 저장
if found == 0:
answer.append(-1)
return answer역순을 통한 큰 수 탐색 (시간 초과)
def solution(numbers):
answer = []
for i in range(len(numbers)-1, -1, -1):
max_val = -1
for j in range(i+1, len(numbers)):
if numbers[i] < numbers[j]:
max_val = numbers[j]
break
answer.append(max_val)
return answer[::-1]스택을 통한 큰 수 탐색
def solution(numbers):
answer = [-1] * len(numbers)
# 스택 리스트를 통해 numbers 인덱스를 저장
stack = []
for idx in range(len(numbers)):
# stack의 top과 numbers 값 비교
while stack and numbers[stack[-1]] < numbers[idx]:
answer[stack.pop()] = numbers[idx]
# 스택에 인덱스 정수를 저장합니다
stack.append(idx)
return answer
🥇 공 이동 시뮬레이션
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87391
문제 설명
n행 m열의 격자가 있습니다.
격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다.
당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.
열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))
단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가
더 이상 이동할 수 없을 때 멈추게 됩니다.
예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때
query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다.
(격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)
격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는
2차원 정수 배열 queries가매개변수로 주어집니다.
n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때,
x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
1. 1 ≤ n ≤ 10^9
2. 1 ≤ m ≤ 10^9
3. 0 ≤ x < n
4. 0 ≤ y < m
5. 1 ≤ queries의 행의 개수 ≤ 200,000
5-1. queries의 각 행은 [command,dx] 두 정수로 이루어져 있습니다.
5-2. 0 ≤ command ≤ 3
5-3. 1 ≤ dx ≤ 10^9
5-4. 이는 query(command, dx)를 의미합니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
격자의 범위가 10의 9승이라면 완전 탐색으로는 풀지 못하고 다른 효율적인 접근법이 필요합니다.
따라서 범위를 한정하여 도착점에서 시작하여 도착점으로 다시 돌아오는 경우의 수를 찾도록 코드를 구현해야 합니다.
(문제 해결 중)
💡 내가 해결한 방식은?
잘못된 풀이
def go(a, b, queries):
dy = [q[1] for q in queries if q[0] == 0 or q[0] == 1]
dx = [q[1] for q in queries if q[0] == 2 or q[0] == 3]
y, x = a, b
for i in range(len(queries)):
ny = y + dy[i]
nx = x + dx[i]
if ny < 0 or nx < 0 or ny >= 2 or nx >= 2: continue
go(ny, nx)
def solution(n, m, x, y, queries):
global answer
answer = 0
# 격자의 모든 좌표를 순회
for i in range(n):
for j in range(m):
# 각 시작점에 대해 go 함수 호출
go(i, j, queries)
if i == x and j == y:
answer += 1
return answer✍️ TIL
첫 번째 문제가 가장 재미있었다. 나는 어떻게 하면 효율적인 풀이로 끝낼 수 있을까 고민하며 풀었는데
다른 사람의 풀이에 들어가보니 예술 작품이 전시되어 있었다 (궁금하면 직접 구경하기ㅋㅋ)
두 번째 문제는 시간 복잡도 싸움이라는 걸 알고 있었지만 그럼에도 맞아보고 싶어서
반복문 풀이로 정면 승부를 해보았다. 역순으로 변조를 걸어보아도 어림도 없이 시간 초과를 당했다.
스택을 비우는 것처럼 내 마음도 비우는 연습을 해야겠다. 요즘 너무 욕심이 많아 다 놓칠까봐 겁이나서..
마지막 챌린지 문제는 비록 풀기에 버겁더라도 계속해서 추가하려 한다. 볼때마다 고민해봐야지