본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[COCI 2012/2013 기출, 백준 5622번] 다이얼 문제 해설 및 C/C++,자바 풀이

출처: COCI 2012/2013

출처: 백준 알고리즘 (번역본)

정답률: 58.1%

분류: 문자열 사용하기

5622번 다이얼 문제

문제

상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다.

전화를 걸고 싶은 번호가 있다면 숫자 하나를 누른 다음에 금속 판이 있는 곳까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다.

숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해서는 1초씩 더 걸린다. 상근이의 할머니는 전화번호를 각 숫자에 해당하는 문자로 외운다. 즉 어떤 단어를 걸 때, 각 알파벳에 해당하는 숫자를 걸면 된다. 예를 들어, UNUCIC는 868242와 같다.

할머니가 외운 단어가 주어졌을 때, 이 전화를 걸기 위해서 필요한 시간을 구하는 프로그램을 작성하시오.

입출력

입력: 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어는 2글자~15글자로 이루어져 있다.

출력: 첫째 줄에 다이얼을 걸기 위해서 필요한 시간을 출력한다.

 

다 풀었으면 스크롤을 내려서

같이 ANSWER를 확인하고 답안을 비교해봅시당!!


 

ANSWER

문제가 기네요 ㅎㅎ 예시를 통해 이해해봅시다.

1이 2초가 걸리니까 2면 3초..즉 +1씩 시간이 걸리는거네요?

WA일 경우, W가 9에 속해있으므로 10초 걸리고 A가 2에 걸려있으므로 3초 걸려서 도합 13이 되는거군요 ㅎㅎ

UNUCIC 또한 U가 8이라 9초가 걸리는데 총 2개 있으므로 18초,

N은 6이므로 7초, C는 2이므로 3초인데 두 개라 6초 마지막 I는 4에 해당하므로 총 5초가 걸리네요

18+7+6+5 = 36!! 입력이 알파벳인데 알파벳이 9에서 끝나네요 근데 0은 왜있는거지...ㅎㅎ

 

이제 문제를 풀기 위한 특징을 정리해봅시다. 일단 문자가 어느 숫자에 속하는지 알수 있으면 바로바로 계산하면 좋겠죠? 당장 생각나는건 아무래도 가장 쉬운 배열인데.. 음..그 외에도 각 알파벳 개수를 세서 곱하기를 해준 후 더해줄 수도 있겠어요.7하고 9 빼고 다 3개씩인거보니까 나누기 사용해서 쉽게 접근할 수 있을 것 같은데... 일단 생각나는건 이정도..?

C/C++ 언어 코드

[5622번 다이얼 - C++언어, 3씩 묶인 규칙 이용]

먼저, 나누기를 이용해서 시간을 계산해줬어요 ㅎㅎ 근데 7하고 9의 경우 예외가 있죠?

3개씩 잘 짝지어서 가다가 PQR/STU/VWXYZ이렇게 가야 정상인데(숫자가 9까지이니까 세 개씩 나누다보면 VWXYZ가 모두 하나로 들어갈수밖에 없겠죠)

그런데 실제 다이얼을 보면 PQRS/TUV/WXYZ로 갔잖아요

여기서 다른 애는 S와 V라는 점을 이용했어요.

(- 아님 따로 삐져나오는 YZ를 SV처럼 같이 예외처리해줘도 되는데 이럼 두 코드가 넘 비슷해지니까 요건 자바에서 작성해볼게요 ㅎㅎ)

#include <iostream>
#include <string>
using namespace std;
int main() {
	string phone; int result = 0, time;
	cin >> phone;
	int alphabetCnt[26] = { 0, };
	for (char c : phone) {
		alphabetCnt[c - 'A']++;
	}
	for (int i = 0; i <= 'Z' - 'A'; i++) {
		if (i == 'S'-'A' || i == 'V'-'A') {
			result += (i / 3 + 2)*alphabetCnt[i];
			continue;
		}
		if (alphabetCnt[i]) { 
			time = i / 3 + 3;
			result += (time > 9) ? 10 * alphabetCnt[i] : time * alphabetCnt[i];
		}
	}
	cout << result;
	return 0;
}

메모리: 1988KB

시간 : 0ms

코드길이: 497B

0, 1, 2는 3초가 걸린다, 3,4,5는 4초가 걸린다.. 3으로 나눈 값에 +3을 해준 규칙이 존재하는 걸 알 수 있어요.

[5622번 다이얼 - C언어, 배열]

그 다음 앞에 중얼중얼 파트(?)에서 이야기했던 배열을 이용해 풀어봅시다.

