1004: 뒤집어 더하기

Link : judge.koreatech.ac.kr/problem.php?id=1004

---

1. 문제

• 평소 숫자를 가지고 놀기 좋아하는 종섭이는 숫자를 쓰고 더하고 뒤집고 놀다가 재미있는 성질을 발견했다.
  숫자 120 을 뒤집어서 배열하면 021 이 되는데, 원래 숫자와 뒤집은 숫자를 더하면 141 (120 + 021) 이 된다. 합한 결과인 141은 앞으로 읽으나 뒤로 읽으나 같은 숫자가 된다는 것.
  이렇게 앞으로 읽으나 뒤로 읽으나 같은 것을 회문(Palindrome) 이라고 하는데, 정수가 주어졌을 때, 정수를 뒤집어 더했을 경우 더해진 숫자가 회문이 되는지 판단하는 프로그램을 만들자.

 

---

2. 문제의 조건

• 0 <= n <= 10,000,000

 

---

3. 문제 접근

• 시간 복잡도
  
  시간 제한이 1초로 주어져있고 n은 10,000,000이니 O(N)에 풀어야 한다고 생각했습니다.

 

• 아이디어
  
  str의 기본과 str를 뒤집은 결과를 int으로 반환하여 더한 다음 str[idx]와 str[len(str)-i - 1]번째가 len(str) // 2 번째 만큼 서로 같은지 확인한다.
  
  즉, O(N)의 시간 안에 풀어야하는데 실제적 계산량을 N/2므로 충분하다고 생각했습니다.

 

---

4. 풀이 방법

• 입력값 x를 str으로 받고 x를 뒤집은 값도 따로 저장한다. 그 후 x와 t를 int로 형변환 후에 더해줍니다.
• "1241"이나 "12321" 같은 짝수와 홀수 길이의 문자열에 대해선 홀수의 가운데 자리인 "3"은 신경 쓸 필요가 없으므로 len(str) // 2 까지 탐색합니다.
• str[i]와 str[len(str) - i - 1]이 다르면 False를 리턴합니다. for문 동안 같은 False가 리턴되지 않으면 True를 리턴해줍니다.

 

 

---

5. 소스코드

• cjw-git.tistory.com/13

 

---

 

cjw.git@gmail.com