반복문을 줄이는 방법

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/87390

코딩테스트 연습 - n^2 배열 자르기

 

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

 

1) n행 n열 크기의 비어있는 2차원 배열을 만듭니다.

 

2) i = 1,2,3, ... , n에 대해서, 다음 과정을 반복합니다.

 

○ 1행 1열부터 i행 i열까지의 영역 내에서 모든 빈 칸을 숫자 i로 채웁니다.

 

3) 1행, 2행, ... , n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.

 

4) 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], .. , arr[right]만 남기고 나머지는 지웁니다.

 

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return하도록 함수를 완성하세요

 

 

2. 제한사항

 

$1 \leq n \leq 10^{7}$

 

$0 \leq left \leq right < n^2$

 

$right-left < 10^5$

 

3. 입출력 예시

 

그림1. 입출력 예시

 

4. 입출력 설명

 

n=3인 경우 3*3 2차원 배열에 다음과 같이 수를 집어넣고

 

그림2. 입출력 설명1

 

아래 그림과 같이 1차원 배열로 만든 다음에

 

그림3. 입출력 설명2

left index와 right index를 포함하는 부분까지 배열을 잘라온다

 

그림4. 입출력 설명3

 

 

5. 나의 풀이 - 1

 

 

문제에서 말하는대로 모든 원소가 0인 $n \times n$ 배열을 만든다.

 

1행 1열부터 i행 i열까지 i를 집어넣도록 한다

 

two_arr = [n*[0] for _ in range(n)]
    
    for i in range(1,n+1):
        
        for r in range(1,i+1):
            
            for c in range(1,i+1):
                
                if two_arr[r-1][c-1] == 0:

                    two_arr[r-1][c-1] = i
    
    print(two_arr)
    
    [[1, 2, 3], [2, 2, 3], [3, 3, 3]]

 

i가 1부터 n까지 반복문을 돌고... 안으로 들어가서 2차원 배열의 행 r을 1부터 i까지 반복하고... 안으로 들어가서 

 

1부터 i까지 배열의 열을 반복하는데...

 

그러면 i=2인 경우 r=1이면 c=1,2 반복, r=2이면 c=1,2 반복하는 식으로 1행1열부터 2행2열까지 채워넣을거

 

$r \times c$에 0이 들어가있으면 원소가 채워지지 않은 것이므로 i를 채워넣는다.

 

입출력 설명에서 보여준대로 채워넣었는데 이것을 1차원 배열로 만들고 left부터 right까지 slice해서 가져오면 끝

 

arr = sum(two_arr,[])
    
answer = arr[left:right+1]

return answer

 

근데 이제 이렇게 하면 삼중 반복문을 돌면서 시간이 상당히 많이 소요돼서 시간초과로 통과 못함

 

입출력 제한에서 n이 10000000까지 있다는거 보면 분명 이런 부분도 고려해야할거임

 

1번 비밀 케이스가 719.77ms가 걸린단 말이지

 

 

6. 나의 풀이 - 2

 

삼중 반복문을 도는 것이 문제라고 생각해서 반복문을 한번이라도 더 줄인다면 어떨지 생각을 해봤음

 

사실 입출력 설명을 잘 살펴보면 배열 채워 넣는 것에 규칙이 있다는 것을 파악할 수 있었음

 

1행에는 1열까지(0번 index) 1을 넣고 2열부터 2,3,4,...,n까지 넣고

 

2행에는 2열까지(1번 index)까지 2를 넣고 3열부터 3,4,...,n까지 넣고

 

3행에는 3열까지(2번 index)까지 3을 넣고 4열부터 4,5,6,...,n까지 넣고

 

two_arr = [[i for i in range(1,n+1)] for _ in range(n)]

print(two_arr)

[[1,2,3],[1,2,3],[1,2,3]]
    
for i,row in enumerate(two_arr):

    for c in range(i+1):

        row[c] = i+1

