[실버 IV] 4881번. 자리수의 제곱

 문제 

https://www.acmicpc.net/problem/4881

4881번: 자리수의 제곱

 사용 언어 

Python3

 풀이 과정 

이게 제일 효율적인 방법은 아니더라도 테스트 케이스는 다 맞길래 맞다고 생각했는데!!!

왜 때문에 틀렸습니다?! 반례를 찾으려고 열심히 아무 숫자나 넣어봤는데 내 머리로 계산한 답과 모두 일치했다...

import sys

cases = []
while True:
    case = list(sys.stdin.readline().strip().split())
    if case == ['0', '0']:
        break
    cases.append(case)

def sumEach(case):
    sequence1 = [int(case[0])]
    sequence2 = [int(case[1])]
    isEnd1 = False
    isEnd2 = False
    while (not isEnd1 or not isEnd2):
        if set(sequence1) & set(sequence2): # 만약 겹치는 수(교집합)가 있으면
            common = list(set(sequence1) & set(sequence2))[0]
            result = sequence1.index(common) + sequence2.index(common) + 2
            return result # 두 수열 길이의 합의 최솟값 return

        sum1 = 0
        sum2 = 0
        for i in str(sequence1[-1]):
            sum1 += int(i) ** 2
        if sum1 in sequence1: # 자리수의 제곱의 합이 list에 이미 있으면
            isEnd1 = True # list 조합 완성
        else:
            sequence1.append(sum1) # 없으면 list에 추가

        for i in str(sequence2[-1]):
            sum2 += int(i) ** 2
        if sum2 in sequence2:
            isEnd2 = True
        else:
            sequence2.append(sum2)

    return 0 # while문을 끝까지 돌아도 겹치지 않으면 0

for case in cases:
    result = sumEach(case)
    print(f'{case[0]} {case[1]} {result}')

(스터디 팀원들의 도움을 받아😂) 알고보니 이렇게 짜면 사이클을 다 돌기 전에 겹치는 수가 나오는 경우 사이클을 다 돌아서 더 작은 합이 나오는 경우의 수를 생각하지 못한다는 맹점이 있었다!

그러니까 예시를 들어보면

위와 같은 경우 내 코드에서는 22가 사실 사이클을 다 돌지 않았음에도 89라는 겹치는 수가 있다고 바로 89로 계산하고 종료한다. 고친 코드로의 정답은 다음과 같이 42일 경우이다.

간략히 설명하면 그냥 두 리스트 모두 사이클이 생겨서 종료될 때까지 while문을 돌렸고,

그렇게 얻은 두 수열로 `첫 번째 수열에서 먼저 나오는 중복값의 인덱스의 합`과 `두 번째 수열에서 먼저 나오는 중복값의 인덱스의 합`의 최솟값을 구했다.

그리고 처음부터 값이 같은 89 89 같은 경우는 사이클을 구할 필요가 없기 때문에 while문을 시작하자마자 if문으로 걸러주었다.

 

내가 처음에 이 문제가 이해가 안됐던 게 다음과 같은 문장이었는데

두 숫자가 주어졌을 때, 같은 수가 나올 때 까지 필요한 수열의 길이의 합의 최솟값을 구하는 프로그램을 작성하시오.

이를 간과한 게 결국 더 돌아가게 만들었다.😅

 

이 문제의 교훈은 합의 최솟값/최대값이라는 말이 들어간다면 경우의 수가 여러개인 경우가 무조건 있으니 꼭 고려해야 한다는 것!!!

 

좀 걸렸던 점은 사이클을 끝까지 돌기 때문에 겹치는 부분이 어쩔 수 없이 길어지는데, 코드의 간편함을 위해 list comprehension을 사용했더니 break를 할 수가 없어서 다 계산해줘야 하는 것이 마음에 안들었다. 나는 각각 첫 번째 값 89랑 42만 필요한데!

이 부분을 수정하면 시간을 더 줄일 수 있을 것 같았지만... 찾아보니 list comprehension을 포기해야 하는 부분 같아서 시도하지 않았다. 어쨌든 항상 뿌듯한 맞았습니다! 시간도 나쁘진 않은 것 같다.

+) 2022-04-08에 추가

스터디원의 코드리뷰를 참고해서 몇 가지를 수정했더니 시간이 근소하게 줄어들었다. 코드도 더 이해하기 깔끔해졌다.

아래 제출 답안도 수정해놓았다.

 제출 답안 

import sys

cases = []
while True: # 0 0이 입력될 때까지 입력받기
    case = list(sys.stdin.readline().strip().split())
    if case == ['0', '0']:
        break
    cases.append(case)

def sumEach(case):
    sequence1 = [int(case[0])]
    sequence2 = [int(case[1])]
    if sequence1 == sequence2:
        return 2
    
    while True:
        sum1 = 0
        for i in str(sequence1[-1]): # 각 자리수의 제곱의 합 구하기
            sum1 += int(i) ** 2
        if sum1 in sequence1: # 자리수의 제곱의 합이 list에 이미 있으면
            break # list 조합 완성
        else:
            sequence1.append(sum1) # 없으면 list에 추가
    while True:
        sum2 = 0
        for i in str(sequence2[-1]):
            sum2 += int(i) ** 2
        if sum2 in sequence2:
            break
        else:
            sequence2.append(sum2)

    if set(sequence1) & set(sequence2): # 만약 겹치는 수(교집합)가 있으면
        common1 = [x for x in sequence1 if sequence2.count(x) > 0][0] # sequence1를 기준으로 처음으로 겹치는 수
        common2 = [x for x in sequence2 if sequence1.count(x) > 0][0] # sequence2를 기준으로 처음으로 겹치는 수
        result1 = sequence1.index(common1) + sequence2.index(common1) + 2 # common1 기준 길이의 합
        result2 = sequence1.index(common2) + sequence2.index(common2) + 2 # common2 기준 길이의 합
        return min(result1, result2) # 두 수열 길이의 합의 최솟값 return
    else: # 만약 겹치는 수(교집합)가 없으면
        return 0