#include <stdio.h>
int main()
{
	int times[] = { 3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10 };
	char phone[16]; //최대 16글자
	int result=0; //초기화 안하면 자바랑 다르게 쓰레기값이 들어가서 꼭 초기화를 해줘야해요
	scanf(" %s", phone);
	for (int i = 0; phone[i]!='\0'; i++)
		result += times[phone[i] - 'A'];
	printf("%d", result);
}

메모리: 1116KB

시간: 0ms

코드: 277B

메모리를 차지하는 크기와 코드 길이가 줄어들었어요 ㅎㅎ

[다른 사람 풀이로 배우기 1]

노가다.... 좋은 코드는 아니지만.. 깔끔하게 코드를 잘 정리하셨네요 ㅎㅎㅎㅎ뭔가 기분이 좋아서 투척ㅎㅎ

[다른 사람 풀이로 배우기 2]

참고로 0x0A는 아스키코드로 라인피드(LF)를 말해요. 한줄만 입력받는다는 것을 저렇게 표현했군요 ㅎㅎ

각 다이얼 숫자의 처음 알파벳을 기준으로 판별하고 있어요(2의 시작은 A, 3의 시작은 D, ...)

즉 내가 해당하는 숫자에 아직 도달하지 못해서 다이얼을 돌려줄 때마다 1을 더하고 있네요 ㅎㅎ (6번 라인)

예를 들어, E이면, A보다 크니까 다이얼 하나 돌아가므로 일 더하고,

다음 3번에 해당하는 D보다 크거나 같으니까, 또 다이얼이 하나 돌아가니 1을 더해주는거죠. 다음 4번 시작점 G에서는 num>=c; 이 부문이 충족이 안되니까 반복문을 빠져나오게 되겠죠?ㅎㅎㅎ

 

JAVA 언어 코드

[5622번 다이얼 - JAVA언어, 스위치]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	     char[] dials = br.readLine().toCharArray();
	     int sum =0;
	     for (char c : dials) {
	    	 sum += 2;
	    	 switch(c) {
	    	 case 'W': case'X':  case'Y': case'Z': 
	    		 sum+=1;
	    	 case 'T': case'U':  case'V':
	    		 sum+=1;
	    	 case 'P': case'Q':  case'R': case'S':
	    		 sum+=1;
	    	 case 'M': case'N':  case'O':
	    		 sum+=1;
	    	 case 'J': case'K':  case'L':
	    		 sum+=1; 
	    	 case 'G': case'H':  case'I':
	    		 sum+=1;
	    	 case'D':  case'E': case'F':
	    		 sum+=1; 
	    	 case 'A': case'B': case'C': 
	    		 sum+=1;
	    	 }
	     }
	     System.out.println(sum); 
	}
}

 

[다른사람 풀이로 배우기1]과 [다른사람 풀이로 배우기2]를 보다가 문득 생각나서 ㅎㅎㅎ

스위치 케이스로 풀어봤어요 ㅎㅎ 다이얼이 시계방향으로 돌아가잖아요? 9를 누르면 9->8->7... 이렇게 처음위치로 돌아간다고 했어요 ㅎㅎ 각 case는 다이얼 숫자를 의미하고 돌아갈때마다 +1을 쌓아주는 코드입니다.

[C언어 '다른 사람 풀이1' 의 자바 버전입니다]

[5622번 다이얼 - JAVA언어, 3특징]

위 C언어 코드에서 설명했던 방식이지만 형식을 조금 바꿔서 푼 코드입니다.

0, 1, 2는 3초가 걸린다, 3,4,5는 4초가 걸린다.. 3으로 나눈 값에 +3을 해준 규칙이 존재하는 걸 알 수 있어요. 이번에는 예외 처리를 S, V, Y, X로 둬볼게요 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static int time;
	public static void main(String[] args) throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	     char[] dials = br.readLine().toCharArray();
	     for(char c: dials) {
	    	 time += (c-'A')/3+3;
	    	 if(c=='S'||c=='V'||c=='Y'||c=='Z')
	    		 time--;
	     }
	     System.out.print(time);  
	}
}

메모리: 12880

시간: 72ms

코드 길이: 483B

역시 코드는 다듬어질 수록.. 더 좋아지는 것 같아요 ㅎㅎ 조건문에서 매번 'A'를 빼는 게 지저분해보여서 애초에 시간 계산할 때 한번에 처리해줬어요 ㅎㅎ

그리고 c/3+3 과 c/3+2는 차이가 1이라는 점을 활용했습니다.

 

오늘은 여기까지입니다.

보고 가는 길에 공감!! 오늘도 문제푸느라 수고했어요 ㅎㅎ 좋은 하루 되세요