Rectangle Partition

https://www.codingame.com/training/easy/rectangle-partition

Practice Loops and Arrays with the exercise "Rectangle Partition"

import sys
import math

w, h, count_x, count_y = [int(i) for i in input().split()]
x = ['']*(count_x)
y = ['']*(count_y)

# x축, y축을 나누는 숫자 입력
tmp = 0
for i in input().split():
    x[tmp] = int(i)
    tmp +=1
tmp = 0
for i in input().split():
    y[tmp] = int(i)
    tmp = tmp+1
    
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
x.sort()
y = list(set(y))
y.sort()

count =0        # 정사각형의 개수 0으로 초기화.

# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)

dpx = [int(0)]*(w+1)
dpy = [int(0)]*(h+1)

for x_s in range(lx):
    for x_inc in range(x_s, lx+1):
        if x_inc==x_s:    # 건너뛰는 간격이 0이면 본인.
            dpx[ x[x_s] ] +=1
        elif x_inc==lx:
            dpx[ w-x[x_s] ] +=1  # 제일 끝으로 가면 전체 길이에서 본인 뺀다.
        else:           # 건너뛰는 간격 크기만큼 간 후 본인과 뺀다.
            dpx[x[x_inc]-x[x_s]] +=1
dpx[w] = 1

for y_s in range(ly):  
    for y_inc in range(y_s, ly+1):
        if y_inc==y_s:
            dpy[ y[y_s] ] +=1
        elif y_inc==ly:
            dpy[ h-y[y_s] ] +=1
        else:
            dpy[ y[y_inc]-y[y_s] ] +=1
dpy[h] = 1 

#print(dpx)
#print(dpy)

for i in range(w+1):
    for j in range(h+1):
        if dpx[i]==0 or dpy[j]==0:
            continue
        if i==j:
            #print(i, j, dpx[i], dpx[j], dpx[i]*dpy[j])
            count += dpx[i]*dpy[j]
            
print(count)

import sys
import math

w, h, count_x, count_y = [int(i) for i in input().split()]
x = ['']*(count_x)
y = ['']*(count_y)

# x축, y축을 나누는 숫자 입력
tmp = 0
for i in input().split():
    x[tmp] = int(i)
    tmp +=1
tmp = 0
for i in input().split():
    y[tmp] = int(i)
    tmp = tmp+1
    
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
x.sort()
y = list(set(y))
y.sort()

count =0        # 정사각형의 개수 0으로 초기화.

x_diff=0
y_diff=0

# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)

for x_s in range(lx+1):
    for y_s in range(ly+1):
        for x_inc in range(lx-x_s+1):
            if x_inc==0 and x_s!=lx:    # 건너뛰는 간격이 0이면 본인.
                x_diff = x[x_s]
            elif x_inc==lx-x_s and x_s==lx:
                x_diff = w
            elif x_inc==lx-x_s:
                x_diff = w-x[x_s]   # 제일 끝으로 가면 전체 길이에서 본인 뺀다.
            else:           # 건너뛰는 간격 크기만큼 간 후 본인과 뺀다.
                x_diff = x[x_s+x_inc]-x[x_s]
                
            for y_inc in range(ly-y_s+1):
                if y_inc==0 and y_s!=ly:
                    y_diff = y[y_s]
                elif y_inc==ly-y_s and y_s==ly:
                    y_diff = h
                elif y_inc==ly-y_s:
                    y_diff = h-y[y_s]
                else:
                    y_diff = y[y_s+y_inc]-y[y_s]
                #print("x_s: "+str(x_s)+" x_inc: "+str(x_inc)+" y_s: "+ str(y_s)+" y_inc: "+str(y_inc))
                #print(str(x_diff)+" "+str(y_diff), end="\n")
                # 두 간격이 같고, 0이 아니면 count 추가.    
                if x_diff==y_diff and x_diff!=0:
                    count = count+1

print(count)

첫 번째 코드는 hi-density는 물론, low-density case를 통과하지 못한다.

두 번째 코드는 hi-density만 통과하지 못한다...

이미 계산한 정보는 저장하래서 저장했는데 뭐가 문제일까?

 

import sys
import math

w, h, count_x, count_y = [int(i) for i in input().split()]
x = ['']*(count_x)
y = ['']*(count_y)

# x축, y축을 나누는 숫자 입력
tmp = 0
for i in input().split():
    x[tmp] = int(i)
    tmp +=1
