[ SWEA ] D2 - 2001, 1989, 1986, 1984 - python 문제풀이

2001 파리퇴치

퇴치할 파리 정사각형이 어디까지 이동할 수 있을 지 파악해서 갈 수 있는 곳 까지만 for문을 도는게 그나마 시간을 조금이라도 줄이는 방법

for tc in range(int(input())):
    N,M = map(int, input().split())
    fly = [list(map(int, input().split())) for _ in range(N)]
    max_value = 0
    for i in range(N-M+1):
        for j in range(N-M+1):
            row_idx = i
            col_idx = j
            tmp = 0
            for k in range(M):
                tmp += sum(fly[row_idx+k][col_idx:col_idx+M])
            if tmp > max_value:
                max_value = tmp
    print("#{} {}".format(tc+1, max_value))

 

1989 초심자의 회문검사
파이썬 답게 슬라이싱을 써서 간단히 구현할 수도 있고, 내장함수 reverse를 써서도 풀 수 있다. reverse보다 슬라이싱이 훨씬 빠르고 구현하기도 쉽다. 참고로 reverse, reversed 함수는 리스트에 사용할 수 있음

# 방법 1 - 슬라이싱 활용
for tc in range(int(input())):
    s = input()
    result = 0
    if s == s[::-1]:
        result = 1
    print("#{} {}".format(tc+1, result))
    
# 방법 2 - reverse, reversed 활용
for tc in range(int(input())):
    s = list(input())
    result = 0
    if s == list(reversed(s)):
        result = 1
    print("#{} {}".format(tc+1, result))

list_a = [1,2,3,4]

• list_a.reverse() : 원본 배열을 뒤집어버림. 리턴하는 것은 아니기때문에 변수에 담을 필요 없음(list_a = [4,3,2,1])
• reversed(list_a) : 배열을 뒤집어 매핑한 주소값(?)이 리턴됨, 내용을 확인하려면 list로 다시 만들어줘야함
• list(reversed(list_a) : 배열을 뒤집어 리스트로 반환함(list_a = [1,2,3,4] 그대로)

 

1986 지그재그 숫자
문제를 있는 그대로 구현해서 풀이하면 쉽게 풀리기도 하지만, 한번 더 생각해보면 더 쉽고 빠르게 풀 수 있는 방법이O

# 방법 1 - 문제를 있는 그대로 해석해 풀이 - 귀찮아서 lambda로 한번에 풀었음
for tc in range(int(input())):
    print("#{} {}".format(tc+1,sum(list(map(lambda x: x if x % 2 == 1 else -x, list(range(1,int(input())+1)))))))

# 방법 2 - 문제를 잘 읽고 패턴을 찾아 풀이
for tc in range(int(input())):
    N = int(input())
    print("#{} {}".format(tc+1, -1*(N//2)+N if N%2==1 else -1*(N//2)))

1 -2 3 -4 5 -6 ... 이런식으로 간다면

• n이 짝수개라면 : (1-2)+(3-4)+...+((n-1)-n) = -1*(n/2)
• n이 홀수개라면 : (1-2)+(3-4)+...+((n-2)-(n-1))+n = n -1*(n/2)

 

실제로 둘 다 돌려보았을 때는 다음과 같이 큰 차이는 없어 보이지만, 
첫 번째 방법은 O(n), 두 번째 방법(공식으로 풀이)의 시간복잡도는 상수다.

결국 선택의 문제다. 공식으로 풀면 아주 빠르지만, 다른 사람이 한 번에 보고 코드를 이해하기는 어려울 수 있다. 반면 첫 번째 방법처럼 풀면 시간복잡도는 더 높지만, 다른사람도 코드를 보고 어떤 문제를 어떤 식으로 풀이를 했는지 이해하기 쉽다. (다만, 내 코드는 람다식을 써서 너무 길어 가독성은 좀 떨어진다). 주석을 잘 달아놓고 빠르게 풀 수 있는 방법을 쓰는게 좋다고 생각한다. 상수의 시간복잡도... ★

 

1984 중간평균값 구하기

for tc in range(int(input())):
    numbers = list(map(int, input().split()))
    print("#{} {}".format(tc+1, round(((sum(numbers)-max(numbers)-min(numbers))/8))))