print(two_arr)

[[1,2,3],[2,2,3],[3,3,3]]

arr = sum(two_arr,[])

answer = arr[left:right+1]

return answer

 

그래서 1번 풀이에선 모든 원소에 0을 넣은 초기 2차원 배열을 생성했다면

 

일단 모든 열에 1,2,3,4,...,n까지 집어 넣은 배열을 넣고 초기 배열에 규칙에 맞게

 

i=0인 경우 row는 1행일거고 range(1)인 0부터 0까지만 반복을 하면... c=0만 될거고

 

row[0]=1을 집어넣는다

 

i=1인 경우 row는 2행일거고 range(2)인 0부터 1까지만 반복을 하면 c=0,1이 될거고

 

row[0]=2, row[1]=2를 집어넣는다... 이것을 반복하면 원하는 2차원 배열이 생성

 

나머지는 똑같이 1차원 배열을 만들고 left index부터 right index까지 자름

 

그러면 1번 케이스 719.77ms가 67.47ms까지 10배이상 줄어드는거 보면 상당히 빨라진것은 맞지만

 

전체적으로 시간 초과로 통과를 못함

 

 

7. 나의 풀이 - 3

 

단순히 반복문보다 list comprehension이 빠르니까

 

list comprehension을 이용해서 초기 배열을 만들지 말고 그냥 처음부터 규칙에 맞는 2차원 배열을 만들어버릴 생각을 해봤음

 

 

two_arr = [[r if ind < r else i for ind,i in enumerate(range(1,n+1))] for r in range(1,n+1)]

print(two_arr)

[[1, 2, 3], [2, 2, 3], [3, 3, 3]]

arr = sum(two_arr,[])
    
answer = arr[left:right+1]

return answer

 

r을 1부터 n까지 반복한다는 것은 n개의 행을 만드는건데..

 

각 행에서 규칙에 맞게 ind<r이면 r을 집어넣고 아니면 i를 집어넣도록 함

 

예를 들어 r=1이면 ind=0인 경우 i=1이지만 r=1을 넣고 ind=1부터는 i=2를 넣음.. 그래서 1행은 [1,2,3]

 

r=2이면 ind=0인 경우 i=1이지만 r=2를 넣고 ind=1인 경우 i=2이지만 r=2를 넣고 ind=2부터는 i=3을 넣음

 

그래서 2행은 [2,2,3]... 이것을 반복

 

1번 비밀케이스가 66.65ms로 2번 풀이에 비해 아주 약간 빨라짐

 

 

8. 나의 풀이 - 4

 

그러면 2차원 배열을 만들고 1차원 배열로 만든다음에 left부터 right까지 slice를 해야할까???

 

규칙이 뻔히 있는데 그냥 1차원 배열부터 만들면 어떨까??

 

#two_arr = [[r if ind < r else i for ind,i in enumerate(range(1,n+1))] for r in range(1,n+1)]

#print(two_arr)

#[[1,2,3],[2,2,3],[3,3,3]]

arr = [r if ind < r else i for ind,i in enumerate(range(1,n+1)) for r in range(1,n+1)]

print(arr)

[1,2,3,2,2,3,3,3,3]

answer = arr[left:right+1]

return answer

 

앞에서 이용한 list comprehension

 

two_arr = [[r if ind < r else i for ind,i in enumerate(range(1,n+1))] for r in range(1,n+1)]에서 사실

 

for r in range(1,n+1) 앞에 리스트를 빼버리면 처음부터 1차원 배열이 생성이 된다

 

이렇게 하면 1번 비밀 케이스가 66.65ms에서 4.44ms로 10배이상 빨라지지만 여전히 다른 케이스에선 시간 초과가 남

 

 

9. 나의 풀이 - 5

 

1차원 배열을 만들고 left부터 right까지 slice를 했는데 규칙을 아니까 그냥 left부터 right까지만 채워넣겠다는 방법을 생각해봄

 

