핸드폰 번호 궁합
2 초 | 256 MB | 3533 | 2684 | 2383 | 77.622% |
문제
어린시절 다들 한 번씩은 이름으로 궁합을 본 적이 있을 것이다. 이것과 비슷한 방식으로 중앙대학교에는 핸드폰 번호 궁합을 보는 것이 유행이라고 한다.
핸드폰 번호 궁합을 보기 위해서는 먼저 궁합을 보고싶은 두 중앙대생 A와 B의 핸드폰 번호에서 맨 앞의 010과 "-"(하이픈)을 모두 제외한 후, A부터 시작하여 한 숫자씩 번갈아가면서 적는다. 그리고 인접한 두 숫자끼리 더한 값의 일의 자리를 두 숫자의 아래에 적어나가면서 마지막에 남는 숫자 2개로 궁합률을 구하게 된다.
예를 들어, 아래의 그림과 같이 A의 번호가 010-7475-9336 이고, B의 번호가 010-3619-5974 이면, 7346715995393764에서 시작하여 070386484822030, 77314022204233, 4045424424656, 449966866011, 83852442612, 1137686873, 240344450, 64378895, 0705674, 775131, 42644, 6808, 488, 26이 되어 둘은 26%의 궁합률을 가지게 된다.
위의 예시에서처럼 인접한 두 숫자를 더한 값이 두자리 정수가 되더라도, 일의 자리 숫자만 적는다. 가령 7과 3을 더하면 0을 적고, 4와 8을 더하면 2를 적는다.
중앙대학교에서 유행인 핸드폰 번호 궁합률을 알아보는 프로그램을 작성해보자. 단, A와 B의 핸드폰 번호는 다르다고 가정한다.
입력
첫 번째 줄에는 궁합을 보고싶은 중앙대생 A의 핸드폰 번호가 주어진다.
두 번째 줄에는 궁합을 보고싶은 상대방 B의 핸드폰 번호가 주어진다.
핸드폰 번호는 맨 앞의 010과 "-"(하이픈)을 제외하여 숫자 8개로 주어진다.
A와 B의 핸드폰 번호는 같지 않다.
출력
A와 B의 핸드폰 번호 궁합률을 두자리 정수로 출력한다.
십의 자리가 0이어도 앞에 0을 붙여 두자리로 출력한다.
예제 입력 1 복사
74759336
36195974
예제 출력 1 복사
26
예제 입력 2 복사
01234567
12345678
예제 출력 2 복사
02
알고리즘 분류
코드
package 핸드폰번호궁합;
import java.io.*;
import java.util.stream.IntStream;
/*
[시간 복잡도] O(N^2)
---
[문제 해결 방법]
1. 핸드폰 번호 병합:
- 두 핸드폰 번호를 번갈아가며 하나의 문자열로 병합합니다. 각 숫자를 번갈아가며 궁합을 계산하기 위해서 입니다.
2. 병합된 문자열을 숫자로 변환:
- 병합된 문자열을 숫자의 배열로 변환합니다. 각 문자를 숫자로 변환하여 배열에 저장합니다.
3. 인접한 두 숫자의 합 계산:
배열의 크기가 2가 될 때까지 인접한 두 숫자를 더하고, 그 결과의 일의 자리를 새로운 배열에 저장하는 작업을 반복합니다.
이 과정을 통해 궁합을 계산합니다.
---
*/
public class Main {
static final int DIVIDER_TEN = 10;
public static void main(String[] args) throws IOException {
// BufferedReader br = new BufferedReader(new StringReader(input1()));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 핸드폰 번호 입력
String phoneNumberA = br.readLine();
String phoneNumberB = br.readLine();
// 번갈아가며 병합한 문자열 생성
StringBuilder mergedPhoneNumbers = new StringBuilder();
for (int i = 0; i < 8; i++) {
mergedPhoneNumbers.append(phoneNumberA.charAt(i)).append(phoneNumberB.charAt(i));
}
// 병합된 문자열을 리스트로 변환
int[] phoneNumberDigits = new int[16];
for (int i = 0; i < 16; i++) {
phoneNumberDigits[i] = Character.getNumericValue(mergedPhoneNumbers.charAt(i));
}
// 인접한 두 숫자를 더한 값의 일의 자리를 계산
// [방법1] ***IntStream을 사용하여 처리***
// 속도 : 116MS
while (phoneNumberDigits.length > 2) {
int[] finalPhoneNumberDigits = phoneNumberDigits;
phoneNumberDigits = IntStream.range(0, phoneNumberDigits.length - 1)
.map(i -> (finalPhoneNumberDigits[i] + finalPhoneNumberDigits[i + 1]) % DIVIDER_TEN)
.toArray();
}
// [방법2] ***두 포인터 방식*****
// 속도 : 132MS
// while (phoneNumberDigits.length > 2) {
// int[] newPhoneNumberDigits = new int[phoneNumberDigits.length - 1];
// int left = 0;
// int right = 1;
// int index = 0;
// while (right < phoneNumberDigits.length) {
// newPhoneNumberDigits[index++] = (phoneNumberDigits[left] + phoneNumberDigits[right]) % DIVIDER_TEN;
// left++;
// right++;
// }
// phoneNumberDigits = newPhoneNumberDigits;
// }
// [방법3] *** for loop 방식***
// 속도 : 208MS
// while (nums.length > 2) {
// int[] newNums = new int[nums.length - 1];
// for (int i = 0; i < nums.length - 1; i++) {
// newNums[i] = (nums[i] + nums[i + 1]) % 10;
// }
// nums = newNums;
// }
// 결과 출력
for (int digit : phoneNumberDigits) {
bw.write(String.valueOf(digit));
}
bw.flush();
bw.close();
br.close();
}
// 예제 출력1 26
static String input1() {
return "74759336\n" + "36195974";
}
// 예제 출력2 02
static String input2() {
return "01234567\n" + "12345678";
}
}
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 가장긴감소하는부분수열 - 11722번 (0) | 2024.06.15 |
---|---|
[백준] 부녀회장이될테야 - 2775번 (1) | 2024.06.15 |
[백준] 가장 긴 증가하는 부분 수열 - 11053번 (1) | 2024.06.15 |
DP(Dynamic Programming) 핥아보기 (0) | 2024.06.15 |
[백준] 우유축제 - 14720번 (0) | 2024.06.14 |