tmp = 0
for i in input().split():
    y[tmp] = int(i)
    tmp = tmp+1
    
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
x.sort()
y = list(set(y))
y.sort()

count =0        # 정사각형의 개수 0으로 초기화.

x_diff=0
y_diff=0

# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)

dpx = []
dpy = []

for x_s in range(lx):
    for x_inc in range(x_s, lx+1):
        if x_inc==x_s:    # 건너뛰는 간격이 0이면 본인.
            dpx.append(x[x_s])
        elif x_inc==lx:
            dpx.append(w-x[x_s])   # 제일 끝으로 가면 전체 길이에서 본인 뺀다.
        else:           # 건너뛰는 간격 크기만큼 간 후 본인과 뺀다.
            dpx.append(x[x_inc]-x[x_s])
dpx.append(w)

for y_s in range(ly):  
    for y_inc in range(y_s, ly+1):
        if y_inc==y_s:
            dpy.append(y[y_s])
        elif y_inc==ly:
            dpy.append(h-y[y_s])
        else:
            dpy.append(y[y_inc]-y[y_s])
dpy.append(h)    

# dpx와 dpy를 정렬한다.
dpx.sort()
dpy.sort()

for i in range(len(dpx)):
    for j in range(len(dpy)):
        if dpx[i]==dpy[j]:
            count = count+1
            
print(count)

부분 선분의 길이를 인덱스로 하는 배열에 부분 선분이 몇 개 등장하는지 저장하여 나중에 x기준, y기준으로 같은 길이의 선분이 있으면 배열의 값만 곱해서 더해주면 되는 코드이다.

이 코드는 hi-density만 통과하지 못한다.

import sys
import math
 
w, h, count_x, count_y = [int(i) for i in input().split()]
x = []
y = []
 
# x축, y축을 나누는 숫자 입력
for i in input().split():
    x.append(int(i))
for i in input().split():
    y.append(int(i))
 
# x와 y의 부분 선분 리스트에 시작점 0과 끝점 w/h를 추가한다.
x.append(0)
x.append(w)
y.append(0)
y.append(h)
 
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
y = list(set(y))
x.sort()
y.sort()
 
count =0        # 정사각형의 개수 0으로 초기화.
 
# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)
 
dpx = {}
dpy = {}
 
for x_s in range(lx):
    for x_inc in range(x_s+1, lx):
        xkey = x[x_inc]-x[x_s]
            
        if xkey in dpx:
            dpx[xkey] += 1
        else:
            dpx[xkey] =1
 
 
for y_s in range(ly):  
    for y_inc in range(y_s+1, ly):
        ykey = y[y_inc]-y[y_s]
            
        if ykey in dpy:
            dpy[ykey] += 1
        else:
            dpy[ykey] =1
 
for i in dpx.keys():
    for j in dpy.keys():
        if i==j:
            count += dpx[i]*dpy[j]
print(count)

딕셔너리 자료형을 사용해서, 키로 사용할 부분 선분의 길이가 딕셔너리에 존재하면 value를 1 증가, 아니면 딕셔너리에 추가하는 방식을 사용했더니 hi-density를 하나 통과할 수 있었다.

=>

import sys
import math
 
w, h, count_x, count_y = [int(i) for i in input().split()]
 
# x축, y축을 나누는 숫자 입력
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
 
# x와 y의 부분 선분 리스트에 시작점 0과 끝점 w/h를 추가한다.
x.append(0)
x.append(w)
y.append(0)
y.append(h)
 
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
y = list(set(y))
x.sort()
y.sort()
 
count =0        # 정사각형의 개수 0으로 초기화.
 
# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)
 
dpx = {}
dpy = {}
 
for x_s in range(lx-1):
    for x_inc in range(x_s+1, lx):
        xkey = x[x_inc]-x[x_s]
            
        if xkey in dpx:
            dpx[xkey] += 1
        else:
            dpx[xkey] =1
 
 
for y_s in range(ly-1):  
    for y_inc in range(y_s+1, ly):
        ykey = y[y_inc]-y[y_s]
            
        if ykey in dpy:
            dpy[ykey] += 1
        else:
            dpy[ykey] =1
 
for i in dpx.keys():
    if i in dpy:
        count+=dpx[i]*dpy[i]
print(count)

직전의 코드와 다른 점은,

dpx에 존재하는 각각의 키 i가 dpy에 존재하는지 여부만 검사하여 dpx[i]*dpy[i]를 수행했다는 점이다.(line 50~52)

모든 케이스를 통과하였다!