백준 1157번 단어 공부

1157번: 단어 공부 (acmicpc.net)

1157번: 단어 공부

 

문제 요약: 단어의 길이가 1,000,000을 넘지 않는 알파벳 대소문자로 이루어진 단어가 주어진다. 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는?를 출력한다. 

 

 

문제풀이: 처음에 코딩을 하고 문제를 제출했을 때, 시간 초과가 떴다. 뭐가 문제인가 찾아보았고, 1백만인 문자열 배열을

strlen()을 이용해서 for문 안 조건문으로 사용하고 있었다. 이렇게 될 경우 루프를 한 바퀴 돌때마다 strlen이 문자열의 처음부터 끝까지 한 글자씩 NULL문자가 나오는 곳을 찾으려 하기 때문에 시간이 오래 걸릴 수밖에 없고, 이로 인해 시간 초과가 뜬 것이다. 그래서 변수를 선언해 길이 값을 저장하여 조건문에 사용하였고, 이상이 없는 것을 확인했다. 두 번째로 이 문제를 풀면서 시간을 많이 소요한 것은 문제 이해이다. 나는 이 문제가 2번 이상 사용된 알파벳이 2개 이상 존재하면 '?'를 출력하는지 알았다. 알고 보니 가장 많이 사용된 알파벳이 기준이었다. ( aabbbccccd라고 할 때 빈도 수가 가장 큰 것은 c이고, '?'를 출력하지 않지만 내가 처음 이해했던 대로라면 2번 이상 사용된 알파벳이 무려 3개이기 때문에 '?'가 출력되는 것이다. ) 이 문제를 풀면서 느낀 점은 문제를 꼼꼼히 이해해야 한다는 것이다. 나는 요즘 문제를 읽어도 머리에 잘 들어오지 않을 때가 많아서 먼저 메모장에 문제를 요약하고 어떻게 풀어갈 것인가 대충 알고리즘을 짠 후에 코딩을 시작하고 있다. 문제를 이해 못해서 못 풀었다는 핑계를 대는 것이 아니라, 코딩을 하면서 부주의했던 것들에 대한 성찰이자 앞으로 더 신경 쓰겠다는 반성의 의미이다. 말이 조금 길어졌는데 이 문제 같은 경우에는 아스키코드를 가지고 접근했다

먼저 알파벳 빈도수를 저장할 배열을 만들고 입력받은 알파벳을 하나씩 정수로 변환한 후 아스키 코드 값과 일치한 인덱스의 크기를 증가하는 식으로 코드를 짜보았다. 크기가 다 저장된 후에는 제일 빈도 수가 큰 값을 최댓값으로 저장해주고 만약 최대 값과 동일한 크기가 존재한다면?를 반환하고, 그렇지 않다면 알파벳을 출력한다.

 

 

 

 

 

 

http://colorscripter.com/s/f79AN5C

공유된 코드 - Color Scripter