출처
: Programmers
문제
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
n행n열 크기의 비어있는 2차원 배열을 만듭니다.- i = 1, 2, 3, …, n에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
- 1행, 2행, …,
n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. - 새로운 1차원 배열을
arr이라 할 때,arr[left],arr[left+1], …,arr[right]만 남기고 나머지는 지웁니다. 정수n,left,right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤
n≤ $10^7$ - 0 ≤
left≤right< $n^2$ right-left< $10^5$
(생략)
나의 풀이(시도)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
def solution(n, left, right):
filled_arr = make_one_dim_arr(n, left, right)
print("result=>", filled_arr)
answer = []
return answer
def make_one_dim_arr(n, left, right):
'''
아니 그냥
[1, 2, 3, 4]에서 1만 2로 바꾸고
[2, 2, 3, 4]에서 2만 3으로 바꾸면 됨
그리고 left, right로 미리 잘라야됨
'''
'''
아예 처음부터
[left, right+1] 범위에서만
생성되도록 하면 효율적일텐데
'''
# size = n**2
# iter 범위
# => [left_cut, right_cut+1]로 좁힘
left_cut = left // n
minus_pad = (left_cut)*n
left = left - minus_pad
right_cut = right // n
right = right - minus_pad
print(left, right)
'''
입력이 10^7이므로
2중 for문은 안될것같음
이거의 핵심은 결국
[1, 2, 3, 4]를 [4, 4, 4, 4]로
차례대로 변경시키는 건데
그럼 iter 범위를 (n/2)로 줄이고
한 번 iter당
연산을 양쪽에서 두번은 안될까?
'''
init_list_front = [(_+1) for _ in range(n)]
init_list_post = [n for _ in range(n)]
sum_front = []
sum_post = init_list_post.copy()
# 범위를 절반으로 나눔
# 홀수인 경우 고려해서 (+1)
for i in range(int(n/2)+1):
if (i < left_cut
or i>= right_cut+1):
continue
# 짝수인 경우
# 마지막은 양쪽 다 진행 필요 X
if ((i == int(n/2))
and (n % 2 == 0)):
continue
print("--------------")
print(f"iter-\"{i}\"")
# 앞쪽(front)
for j in range(i): ##
init_list_front[j] = i+1
print("front_init\n=>", init_list_front)
sum_front += init_list_front
if i == int(n/2):
print("--------------")
continue
# 뒷쪽(post)
for j in range(n-i-1, -1, -1):##
init_list_post[j] = n-i
# init_list_post.reverse()
init_list_post.reverse()
print("post_init\n=>", init_list_post)
sum_post += init_list_post
print("--------------")
print("front\n=>", sum_front)
sum_post.reverse()
print("post\n=>", sum_post)
print("--------------")
print("--------------")
temp_sum = sum_front+sum_post
print(temp_sum)
sum = temp_sum[left:right + 1]
print(sum)
return sum
이번 문제도 뭔가 쉽게 될 것 같았는데
이리저리 조건을 고려하다보니
일반적으로 포괄하는 코드는 못 짠 것 같다.
일단,
문제에서 설명하는 순서에 맞게 정직하게 하는 건
대부분 비효율적인 결과로 이어질 것 같아보였다.
결국 1차원 배열로 또는 배열처럼 생각하는 게 핵심인데,
그렇다면, 처음부터 1차원 배열식으로 하는 게 나아 보였다.
하지만,
입력값인 배열 크기의 범위가 $0$~$10^7$이기 때문에
정직한 이중 for문은 될 리가 없다.
하지만 한 개의 반복문으로 기가 막히게 인덱싱 하는 건
딱히 떠오르지가 않아 이런저런 조건문을 달게되었다.
그리고 최대한 반복 수를 줄이고자
1
for i in range(int(n/2)+1):
1
2
3
if ((i == int(n/2))
and (n % 2 == 0)):
continue
이런 코드들도 넣게되었지만,
결국 시간초과는 계속 발생했다.
결과적으로 이건 실패했다.
더이상 잡고 있자니 시간이 너무 들 것 같아 그만뒀다.
다른 사람들의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
vector<int> solution(int n, long long left, long long right)
{
vector<int> result;
for (long long i = left; i <= right; i++) // i : 칸의 인덱스
{
long long y = i / n; // y : 해당 칸 y 좌표
long long x = i % n; // x : 해당 칸 x 좌표
result.push_back(max(y, x) + 1);
}
return result; // 2번 칸 ~ 5번 칸에 오는 값들의 배열
}
(출처: [프로그래머스] n^2 배열 자르기 - LEVEL2)
이건 C++이긴 하지만,
역시나 이번에도 내가 너무 복잡하게 생각했다는 걸
통감하게 만들 정도로 심플한 아이디어였다…
결국,
이런저런 리스트 덧셈 과정 없이
그냥 바로 1차원 배열 인덱스에서
배열 크기인 $n$만큼 나눠주면
그게 2차원상의 인덱스가 되는 것이었다..!
위 코드를 바탕으로 파이썬으로 작성해보았다.
1
2
3
4
5
6
7
8
9
def solution(n, left, right):
result = []
for i in range(left, right+1):
x = i % n
y = i // n
which_max = max(x, y)
result.append(which_max + 1)
answer = result
return answer
이러니까 대략 두 자리수 ms 내로 되었다…
보니까
파이썬으로 더 짧게는 이렇게도 될 수 있다.
1
2
3
4
5
def solution(n, left, right):
answer = []
for i in range(left,right+1):
answer.append(max(i//n,i%n)+1)
return answer
(출처: 프로그래머스 스쿨 다른사람 풀이)