본문 바로가기

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

[백준 문자열 사용하기 문제] 1157번 단어 공부 문제 풀이 및 해설 (C언어, Java언어)

오랜만에 다시 이어가는 알고리즘 문제 풀기~~~!

분류: 문자열 사용하기

출처: 백준

정답률: 37%

[1157] 단어 공부

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

조건

시간 제한: 2초, 메모리 제한 128MB

입출력

입력: 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

출력: 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

예제 입력1

예제 출력1

Mississipi

?

zZa

Z

z

Z

baaa

A

같이 문제를 풀어봐요 ~!


ANSWER

예제를 보니까 대소문자를 구별하지 않고 출력은 무조건 대문자로 하는군요!

중점은, 1. 대문자 소문자 변환과 2. 최대 개수 알파벳 구하기

요렇게겠네요 ㅎㅎ

 

가장 먼저 생각나는 방법은 아무래도 아스키코드를 활용하는 거겠죠?ㅎㅎ

저번 아스키코드 문제 풀 때 언급했었는데 기본적으로 a와 A 값 정도는 외워두는게 좋아요 

C언어 코드

[1157 단어공부 C++언어 - 아스키코드]

#include <iostream>
#include <string>
using namespace std;
int main() {	
	string word;
	int alphabetCnt[100] = {0,}; //0으로 초기화
	cin >> word;
	for (char c : word) {
		if ('a'<=c)
			c = c - 32; //아스키코드 특징을 이용해서 대문자로 변경
		alphabetCnt[c]++;
	}
	
	int max = 0; char c = '?';
	for (int alpha = 'A'; alpha <= 'Z'; alpha++) {
		if (alphabetCnt[alpha] > max) {
			max = alphabetCnt[alpha];
			c = alpha;
		}
		else if (alphabetCnt[alpha] == max) {
			c = '?';
		}
	}
	cout << c << "\n";
	return 0;
}

메모리: 4880KB

시간: 36ms

코드 길이: 537B

알파벳의 아스키코드가 아무래도 65부터 90까지라 넉넉히 배열을 100으로 잡아줬는데요

각 알파벳 코드 배열에 개수를 증가시키기 위해서요 ㅎㅎ근데 100이 좀 거슬린다 하면 아래 코드처럼 기준을 바꿔주면 됩니다.

 

[1157 단어공부 C언어 - 아스키코드]

#include <stdio.h>
int main() {
	char word[1000001];
	int alphabetCnt[26] = { 0, }; //배열 크기를 알파벳 개수로 맞추기 
	fgets(word, sizeof(word), stdin);

	for (int i = 0; word[i]!='\0'; i++) {
		if ('a' <= word[i])
			word[i] = word[i] - 32; //아스키코드 특징을 이용해서 대문자로 변경
		alphabetCnt[word[i]-'A']++; //이렇게 하면 0부터 들어가겠죠?
	}
	
	int max = 0; char c = '?';
	for (int alpha = 0; alpha <= 'Z'-'A'; alpha++) {
		if (alphabetCnt[alpha] > max) {
			max = alphabetCnt[alpha];
			c = alpha;
		}
		else if (alphabetCnt[alpha] == max) {
			c = '?';
		}
	}
	printf("%c", (c=='?')? '?': c+65);//인덱스를 0~25로 맞춰줬으니 출력할때는 다시 맞춰줘야해요
	return 0;
}

메모리: 1972KB

시간: 16ms

코드 길이: 510B

같은 풀이지만 fgets를 사용해서 조금 변형을 줘봤어요 ㅎㅎㅎ

 

[1157 단어공부 C언어 - toupper ]

항상 뭔가 언어를 새로 배울때면... 한 번쯤 타이핑 해보는 대소문자 변환 함수를 사용해볼게요 ㅎㅎ

자바는 toUpperCase가 굉장히 활성회되어 있는데 C언어는 아스키코드가 더 대중적인 느낌..?(나만 그릏게 느끼나..ㅎㅎ)

