TIL 23-04-28 페어 프로그래밍 - 특별한 이차원 배열2

https://github.com/sdoram/Algorithm

https://github.com/sdoram/algorithm_solving_process

GitHub - sdoram/algorithm_solving_process: 알고리즘 풀이 과정 python 파일

 

1.페어 프로그래밍 - 특별한 이차원 배열2

 문제점

문제 설명
n × n 크기의 이차원 배열 arr이 매개변수로 주어질 때, 
arr이 다음을 만족하면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

0 ≤ i, j < n인 정수 i, j에 대하여 arr[i][j] = arr[j][i]
제한사항
1 ≤ arr의 길이 = arr의 원소의 길이 ≤ 100
1 ≤ arr의 원소의 원소 ≤ 1,000
모든 arr의 원소의 길이는 같습니다.

# 입출력 예
i	j   arr[i][j] arr[j][i]
0	0	5	5
0	1	192	192
0	2	33	33
1	0	192	192
1	1	72	72
1	2	95	95
2	0	33	33
2	1	95	95
2	2	999	999

# n*n크기의 이차원 배열 arr
 # return은 arr[i][j] = arr[j][i] 이면 1 아니면 0 return
 # for문, 조건문을 통해서 i와 j 비교

시도해 본 것들

2중 for문을 활용한 방법 시도

def solution(arr):
    for i in range(len(arr)):
            for j in range(len(arr)):
                if arr[i][j] != arr[j][i]:
                    return 0
    return 1

네비게이터와 드라이버 모두 어제 풀어본 경험을 살리면서 문제를 푼 결과 어렵지 않게 풀 수 있었다.

 

1과 0을 모두 포함하는 조건문 만들어보기

def solution(arr):
    for i in range(len(arr)):
            for j in range(len(arr)):
                if arr[i][j] == arr[j][i]:
                    answer = 1
                else:
                    answer = 0
                    break
            break
        return answer

if문에서 1과 0을 모두 포함하는 방법으로 return이 하나만 있는 코드가 만들어졌다.

코드의 길이나 효율성이 좋다고 하기엔 힘들지만 2중 for문을 break를 두번 사용해서 탈출하는 방법을 처음 사용해보는 등 평소에 생각하지 않았던 방법들을 확인할 수 있었다.

 

삼항 연산자를 통한 if문 줄이기 시도 실패

def solution(arr):
    for i in range(len(arr)):
            for j in range(len(arr)):
                answer = 1 if arr[i][j] == arr[j][i] else 0 ,break
            break
        return answer

이런 형태로 여러번 시도했지만, 문법 오류만 계속해서 만났다. if문의 한쪽에서는 1만 받고 else에서 break를 줄 수 있는 방법이 있는지 모르겠다.

 

다른 팀원들과의 코드 리뷰

for문의 범위 설정 개선

i	j	arr[i][j]	arr[j][i]
0	0	5	5
1	1	72	72
2	2	999	999

