문제
정수 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
문제를 보고 든 생각
진짜 이게 뭔가 싶었다.
일단 2차 배열을 만들 필요는 없을 것 같다는 느낌이 왔다.
그리고 제한사항을 보니까 숫자가 너무 압도적으로 거대했다.
이걸 풀 수 있을까라는 생각이 많이 들었다.
이건 2차 배열로 푸는 문제가 아닐 거라고 확신이 들었다.
나의 아이디어
결국 1차 배열로 만들어서 1차 배열을 슬라이싱해야 하는 문제이므로 1차 배열을 만드는 데에 집중했다.
분명 규칙성이 있을 거라고 판단하고 공책에 n=1부터 6까지 행렬을 만들어 1차 배열로 만들어 보았다.
역시 규칙성이 보였다.
i가 1일 때
1
i가 2일 때
12 22
i가 3일 때
123 223 333
i가 4일 때
1234 2234 3334 4444
i가 5일 때
12345 22345 33345 44445 55555
i * i에 i + 1부터 n까지를 붙여주면 한 개의 행이 완성되는 것이다.
그렇게 1차 배열을 바로 만들고 파이썬의 특권인 슬라이싱으로 답안을 제출하는 게 나의 아이디어였다.
결과
arr = ""
for i in range(n):
arr += ",".join([str(i + 1) for _ in range(i + 1)])
arr += ","
arr += ",".join([str(x) for x in range(i + 2, n + 1)])
arr += ","
if len(arr) >= right * 5:
break
arr = [int(i) for i in arr.rstrip(",").split(",")]
print(arr[left : right + 1])
테스트 케이스 20개 중 8개를 맞았다.
초창기 아이디어에서 놓친 부분이 하나 있었는데 그것은 바로
문자열 형태로 된 숫자를 다시 int형태로 바꿀 때 두 자릿수 이상의 숫자면 숫자가 형변환이 될 때 분해될 수 있다는 문제였다.
즉, "10"이라면 int형으로 형변환을 할 때는 [1,0]으로 변한다는 점을 잊고 있었다.
위의 문제는 1차원 배열을 만들 때 쉼표를 넣어주어 구분될 수 있도록 했다.
그리고 int형으로 형변환을 할 때, split을 이용하여 리스트로 바로 넣어주었다.
하지만, 시간 초과였다.
input을 여러 가지를 넣어보니 left, right 값이 작을 때 n은 10^7의 크기도 견뎠지만 문제는 right의 크기였다.
무려 10^7까지 갈 수 있는 n의 제곱보다는 작은 수였다.
내가 작성했던 코드에서 정말 갖가지 방법을 시도해봐도 시간 초과가 떠서 결국 검색을 이용했다.
검색을 통해 알게 된 내용
정말 어이가 이렇게 없을 수가 없었다.
상상도 못한 풀이 내용이었다.
검색을 통해 알게 된 풀이
arr = []
for i in range(left,right+1):
arr.append(max(i // n, i % n) + 1)
print(arr)이걸 적고 있는 지금도 다시 보니까 너무 어이가 없다.
처음에는 이해도 되지 않았다.
"왜 i // n이랑 i % n 중에서 큰 값을 고르는 거지? 두 개가 뭔 의미지?"
left, right+1을 range의 인자로 넣어주는 건 아주 이해가 됐다.
입력 조건에 의해 들어올 수 있는 숫자의 크기가 너무나도 크기 때문에 문제가 요구하는 사항인 left부터 right까지만 구하는 건 너무나도 좋은 방법일 수밖에 없다.
그래서 나도 그걸 위해서 노력했지만 실패했다.
코드를 보고 내가 공책에 적었던 행렬을 봐도 풀이가 이해가 안 됐다.
그래서 그냥 다음 문제를 풀기로 하고 bfs문제를 푸는 도중, 그래프로 등장한 행렬을 보다가 이해가 돼버렸다.
짧게 말하면, i // n은 인덱스의 x값, i % n은 인덱스의 y값이었던 것이다.
n이 3일 때, 행렬은 아래와 같다.
1 2 3
2 2 3
3 3 3
위의 행렬의 인덱스는 아래와 같다.
(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)
left는 2, right는 5이므로
(0, 2), (1, 0), (1, 1), (1, 2)
max를 골라 그 값에 1을 더해준다.
2 + 1, 1 + 1, 1 + 1, 2 + 1 => 3, 2, 2, 3
그래서 답은 [3,2,2,3]이 된다.
어떻게 이런 생각을 하는 걸까.
느낀 점
나도 멋진 아이디어를 떠올릴 수 있는 능력을 갖고 싶다.
요즘 그리디 알고리즘, bfs, dfs, 정렬 문제 등 잘하고 싶은 게 너무 많은데 욕심이 많아서인지 한 가지에 집중을 못하는 느낌이다.
그래서 실력이 늘지 않는 것 같다. 물론 그렇다고 안 할 건 아니지만, 걱정이 태산이다.
시간만 축내고 있는 건 아닌가 싶다.