#include <stdio.h>
#include <ctype.h>
int main() {
	char word[1000001];
	int alphabetCnt[26] = {0, }; //알파벳 개수로 맞추기 
	scanf("%s", word);

	for (int i = 0; word[i]!='\0'; i++)
		alphabetCnt[toupper(word[i])-'A']++; //toupper를 사용했어요
	
	int max = 0; char c = '?';
	for (int alpha = 0; alpha <= 'Z'-'A'; alpha++) {
		if (alphabetCnt[alpha] > max) {
			max = alphabetCnt[alpha];
			c = alpha;
		}
		else if (alphabetCnt[alpha] == max) c = '?'; //여러 개 존재하는 경우 '?'
	}
	putchar((c=='?')? '?': c+65); //아스키코드상 대문자 A는 65
	return 0;
}

 

메모리: 1972KB

시간: 12ms

코드 길이 : 454B

이번에는 출력을 한 글자만 딱 내놓는 putchar를 사용해 변형을 줘봤어요 ㅎㅎ 

 

이렇게 푸신 분이 있더라고요 ㅎㅎ 대문자와 소문자가 32차이가 나는데(아스키 코드 특성상 소문자 a는 97 대문자 a는 65)

32는 2의 5승에서 차이가 난다는 점을 이용하신 것 같아요. 나머지는 그대로 두고 2의 5승 자리수가 1이면 and로 0으로 만들어버리는거죠. 짝짝짝ㅎㅎ

 

JAVA언어 코드

C언어는 이정도로 하고 자바 풀이로 넘어가 볼까요?ㅎㅎ 설명은 앞에서 했으니 코드로

[1157 단어공부 Java언어 - toUpperCase ]

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
class Main{
	public static String input;
	public static int max;
	public static char result;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] word =br.readLine().toCharArray(); br.close();
		int[] alphabetCnt = new int[26];
		for(int i=0; i<word.length; i++)
			alphabetCnt[Character.toUpperCase(word[i])-'A']++;
	
		for(int i=0; i<='Z'-'A'; i++) {
			if(alphabetCnt[i]>max) {
				max = alphabetCnt[i];
				result = (char)(i+65);
			}else if (alphabetCnt[i]==max) result = '?';
		}
		System.out.print(result);
	}
}

메모리: 24116KB

시간: 172ms

코드 길이: 740B

각 알파벳을 대문자로 변경시켜준 뒤 개수를 세었어요 

 

[1157 단어공부 Java언어 - &와 shift 비트 연산]

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
class Main{
	public static String input;
	public static int max;
	public static char result;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] word =br.readLine().toCharArray(); br.close();
		int[] alphabetCnt = new int[100];
		for(int i=0; i<word.length; i++) {
			if((word[i] & 32) == 32 ) //소문자 일 경우
				word[i]-=32; //대문자로
			alphabetCnt[word[i]]++;
		}
		for(int i='A';i<='Z' ;i++) {
			if(alphabetCnt[i]>max) {
				max = alphabetCnt[i];
				result = (char)i;
			}else if(alphabetCnt[i]==max) result = '?';
		}
		System.out.print(result);
	}
}

메모리: 24084KB

시간: 164ms

코드 길이 708B

아까 C언어에서 32의 특성을 이용해 &연산자를 한 걸 보고 문득 생각나서 작성해본 코드입니다. 

가독성이 너무 안좋아서 딱히 좋은 방법인지는 잘 모르겠...

 

[1157 단어공부 Java언어 -아스키코드]

마지막으로 앞에서 설명한 아스키코드 코드 보고 마칠게요 ㅎㅎ

import java.io.IOException;
public class Main {
	public static void main(String[] args) throws IOException {
		int[] alphabetCnt= new int[26];
		for (int c = System.in.read(); c >= 'A'; c = System.in.read()) {
			alphabetCnt[Character.toUpperCase(c) - 'A']++;
		}

		int index = 0;
		boolean isDuplicated=false;
		for (int max = -1, i = 0; i < 26; i++) {
			if (alphabetCnt[i] > max) {
				max = alphabetCnt[i];
				index = i; isDuplicated=false;
			} else if (alphabetCnt[i] == max) isDuplicated=true;
		}
		if (isDuplicated) System.out.print("?");
		else System.out.print((char) (65 + index));
	}
}

메모리: 13184KB

시간: 120ms

코드 길이: 600B

이번에는 버퍼 안쓰고 그냥 기본적인 System.in.read 메서드 사용해서 한 글자씩 읽어줬어요 ㅎㅎ

오늘 풀이는 여기까지입니다!! 다음 알고리즘 포스팅에서 또 봐요 :)

도움이 됐다면 가시기 전에 공감 우떤가요?! !!