코드리뷰를 하는 과정에서 한 팀원이 arr[0][0], arr[1[1]과 같은 값들은 비교할 필요가 없음을 제시

 

i	j	arr[i][j]	arr[j][i]
0	1	192	192 <- 여기서 검증
1	0	192	192 <- 필요 없음

그리고 이어서 여기서 arr[0][1]에서 이미 검증을 했기 때문에 arr[1][0]의 검증을 수행하지 않아도 되는 사실까지 알 수 있었다.

for i in range(len(arr)):
	print(i)
        for j in range(i+1,len(arr)):
        print(i,j)
            if arr[i][j] != arr[j][i]:
                return 0
    return 1
    
0
0 1
0 2
1
1 2
2

print()문을 통해서 for문의 범위를 확인하던 중 생각했던 범위 발견

 

def solution(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i][j] != arr[j][i]:
                return 0
    return 1
print(solution([[0]*1000 for _ in range(1000)]))
# 0.1383202075958252초


def solution(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i][j] != arr[j][i]:
                return 0
    return 1
print(solution([[0]*1000 for _ in range(1000)]))
# 0.23602867126464844초

 실제로 코드 실행시간을 최대치인 1000*1000의 이차원 배열을 기준으로 했을 때 실행 속도가 절반정도 빨라졌다.

다만 주어진 값이 작은 경우에는 for문의 range설정이 시간이 더 걸리는 경우도 있는 것 같았다.

그래도 주어진 값이 커질 수록 개선된 코드가 더 빠르다.

 해결 방법

def solution(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i][j] != arr[j][i]:
                return 0
    return 1

 알게 된 점

알고리즘을 풀면서 굉장히 어렵게 느껴졌던 조건의 변경을 통한 시간 복잡도 개선을 처음부터 같이 해결한 경험을 한 것이 의미가 크다.

이차원 배열은 그 특성상 기본적으로 2중 for문을 사용이 기본이 되는 것 같다. 생성의 경우 List Comprehension을 통해서 개선할 수 있지만, 그 배열을 풀어서 확인해야 하는 경우는 2중 for문을 사용해도 괜찮은 것 같다. 

 

2. 백준 알고리즘 - 뒤집기

 문제점

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 
다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다.
다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다.
뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 
한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

# 0으로 뒤집은 것과 1로 뒤집은 것중에 작은 수 출력

 시도해 본 것들

spit()으로 구분해보기 

bin_str = '0001100'
bin_str_list = bin_str.split('0') #['', '', '', '11', '', '']
bin_str_list1 = bin_str.split('1') #['000', '', '00']

0과 1로 split()했을 때 차이가 존재하고 for문을 사용해 공백을 제거한 뒤의 리스트의 길이를 측정하면 풀이가 가능할 것으로 보이나, 공부하는 입장에서 리스트의 원소가 눈에 잘 들어오지 않아서 패스

 

for문과 조건문을 사용해서 나누기

bin_str = '0001100'
str_list = []
num_list = []
for num in range(len(bin_str)):
    if num != 0 and bin_str[num-1] != bin_str[num]:
        str_list.append(num_list)
        num_list = []
    if num == len(bin_str)-1 and bin_str[num]:
        str_list.append(num_list)
    num_list.append(bin_str[num])

print(str_list)[['0', '0', '0'], ['1', '1'], ['0', '0']]

 

num_list.append(bin_str[num])

이 코드로 num_list에 숫자를 넣고 

 

if num != 0 and bin_str[num-1] != bin_str[num]:
        str_list.append(num_list)
        num_list = []

이 조건문을 통해서 글자가 달라지는 순간을 찾고 만들어진 list를 추가하고 다시 초기화하는 로직

 

if num == len(bin_str)-1 and bin_str[num]:
        str_list.append(num_list)

이 코드로 마지막 리스트까지 추가해서 리스트 완성

리스트를 만들었지만, 0과 1이 모두 함께 있는 이차원 배열이 만들어졌다. 이걸 활용하는 것 보다 리스트 자체를 두개로 구분하는 게 더 이해하기 쉬울 것 같다.

 

zero_str_list = []
one_str_list = []

0과 1의 리스트를 따로 선언

 

if num != 0 and bin_str[num-1] != bin_str[num] and bin_str[num-1] == '0':
        zero_str_list.append(num_list)
        num_list = []
    elif num != 0 and bin_str[num-1] != bin_str[num] and bin_str[num-1] == '1':
        one_str_list.append(num_list)
        num_list = []

if문 조건에서 글자가 바뀌는 순간 0과 1을 구분해서 추가하기 

 

if num == len(bin_str)-1 and bin_str[num] == '0':
        zero_str_list.append(num_list)
elif num == len(bin_str)-1 and bin_str[num] == '1':
	one_str_list.append(num_list)

 마지막 리스트를 0과 1을 구분해서 추가하기

 

print(one_str_list) # [['1', '1']]
print(zero_str_list) # [['0', '0', '0'], ['0', '0']]

리스트 결과물 확인 무사히 1과 0으로 구분된 이차원 배열이 만들어졌다.

 

print(len(one_str_list) if len(one_str_list) <
      len(zero_str_list) else len(zero_str_list))

마지막으로 if문을 통해서 리스트의 길이가 짧은 쪽을 출력하는 조건 설정 

 

참고 코드

def solution(n):
    answer = []
    for i in range(n):
        ainner = []
        for j in range(n): 
            if i == j:
                ainner.append(1)
            else:
                ainner.append(0)
        answer.append(ainner)
    return answer

어제 2차원 배열을 풀어보고 코드리뷰하는 과정에서 다른 팀원의 코드가 위에서부터 읽었을 때 가독성이 좋아 기억에 남은 코드를 참고했다.

다만 조건문이 길어지고 많아지다 보니 참고 코드만큼 보기 쉬운 코드가 나오지는 않았다.

 

처음에 포기한 split() 사용하기

bin_str = '0001100'
zero_bin_str_list = bin_str.split('0')  # ['', '', '', '11', '', '']
one_bin_str_list1 = bin_str.split('1')  # ['000', '', '00']
reverse_one = 0
reverse_zero = 0

for s in zero_bin_str_list:
    if s != '':
        reverse_one += 1
        
for s in one_bin_str_list1:
    if s != '':
        reverse_zero += 1

print(reverse_one) # 1
print(reverse_zero) # 2
print(reverse_zero if reverse_zero <= reverse_one else reverse_one) #1

for문을 사용해서 공백이 아닌 경우만 카운트 하면 그게 뒤집어야 하는 숫자가 된다.

 해결 방법

bin_str = input()
zero_str_list = []
one_str_list = []
num_list = []
for num in range(len(bin_str)):
    if num != 0 and bin_str[num-1] != bin_str[num] and bin_str[num-1] == '0':
        zero_str_list.append(num_list)
        num_list = []
    elif num != 0 and bin_str[num-1] != bin_str[num] and bin_str[num-1] == '1':
        one_str_list.append(num_list)
        num_list = []
    if num == len(bin_str)-1 and bin_str[num] == '0':
        zero_str_list.append(num_list)
    elif num == len(bin_str)-1 and bin_str[num] == '1':
        one_str_list.append(num_list)
    num_list.append(bin_str[num])

print(len(one_str_list) if len(one_str_list) <
      len(zero_str_list) else len(zero_str_list))

print로 확인하는 결과는 알기 쉬워졌는데 코드의 가독성은 굉장히 떨어진 것 같다.

 

bin_str = input()
zero_bin_str_list = bin_str.split('0')
one_bin_str_list1 = bin_str.split('1')
reverse_one = 0
reverse_zero = 0

for s in zero_bin_str_list:
    if s != '':
        reverse_one += 1

for s in one_bin_str_list1:
    if s != '':
        reverse_zero += 1
print(reverse_zero if reverse_zero <= reverse_one else reverse_one)

문제 자체를 파악하고 난 뒤는 이 코드가 더 이해하기 쉬운 것 같다.

 알게 된 점

한 번 풀었다고 바로 끝나는 게 아니라 다른 방법으로 풀어보면 이해가 잘 가지 않는 코드도 내가 아는 다른 코드만큼 이해할 수 있는 지름길 같다.

이차원 배열과 관련된 문제가 보이면 일단 피하고 싶은 경향이 있었는데 조금 복잡하지만 정확히 원하는 대로 원소와 배열을 조작해서 다음에도 이차원 배열을 사용할 수 있을 것 같다.