TIL 23-05-18 프로그래머스 - 비밀지도

1. 백준 알고리즘 - 셀프 넘버 

 문제점

https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

 시도해 본 것들

셀프 넘버 만들기 

num_list = [num for num in range(1, 10000)]
for num in range(1, 100):
    print(num + sum([int(n) for n in str(num)]))
    num_list.remove(num + sum([int(n) for n in str(num)]))
print(num_list)

 

num + sum([int(n) for n in str(num)]

num + num의 각 자리 수의 합으로 셀프 넘버 생성 

그리고 이걸 바탕으로 remove로 1~10000까지의 배열에서 삭제 

 

ValueError 해결하기 

num_list = [num for num in range(1, 10000)]
for num in range(1, 10000):
    try:
        num_list.remove(num + sum([int(n) for n in str(num)]))
    except ValueError:
        pass
print(num_list)

이미 list에서 삭제된 값이나 10000을 넘어가는 값을 지우려고 할 때 에러 발생하는 문제

좀 더 깔끔한 방법을 고민하다가 try, except로 예외 처리 

 해결 방법

# 1~10000까지를 원소로 가진 리스트 만들기
num_list = [num for num in range(1, 10001)]
for num in range(1, 10001):
    # 10000을 넘는 경우 or 겹치는 경우를 위해 try, except
    try:
        # num과 num의 각 자리수의 합을 기준으로 remove
        num_list.remove(num + sum([int(n) for n in str(num)]))
    except ValueError:
        pass
    # 리스트 종방향으로 출력
print(*num_list, sep="\n")

10000은 셀프 넘버가 아니므로 없어도 되지만, 코드와 의도를 제대로 맞추기 위해 range(1, 10001)으로 수정 

 알게 된 점

예전에 처음 봤을 때 이걸 어떻게 풀지 생각하며 넘어갔는데, 오늘 풀고나니 그렇게 어려운 방법은 아니었다.

다만 list comprehension같은 방법이 익숙해지면서 예전 방식대로 시도했다면 매우 길어질 코드를 줄여주면서 가독성이 증가한 것 같다. 

 

2.프로그래머스 - 비밀지도 

 문제점

https://school.programmers.co.kr/learn/courses/30/lessons/17681

프로그래머스

 시도해 본 것들

10진수를 2진수로 변환하기

# bin으로 2진수 변환
# [2:]로 접두어 0b제거
# int로 다시 10진수 변환
int(bin(arr1[i])[2:])
int(bin(arr2[i])[2:])

 

 

2진수 값 10진수 기준으로 더하고 0으로 자리수 맞추기 

# f"{2진수 더한 값: 채울 값=0  ,왼쪽 방향=> 0의 ,개수={n}}"
bin_ar = f"{int(bin(arr1[i])[2:]) + int(bin(arr2[i])[2:]):0>{n}}"

f 스트링에서 이렇게 긴 변수를 선언한 적이 없어서 살짝 헷갈렸다.

특히 개수의 경우 {}으로 한 번 더 감싸줘야 제대로 n이라는 변수를 인식했다. 

 

replace()로 변환하기 

bin_ar = bin_ar.replace('0',' ')
bin_ar = bin_ar.replace('1','#')
bin_ar = bin_ar.replace('2','#')

2진수로 변환 후 10진수 상태에서 더했으므로 0,1,2로만 이루어진 숫자가 만들어진다.

그리고 0만 ' ',이고 1과 2는 '#'으로 변환했다. 

 해결 방법

최초 제출

def solution(n, arr1, arr2):
    # 지도는 한 변의 길이가 n인 정사각형
    # 벽은 공백 or #으로 이루어짐
    # 지도1과 2를 겹쳐서 하나라도 벽이면 전체 지도에서 벽
    # arr = 0은 공백, 1은 벽으로 표현된 이진수를 10진수로 변환한 값 

    # 각각의 arr의 원소를 2진수로 변환하기 
    # arr1과 arr2가 아무나 1이라면 1 아니라면 0
    # 채우기
    answer = []
    for i in range(n):
        bin_ar = f"{int(bin(arr1[i])[2:]) + int(bin(arr2[i])[2:]):0>{n}}"
        bin_ar = bin_ar.replace('0',' ')
        bin_ar = bin_ar.replace('1','#')
        bin_ar = bin_ar.replace('2','#')
        answer.append(bin_ar)
    return answer

 

replace()를 한 번에 사용 

def solution(n, arr1, arr2):
    # 지도는 한 변의 길이가 n인 정사각형
    # 벽은 공백 or #으로 이루어짐
    # 지도1과 2를 겹쳐서 하나라도 벽이면 전체 지도에서 벽
    # arr = 0은 공백, 1은 벽으로 표현된 이진수를 10진수로 변환한 값

    # 각각의 arr의 원소를 2진수로 변환하기
    # arr1과 arr2가 아무나 1이라면 1 아니라면 0
    # 채우기
    answer = []
    for i in range(n):
        # arr1과 arr2의 합에 빈공간 0으로 채우기
        bin_ar = f"{int(bin(arr1[i])[2:]) + int(bin(arr2[i])[2:]):0>{n}}"
        # 0이면 공백, 1이나 2면 #으로 변환
        bin_ar = bin_ar.replace("0", " ").replace("1", "#").replace("2", "#")
        answer.append(bin_ar)
    return answer

평균 시간 0.3ms -> 0.5ms로 증가 

 알게 된 점

2중 for문을 사용하지 않아서 나름 만족스럽다. 

replace()를 나눠서 사용하는 것 보다 같이 사용하는 게 메모리 사용량은 더 적을 것 같았고 결과도 일치했지만, 시간 복잡도에서 차이가 없거나 빠를 줄 알았는데 오히려 더 느린 결과를 보여줬다. 아마 오차인 것 같긴 하지만 뭔가 찝찝하다.

다 풀고서 다른 풀이를 구경하다가 zfill이라는 함수의 존재를 다시 알게 됐다. 

print("123".zfill(7)) # 0000123

 

 

https://github.com/sdoram/algorithm_solving_process/tree/main/23-05-18

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

각각의 문제가 내용이 많지 않아서 하나로 올렸는데 기존의 commit log를 보면 너무 가독성이 떨어진다. 

내일부터 하나씩 올려보자