1차원 배열에 원소가 채워넣어지는 것을 생각을 해보면

 

n=3일 때 먼저 본다면..

 

arr = [r if ind < r else i for ind,i in enumerate(range(1,n+1)) for r in range(1,n+1)]

 

r=1일 때 1행에 1,2,3 3개... 이 때 r=1이고 n=3이고 i=1,2,3이므로 각 원소 1,2,3의 index는 n*(r-1)+(i-1)이라는 특징이 있음

 

r=2일 때 2행에 2,2,3으로 3개

 

이걸 연결해서 생각해보면 1,2,3,2,2,3으로 총 6개.. 역시 n=3, r=2, i=1,2,3이므로 1,2,3 다음인 2,2,3은 n*(r-1)+(i-1)이라는 특징을 가짐

 

마찬가지로 r=3일 때 3행에 3,3,3이 넣어져서 1,2,3,2,2,3,3,3,3으로 총 9개이고 n=3, r=3, i=1,2,3에서 2,2,3 다음도 n*(r-1)+(i-1)이라는 index를 가짐

 

그래서 일반적으로 1차원 배열에 채워넣어지는 원소는 n*(r-1)+(i-1)이라는 index를 가진다는 것을 알 수 있었음

 

arr = []
    
for r in range(1,n+1):

    for i in range(1,n+1):

        if n*(r-1)+(i-1) >= left and n*(r-1)+(i-1) <= right:

            if i-1 < r:

                arr.append(r)

            else:

                arr.append(i)

return arr

 

그래서 n*(r-1)+(i-1)이 left이상 right이하 일 때만 원소를 채워넣겠다는 전략으로 1차원 배열을 생성함

 

list comprehension으로 만들어지지가 않아서(만들수 있는지 모르겠음)

 

이중 반복문으로 분리해서 만들었음

 

그래서인지, 조건문 검사하는 시간이 걸려서인지.. 1번 비밀케이스가 4.44ms에서 20.29ms로 5배 증가함

 

 

10. 나의 풀이 - 6

 

그러면 이번엔 for문을 쓰는것 자체에서 시간이 많이 걸린다고 생각을 했음

 

for문을 안쓰고... 단 1번의 반복문만 사용할 수는 없을까?

 

r과 i를 증가시키기만 하면 되니까

 

while 반복문 내에서 r과 i를 증가시키면서 채워 넣는 전략을 구상함

 

arr = []
    
r = 1

i = 0

while n*(r-1)+(i-1) < right:

    i += 1

    if i == n+1:

        r += 1

        i = 1

    if n*(r-1)+(i-1) >= left:

        if i-1 < r:

            arr.append(r)

        else:

            arr.append(i)

return arr

 

앞에서도 r=1, i=1부터 시작을 했으니까 초기 r=1, i=0으로 시작을 한 다음

 

while 반복문에 들어가면 i에 1을 더해서 r=1, i=1부터 시작하도록 함

 

현재 index가 n*(r-1)+(i-1)이니까 이게 left이상이면 arr에 원소를 채워 넣을거임

 

원소 채워 넣는 규칙은 i-1이 r보다 작으면 r을 넣고 아니면 i를 넣는다는 것은 앞에서 했음

 

한번의 반복문이 돌면 i에 1을 더할거임

 

그러면 right index까지 채워 넣어야 하니까 n*(r-1)+(i-1) < right라는 조건이 참이 될때까지 반복문이 돌거임

 

n*(r-1)+(i-1) <= right 이렇게 쓰면 안되는 이유가 코드 구현상 i+=1을 한 순간부터 반복문이 시작이니까

 

r을 어떻게 처리해야할까? 고민을 했는데 생각보다 간단했음

 

i가 n+1이 되면 r에 1을 더하고 i를 1로 만들면 되는 거였음

 

이렇게 하면 1번의 반복문으로 할 수 있지 않을까?? 분명 빠를거라고 확신했음

 

