[SWEA|파이썬] 1493. 수의 새로운 연산 (D3)

문제

https://tinyurl.com/2j73qsyu

SW Expert Academy

 

 

🐍파이썬

def numToXy(num):	#숫자->좌표 변환 함수
    p_cnt = 0	
    xyArr = [0, 0]
    total_p = 0		
    num2 = num
    while True:
        p_cnt += 1
        total_p += p_cnt
        num2 -= p_cnt	
        if num2 <= 0:
            xyArr[0] = p_cnt-(total_p-num)
            xyArr[1] = 1+(total_p-num)
            break
    return xyArr
def xyToNum(x, y):	#좌표->숫자 변환 함수
    group = (x+y)-1
    total = 0
    for i in range(1, group+1):
        total += i
    return total - (y-1)
T = int(input())
for test_case in range(1, T+1):
    p, q = map(int, input().split())
    a = numToXy(p)
    b = numToXy(q)
    x = a[0] + b[0]
    y = a[1] + b[1]
    print("#{} {}".format(test_case, xyToNum(x, y)))

💡 규칙

num	(x, y)
1	(1,1)
2	(1,2)
3	(2,1)
4	(1,3)
5	(2,2)
6	(3,1)
7	(1,4)
8	(2,3)
9	(3,2)
10	(4,1)

숫자와 좌표간의 상관관계는 위의 표와 같다.

색깔로 구분한 숫자들을 하나의 그룹이라고 표현할 때 각 그룹에 속한 숫자의 갯수 i는 1, 2, 3, 4개로 순차적으로 늘어남을 알 수 있다.

또한 각 그룹의 x좌표는 1에서 시작해 i까지 증가하고 y좌표는 i에서 시작해 1씩 감소하는 양상을 보인다.

이를 이용해 두 개의 함수를 만들었다.

 

def numToXy(num) 👉숫자->좌표 변환 함수

def numToXy(num):	#숫자->좌표 변환 함수
    p_cnt = 0	
    xyArr = [0, 0]
    total_p = 0		
    num2 = num
    while True:
        p_cnt += 1
        total_p += p_cnt
        num2 -= p_cnt	
        if num2 <= 0:
            xyArr[0] = p_cnt-(total_p-num)
            xyArr[1] = 1+(total_p-num)
            break
    return xyArr

p_cnt 그룹을 확인할 변수, 그룹을 늘려나가며 해당 수가 어떤 그룹에 속하는지 확인

xyArr x, y좌표를 담을 배열

total_p 1부터 p_cnt까지의 총합을 저장할 변수. 만약 p_cnt가 4라면 total_p는 1+2+3+4=10이고, 이는 그룹4의 마지막 수이다.

 

p_cnt 값을 늘려나가며 num2에서 p_cnt를 빼준다.

num2의 값이 음수거나 0이라면 해당 p_cnt가 num의 그룹이 된다.

만약 num의 값이 5였다면
num2 - 1 - 2 - 3일때 num2의 값이 음수가 된다.
따라서 5의 그룹은 3 (p_cnt = 3) 이다.

i = 그룹값일 때, 

각 그룹의 x좌표는 1에서 시작해 i까지 증가하고 y좌표는 i에서 시작해 1씩 감소하므로 해당 원리를 이용해 x, y 좌표를 구한다.

xyArr[0] = p_cnt-(total_p-num)	#x좌표
xyArr[1] = 1+(total_p-num)	#y좌표

x좌표는 i에서 그룹 내 가장 큰 숫자와 구하고자 하는 숫자의 차이를 빼서 구할 수 있다.

예를 들어 9의 x좌표를 구하고 싶다면 먼저 9의 그룹을 구한다.(=4)

이후 해당 그룹의 최댓값(1+2+3+4=10)에서 num 값(=9)을 뺀 결과(=1)를 그룹값에서 빼주면 x좌표가 된다.

y좌표는 1에 그룹 내 가장 큰 숫자와 구하고자 하는 숫자의 차이를 더해서 구할 수 있다.

9의 y좌표를 구하려면 y값이 시작되는 1에 해당 그룹의 최댓값(1+2+3+4=10)에서 9를 뺀 값(=1)을 더해주면 된다.

 

 

def xyToNum(x, y) 👉 좌표->숫자 변환 함수

def xyToNum(x, y):	#좌표->숫자 변환 함수
    group = (x+y)-1
    total = 0
    for i in range(1, group+1):
        total += i
    return total - (y-1)

 

num	(x, y)
1	(1,1)
2	(1,2)
3	(2,1)
4	(1,3)
5	(2,2)
6	(3,1)
7	(1,4)
8	(2,3)
9	(3,2)
10	(4,1)

위 표에서 보면 각 그룹은 (두 좌표의 합-1)의 값과 같다.

이를 이용해 좌표가 속한 값을 구하고 y의 좌표 값이 1부터 커지는 원리를 이용해 그룹의 최댓값을 구한다.

y좌표는 그룹의 최댓값에서부터 1씩 감소하는 특징이 있기 때문에 최댓값과 현재 좌표를 이용하면 num을 구할 수 있다.

위의 표에서 규칙을 찾은 결과, 최댓값-(y-1)을 해주면 현재 좌표가 가리키는 num값을 찾을 수 있다.

 

만약 (x, y) = (2,3)이라면

2(=x)+3(=y)-1 = 4이므로 해당 좌표의 그룹값은 4이다. 

해당 그룹의 최댓값은 1+2+3+4=10이다.

최댓값 10에서 (y-1)를 진행하면 10-(2-1)=9로 num을 찾을 수 있다.

 

 

다른 풀이 방법

def make_list(start_list, target):
    while start_list[-1] <= target:
        start_list.append(len(start_list)+start_list[-1])
    gap = (target-start_list[-2])
    x, y = 1+ gap, (len(start_list)-1) - gap
    return x, y
T = int(input())
for test_case in range(1, T + 1):
    number_list = list(map(int, input().split()))
    number_list.sort()
    start_list = [1]
    x1, y1 = make_list(start_list, number_list[0])
    x2, y2 = make_list(start_list, number_list[1])
    x = x1+x2
    y = y1+y2
    
    while len(start_list) < (x+y):
        start_list.append(len(start_list)+start_list[-1])
    answer = start_list[-2] + (x-1)
    print(f"#{test_case} {answer}")

풀이 출처: https://lyeong-gwa.tistory.com/129

1493. 수의 새로운 연산 (코딩테스트, SW Expert Academy)