SW coding test (1)

오늘은 SW Expert Academy 에 나온 몇 가지 문제 풀이에 대해 리뷰해보도록 하겠다.

Contents

1. 문자열의 거울상
2. 파리 퇴치

---

1. 문자열의 거울상

<문제>
'b’, ‘d’, ‘p’, ‘q’로 이루어진 문자열이 주어진다. 이 문자열을 거울에 비추면 어떤 문자열이 되는지 구하는 프로그램을 작성하라! 예를 들어, “bdppq”를 거울에 비추면 “pqqbd”처럼 나타날 것이다.

<나의 풀이>

t = int(input())

for tc in range(1, t+1):
    text = input()
    mirror = {"b": "d", "d": "b", "p": "q", "q": "p"}
    result = "".join(mirror.get(char) for char in reversed(text))

    print(f"#{tc} {result}")

위의 문제를 해결하기 위해 나는 dictionary 를 이용하였다. 거울에 비춘 알파벳들이 b ⇆ d 그리고 p ⇆ q 의 관계를 갖기 때문에 이를 mirror 라는 dictionary 에 넣어준다. 그리고 input 으로 받은 text 를 for 문을 통해 거꾸로 스캔하며 해당 key 에 대한 value 를 새로운 string 인 result 에 join 한다.

따라서, 여기서 짚고 넘어가고 싶은 function 두 가지는 다음과 같다.

1. reversed(sequence)
   Returns a reversed iterator object.

2. dictionary.get(key, default = None)
   Returns the value of the item with the specified key or the default value.

<결과>

(input) 	2
			bdppq
        	qqqqpppbbd

(output)	#1 pqqbd
			#2 bddqqqpppp

<참고>
mirror 라는 dictionary 를 만들기 위한 더욱 간단한 방법을 발견했다. 바로 dict() 와 zip() 을 이용하는 것이다.

mirror = dict(zip(['b', 'd', 'p', 'q'], ['d', 'b', 'q', 'p']))

---

2. 파리 퇴치

<문제>
간단히 요약하자면 N x N 의 배열 안에 해당 숫자만큼의 파리가 존재할 때, M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다. 죽은 파리의 개수를 구하라!

<제약 사항>
5 ≤ N ≤ 15 and 2 ≤ M ≤ N

<나의 풀이>

t = int(input())
 
for test_case in range(1, t + 1):
    N, M = map(int, input().split())
    max_fly_count = 0
 
    grid = [list(map(int, input().split())) for i in range(N)]
 
    for i in range(N - M + 1):
        for j in range(N - M + 1):
            box = [grid[row][j:j + M] for row in range(i, i + M)]
            fly_count = sum(sum(row) for row in box)
            max_fly_count = max(max_fly_count, fly_count)
 
    print(f"#{test_case} {max_fly_count}")

이 풀이에서 주요했던 것은 N - M + 1 의 범위 설정과 box 를 만들 때 list comprehension 에 들어가있는 for 문이다. 우선, N 과 M 의 범위를 참고하자면 N = M 일 수도 있기 때문에 파리채의 크기 설정 시 range 가 0 이 되는 것을 막기 위해 N - M + 1 을 해주었다. 그리고 box 를 만들기 위해 grid 의 row 와 column 을 설정해 주는데 trial and error 을 겪었다. 다음과 같이 5 x 5 크기의 grid 에 파리들이 있다고 하자.

2 x 2 의 파리채를 사용한다면 우리는 빨간 상자로 표시된 사각형에 들은 숫자의 합이 최대인 곳을 찾아야한다.

box = grid[i:i + M][j:j + M]

따라서 나는 위처럼 설정해주면 길이가 M 인 row 와 column 을 동시에 출력할 줄 알았으나 컴퓨터는 grid[i:i + M] 을 먼저 slicing 한 후 그 중 [j:j + M] 을 실행하여 문제를 일으켰다.

(wrong output) 	[[1, 3, 3, 6, 7], [8, 13, 9, 12, 8]]
				[[8, 13, 9, 12, 8]]
				[]
				[]
				[[8, 13, 9, 12, 8], [4, 16, 11, 12, 6]]
				[[4, 16, 11, 12, 6]]
				[]
				[]
				[[4, 16, 11, 12, 6], [2, 4, 1, 23, 2]]
				[[2, 4, 1, 23, 2]]
				[]
				[]
				[[2, 4, 1, 23, 2], [9, 13, 4, 7, 3]]
				[[9, 13, 4, 7, 3]]
				[]
				[]
				#1 99

In Python, when you use grid[i:i+M][j:j+M], it creates a new list by slicing grid along the first dimension (i:i+M) and then further slices the result along the second dimension (j:j+M).
However, this might not give you the desired 2x2 subarray. To get the correct 2x2 subarray from a 2D list, you should use nested list comprehension. This way, you explicitly loop through the rows and take the appropriate columns for each row, ensuring you get a proper 2x2 subarray.

그 이유를 알고보니 python 이 앞서 제기한 방법처럼 작동하기 때문이었다. 따라서 nested for loop 를 써주었더니 원하는대로 잘 작동하였다.

(correct output)	[[1, 3], [8, 13]]
					[[3, 3], [13, 9]]
					[[3, 6], [9, 12]]
					[[6, 7], [12, 8]]
					[[8, 13], [4, 16]]
					[[13, 9], [16, 11]]
					[[9, 12], [11, 12]]
					[[12, 8], [12, 6]]
					[[4, 16], [2, 4]]
					[[16, 11], [4, 1]]
					[[11, 12], [1, 23]]
					[[12, 6], [23, 2]]
					[[2, 4], [9, 13]]
					[[4, 1], [13, 4]]
					[[1, 23], [4, 7]]
					[[23, 2], [7, 3]]
					#1 49

---