문제
https://www.acmicpc.net/problem/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
'코딩 테스트 스터디 > 백준' 카테고리의 다른 글
[실버 III] 2606번. 바이러스 (0) | 2022.04.06 |
---|---|
[골드 V] 14503번. 로봇 청소기 (0) | 2022.04.05 |
[실버 IV] 24060번. 알고리즘 수업 - 병합 정렬 1 (0) | 2022.02.23 |
[실버 V] 16171번. 나는 친구가 적다 (Small) (0) | 2022.02.23 |
[실버 IV] 1764번. 듣보잡 (0) | 2022.02.20 |