[멀티잇 코딩테스트 러닝클래스] 0커플, 폭탄 구현하기 - 파이썬(Python)

0커플

 

 

 

 

 

문제는 장황하지만 도출 과정은 꽤 간단한 문제입니다. 서로 커플인 숫자는 절댓값이 같으며 하나는 양수, 다른 하나는 음수입니다. 그 말은 커플인 숫자끼리 더하면 0이 된다는 뜻입니다. 따라서 입력에서 두 번째 줄에 주어진 수들을 모두 더하면 결국 커플이 아닌 수끼리의 합만 남게 됩니다. 

 

따라서 이 문제의 해답은 주어진 모든 숫자들을 더하는 것입니다.

 

 

import sys
input = sys.stdin.readline
N = int(input())
people = list(map(int,input().split()))
print(sum(people))

 

 

하지만 이 문제에서 배울 수 있는 개념인 Hash를 통해서도 풀어보겠습니다. Hash는 Key와 Value로 이루어진 자료구조로, Hash에서 Key의 존재 유무를 검색하는 속도는 O(1)이면 충분합니다. 파이썬에서는 dict()를 이용해보겠습니다.

 

 

import sys
input = sys.stdin.readline

N = int(input())
people = list(map(int,input().split()))

sum = 0
occur = dict()

# Hash에 people[i]가 Key로 존재하는지 확인
for i in range(N) :
	occur[people[i]] = 1

# -people[j]가 Hash에 존재하지 않는다면 peope[j]를 sum에 더함
for j in range(N) :
	if -people[j] not in occur :
    	sum += people[j]

print(sum)

 

---

 

폭탄 구현하기

 

 

 

 

배열을 탐색하는 것이 정석이지만, 우선 조금 더 편한 방법으로 풀어보겠습니다. 폭탄 피해를 입은 구역에 적혀있는 숫자들의 합을 구하는 문제인데요. 굳이 배열을 탐색할 필요없이 가능한 숫자들의 합을 생각해보면 됩니다.

 

폭탄이 떨어진 곳을 기준으로 배열의 상하좌우 탐색이 모두 가능하다면 피해 구역은 총 5개입니다. 하지만 y나 x가 len 혹은 1과 같다면 피해 구역은 줄어들죠. 예를 들어, x==0 and y==0이라면 피해 구역은 3개, x==len and 0<y<len이라면 피해 구역은 4개가 됩니다. 

 

따라서 반복할 때마다 5에서 피해 구역이 줄어들 수 있는 모든 경우를 뺀 값(5,4,3 중 하나)을 sum에 계속 더해주면 되겠습니다.

 

 

import sys
input = sys.stdin.readline

len, cnt = map(int,input().split())
sum = 0

for i in range(cnt) :
	y, x = map(int,input().split())
	sum += 5 - (x==len) - (y==len) - (x==1) - (y==1)
	
print(sum)

 

 

이제 기초 배열 탐색인 dx와 dy를 이용해서 해결해보겠습니다.

 

우선 N*N 크기의 2차원 배열 matrix와 dx, dy 좌표 배열(상-하-좌-우 순서)을 선언했습니다.

 

이후 반복문을 통해 input을 읽어들여 x, y에 각각 저장하고 폭탄이 떨어진 위치에 +1, 떨어진 위치 기준 상하좌우 인덱스에 +1합니다. 단, 상하좌우 좌표인 matrix[nx][ny]가 정해진 범위를 벗어난다면 +1하지 않습니다.

 

 

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
# 2차원 배열 생성
matrix = [[0 for _ in range(N)] for _ in range(N)]
sum = 0

# dx, dy 좌표 설정 : 상하좌우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

for i in range(K) :
	x,y = map(int,input().split())
    	# 폭탄이 떨어진 위치에 +1
	matrix[x-1][y-1] += 1
	for j in range(4) :
    	# matrix[nx][ny] : 폭탄이 떨어진 위치 기준 상하좌우 좌표
		nx = x-1 + dx[j]
		ny = y-1 + dy[j]
        # nx와 ny가 모두 matrix의 인덱스 범위를 벗어나지 않아야 함
		if 0<=nx<N and 0<=ny<N : matrix[nx][ny] += 1

for i in range(N) :
	for j in range(N) : sum += matrix[i][j]

print(sum)