💡문제 설명
1 ~ n
의 번호가 있는 택배 상자가 창고에 있습니다. 당신은 택배 상자들을 다음과 같이 정리했습니다.
왼쪽에서 오른쪽으로 가면서 1번 상자부터 번호 순서대로 택배 상자를 한 개씩 놓습니다. 가로로 택배 상자를 w
개 놓았다면 이번에는 오른쪽에서 왼쪽으로 가면서 그 위층에 택배 상자를 한 개씩 놓습니다. 그 층에 상자를 w
개 놓아 가장 왼쪽으로 돌아왔다면 또다시 왼쪽에서 오른쪽으로 가면서 그 위층에 상자를 놓습니다. 이러한 방식으로 n
개의 택배 상자를 모두 놓을 때까지 한 층에 w
개씩 상자를 쌓습니다.
- 위 그림은
w
= 6일 때 택배 상자 22개를 쌓은 예시입니다.
다음 날 손님은 자신의 택배를 찾으러 창고에 왔습니다. 당신은 손님이 자신의 택배 상자 번호를 말하면 해당 택배 상자를 꺼내줍니다. 택배 상자 A를 꺼내려면 먼저 A 위에 있는 다른 모든 상자를 꺼내야 A를 꺼낼 수 있습니다. 예를 들어, 위 그림에서 8번 상자를 꺼내려면 먼저 20번, 17번 상자를 꺼내야 합니다.
당신은 꺼내려는 상자 번호가 주어졌을 때, 꺼내려는 상자를 포함해 총 몇 개의 택배 상자를 꺼내야 하는지 알고 싶습니다.
창고에 있는 택배 상자의 개수를 나타내는 정수 n
, 가로로 놓는 상자의 개수를 나타내는 정수 w
와 꺼내려는 택배 상자의 번호를 나타내는 정수 num
이 매개변수로 주어집니다. 이때, 꺼내야 하는 상자의 총개수를 return 하도록 solution 함수를 완성해 주세요.
🚫제한사항
- 2 ≤
n
≤ 100
- 1 ≤
w
≤ 10
- 1 ≤
num
≤n
테스트 케이스 구성 안내아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
|---|---|---|
| #1 | 10% | ```w``` = 1 |
| #2 | 20% | ```n``` 은 ```w``` 의 배수입니다. |
| #3 | 70% | 추가 제한 사항 없음 |
🔢입출력 예
| n | w | num | result |
|---|---|---|---|
| 22 | 6 | 8 | 3 |
| 13 | 3 | 6 | 4 |
🔍입출력 예 설명
입출력 예 #1
문제 예시와 같습니다. 꺼내야 하는 상자의 총개수는 8번 상자를 포함해 3개입니다.
입출력 예 #2
6번 상자를 꺼내려면 먼저 13, 12, 7번 상자를 꺼내야 합니다.
따라서 4를 return 합니다.
💻코드
def solution(n, w, num):
answer = 0
# 가로의 길이와 딱 맞아 떨어지는 숫자 (6, 12, 18)가 있기 때문에 -1 해준다.
rows = (num - 1) // w
# 행의 최대 길이
row_line = n // w + 1 if n % w else n // w
# 열 찾기
if rows % 2 == 0:
col = (num - 1) % w
else:
col = (w -(num - 1) % w) - 1
# 스택 만들 때 이미 1,2,3,4,5 ...는 넣었기 떄문에 1번 안해도 된다
for _ in range(stack_num-1):
# 역방향
if prev_flag == 1:
# 11 9 7 5 3 1 으로 진행
for i in range(2*w-1, 0, -2):
# 시작이 6이기 때문에 -1을 먼저 한다
storage_num -= 1
now_num = (i) + storage[storage_num][-1]
# 넣어야 하는 값이 택배 개수를 초과하면 넣지 않고 넘기기
if now_num > n:
continue
storage[storage_num].append(now_num)
# 정방향
else:
# 1 3 5 7 9 11 으로 진행
for i in range(1, 2*w, 2):
now_num = (2*w - i) + storage[storage_num][-1]
# print(2*w - i, storage[storage_num][-1], now_num)
# 넣어야 하는 값이 택배 개수를 초과하면 넣지 않고 넘기기
if now_num > n:
storage_num += 1
continue
storage[storage_num].append(now_num)
storage_num += 1
# 정방향으로 다 넣으면 역방향으로 바꾸기
if prev_flag == 1:
prev_flag = 0
else:
prev_flag = 1
# 택배 개수보다 초과되면 멈추기
if now_num > n:
break
# print(storage)
for i in range(len(storage)):
try:
num_index = storage[i].index(num)
stack_num = i
except:
pass
print(f'n: {n}, w: {w}, num: {num}')
print(len(storage[stack_num]) - 1)
if __name__ == '__main__':
n = 13
w = 3
num = 6
# 몇 번째 라인인지는 모르지만 행이 1번째에 있음을 알 수 있음
# 6 12 18과 같이 딱 떨어지는 숫자여도 같은 행에 있으니 미리 -1
row_line = (num - 1) // w
print(row_line, '행')
# 전체 행의 수
rows = n // w
if n % w != 0:
rows += 1
# row_line -= 1
# rows -= 1
print(f'현재 위치: {row_line}행에 위치해 있고 그 행의 수는 {rows}칸')
# 열 위치 찾기
# 정방향 (왼 -> 오), 1 3 5 7 9 ...
if row_line % 2 == 0:
column = (num - 1) % w
# 역방향 (오 -> 왼), 11 9 7 5 ....
else:
column = w - (num - 1) % w - 1
storage = []
for r in range(rows):
# 짝수 행
if r % 2 == 0:
'''
현재 행의 값
현재 행 : r => 0
전체 열의 수: w = > 짝수수이기 때문에 0 2 4 6...
해당 숫자가 있는 열 위치: column => 0 1 2 3 4 5 <= w-1
값이 1부터 시작하기 때문에 +1
ex) 2행인 경우
r(2행) * w(총 6개의 열) + column(4열) + 1
2행이기 때문에 최대 열(6) 의 2배인 12부터 시작
12로부터 열(4)만큼 더한 곳에 위치해 있음
숫자는 1부터 시작하기 때문에 마지막에 +1
==> 2행 4열 ==> 17
'''
curr_num = row * w + col + 1
stacks.append(curr_num)
# 행이 홀수인 경우
else:
'''
2행 이기 때문에 해당 행의 최대값은 2*열의 최대값
(r + 1) * w ==> 2 * 6 == > 12
홀수 행은 오른쪽에서 왼쪽으로 숫자가 커지기 때문에 왼쪽에 있는 숫자가 가장 큼
오른쪽으로 갈 수록 숫자가 줄어들기 때문에 열의 수(4)만큼 작아짐
'''
curr_num = (row + 1) * w - col
stacks.append(curr_num)
# 만약 최대 숫자를 넘어서면 하나 뺌
if curr_num > n:
stacks.pop()
break
<<<<<<< HEAD
print(len(storage) - storage.index(num))
print('='*20)
rows = n // w
if n % w > 0:
rows += 1
print(rows)
col = num // w - 1
print(col)
=======
answer = len(stacks) - stacks.index(num)
return answer
>>>>>>> c56de94cafdd62c7ad9cd8b2449381f5bbe648d3
https://school.programmers.co.kr/learn/courses/30/lessons/389478?language=python3