for case in cases: # 각각의 경우에 대해 계산하고 출력
    result = sumEach(case)
    print(f'{case[0]} {case[1]} {result}')

 공부한 내용 

index 함수

배열에서 원하는 값의 위치를 찾기 위해 기본 내장함수인 index 함수를 사용할 수 있다.이 때 중복된 값이 있으면 가장 최소의 위치를 반환한다.

a 리스트에서 10의 위치 찾기

a = [11,10,12,13,20,31,11,10,10,11]
print(a.index(10)) # 1

a 리스트에서 2번째 ~ 9번째 위치에서 10의 위치 찾기

a = [11,10,12,13,20,31,11,10,10,11]
print(a.index(10,2,9))    # index(value, start, end) # 7

a 문자열에 '1' 이라는 문자 위치 찾기

a = '123451'
print(a.index('1')) # 0

a 문자열에 1번째 ~ 6번째 위치에서 '1' 이라는 문자 위치 찾기

a = '123451'
print(a.index('1',1,6)) # 5

 

출처: https://pydole.tistory.com/entry/Python-index-%ED%95%A8%EC%88%98-%EB%B0%B0%EC%97%B4%EC%97%90%EC%84%9C-%EC%9B%90%ED%95%98%EB%8A%94-%EA%B0%92%EC%9D%98-%EC%9C%84%EC%B9%98-%EC%B0%BE%EA%B8%B0

f-string formatting

자바스크립트의 백틱 `과 같이 파이썬에서도 버전 3.6부터 보다 편한 출력 형식을 사용할 수 있게 되었다.

f-string의 모양은 f와 {}만 알면 됩니다. 문자열 맨 앞에 f를 붙여주고, 중괄호 안에 직접 변수 이름이나 출력하고 싶은것을 바로 넣으면 됩니다.
f'문자열 {변수} 문자열'

# 문자열 맨 앞에 f를 붙이고, 출력할 변수, 값을 중괄호 안에 넣습니다.
s = 'coffee'
n = 5
result1 = f'저는 {s}를 좋아합니다. 하루 {n}잔 마셔요.'
print(result1)

출처: https://blockdmask.tistory.com/429 

두 리스트의 중복값 찾기(feat. list comprehension)

사실 순서가 중요하지 않으면 set() 자료형의 교집합을 사용하는 것이 가장 좋다고 생각한다. 그런데 나는 1번 리스트를 기준으로 2번 리스트에서, 그리고 그 반대에서 첫 번째로 겹치는 중복값을 찾아야 했기 때문에 방법을 찾아보다가 list comprehension으로 간단히 해결한 방법을 찾았다.

list1 = ["피카츄",'라이츄','파이리','꼬부기','버터플','엔젤몬','아구몬','또가스']
list2 = ['아구몬','파닥몬','에테몬','팔몬','엔젤몬','피카츄','라이츄','파이리']

print([x for i in list1 for x in list2 if i in x])
# ['피카츄', '라이츄', '파이리']
print([x for i in list2 for x in list1 if i in x])
# ['아구몬', '엔젤몬', '피카츄', '라이츄', '파이리']

list comprehension안에서 이중 for문을 사용하는 것은 처음이었는데 너무 깔끔하다.

이 방법을 사용할 때 개인적으로 주의해야 할 것 같은 점은 기준을 list1로 두냐 list2로 두냐에 따라 결과값이 달라지기 때문에 이런 방식이 필요할 때만 사용하자.

출처: https://business-analytics.tistory.com/9

 다른 사람 답안 

파이썬은 아니지만 문제에서 제시한 사이클을 이용한 풀이를 찾을 수 있었다. 이용하라고 준 힌트이니 괜찮은 방법인 것 같다.

#include <iostream>
#include <vector>
 
using namespace std;
 
int arr[9] = { 89, 145, 42, 20, 4, 16, 37, 58, 1 };
 
int cal(int n) {
    int r = 0;
    while (n) {
        r += (n % 10) * (n % 10);
        n /= 10;
    }
    return r;
}
 
bool in(int n) {
    for (int i = 0; i < 9; ++i) {
        if (n == arr[i]) return true;
    }
    return false;
}
 
int main() {
    int a, b;
    while (true) {
        scanf("%d %d", &a, &b);
        if (a + b == 0) break;
        printf("%d %d ", a, b);
        vector<int> aa;
        vector<int> bb;
        while (in(a) == false) {
            aa.push_back(a);
            a = cal(a);
        }
        while (in(b) == false) {
            bb.push_back(b);
            b = cal(b);
        }
 
        if (a == 1 ^ b == 1) {
            printf("0\n");
            continue;
        }
         
        if (a == b) {
            while (!aa.empty() && !bb.empty() && aa.back() == bb.back()) {
                aa.pop_back();
                bb.pop_back();
            }
            printf("%d\n", aa.size() + bb.size() + 2);
        }
        else {
            int ai, bi;
            for (int i = 0; i < 8; ++i) {
                if (a == arr[i]) ai = i;
                if (b == arr[i]) bi = i;
            }
            int r = ai > bi ? ai - bi : bi - ai;
            printf("%d\n", aa.size() + bb.size() + 2 + (r > 4 ? 8 - r : r));
        }
    }
 
    return 0;
}

출처: https://jeonggyun.tistory.com/48