하지만 20.29ms에서 34.61ms로 시간이 조금 더 증가했다

 

 

11. 나의 풀이 - 7

 

왜 시간이 증가했을까?? n*(r-1)+(i-1)이 right보다 크면 반복문을 탈출해서 사실 상관없지만

 

index n*(r-1)+(i-1)이 left이상인지 아닌지 검사하는데 시간이 소요가 될거라고 생각을 했음

 

right 뒤쪽이 상당히 짧은 대신에 left까지 상당히 길어서 상당한 시간이 소요될 수가 있단 말이지

 

어떻게 하면 바로 left부터 집어넣기 시작할 수 있을까??

 

갑자기 미친 아이디어가 떠올랐음

 

n*(r-1)+(i-1)>=left를 자세히 보면 n*(r-1)+(i-1)=left라는 식은 left를 n으로 나누면 몫이 r-1이고 나머지가 i-1이다

 

그러면 이 사실을 이용해서 left를 n으로 나눠서 몫과 나머지를 구하면 어디서부터 시작해야하는지 바로 알수가 있는거임

 

def solution(n, left, right): 
    
    arr = []
    
    r,i = divmod(left,n)
    
    r = r+1
    
    i = i
    
    while n*(r-1)+(i-1) < right:
        
        i += 1
        
        if i == n+1:
            
            r += 1
            
            i = 1
            
        if i-1 < r:

            arr.append(r)

        else:

            arr.append(i)
    
    return arr

 

그래서 divmod를 이용해서 divmod(left,n)을 해서 몫과 나머지 r과 i를 구함

 

n*(r-1)+(i-1) = left로 나오니까 사실 몫은 r-1이고 나머지는 i-1이란 말이지

 

예를 들어 left=2, n=3인 경우 r=0, i=2가 나온다.

 

그러면 r=1, i=3부터 시작을 해야 n*(r-1)+(i-1) >= left을 만족한단 말이야

 

반복문의 시작은 위에서도 봤지만 r=1, i=1부터 시작해야함

 

그래서 초기에 r에는 1을 더한 r = r+1로 초기화 하고 i는 i 그대로 초기화.

 

왜냐하면 while 반복문 안에서 1을 더하면서 시작할거니까

 

이렇게 하면 left부터 right까지 원소를 바로 채워넣을 수 있다

 

이제는 모든 테스트 케이스를 통과할 수 있다

 

 

12. 다른 풀이

 

결국에 이 문제 핵심은

 

1) 규칙을 파악해서 left부터 right까지 바로 채워넣는다

 

2) n*(r-1)+(i-1) = left라는 식을 이용해서 left를 n으로 나눈 몫과 나머지를 이용하면 어디서부터 시작해야하는지 바로 알 수 있다

 

3) r행에서는 r열까지는 r을 집어넣고 r+1열부터는 r+1,r+2,...를 집어넣는다

 

def solution(n, left, right):
    
    answer = []
    
    for i in range(left,right+1):
        
        answer.append(max(i//n,i%n)+1)
    
    return answer

 

위 3가지를 가장 간결하게 구현함

 

left부터 right까지 집어넣을거니까 이 부분만 반복을 할거고

 

left를 n으로 나눈 몫과 나머지로부터 i-1 < r이면 r을 넣고 i >= r이면 i를 넣는다를 max(i//n,i%n)+1로 표현했네

 

 

13. 되돌아보기

 

혼자 힘으로 생각을 하면서 효율성을 개선해가지고 모든 케이스를 통과한거 잘했다

 

굳이 2차원 배열 >> 1차원 배열 >> slice를 따라야하는가?

 

규칙이 있으면 규칙을 써서 어떻게든 간결하게 정답까지 도달하는게 좋은 방법

 

list comprehension 잘 이용했고

 

for문 2번 쓸거를 while문 1번 써서 안에서 1씩 더해가면서 한것도 꽤 좋았다