Script / CSS

G1sUtil.js

G1sBlogger.js

CSS

G1sNavigationList.js

Posts List


2016년 8월 23일 화요일

[Algospot] 정리 못하는 정리베


문제 정보


문제ID
JEONGLIBE
출제자
hyunhwan
출처
제1회 알고스팟 새싹 콘테스트
시간제한
10000ms
메모리제한
65536kb
분류
.

문제 설명

아래 주어진 4개의 패턴의 문자에서 (아티스트 명)과 (곡 제목)이 중복되는 것을 제외한 유니크한 숫자를 구하는 문제입니다.

  • (트랙 번호)_(아티스트 명)_(곡 제목).mp3
  • (트랙 번호). (아티스트 명) - (곡 제목).mp3
  • (아티스트 명) - (곡 제목).mp3
  • (아티스트 명)_(곡 제목).mp3

입력값은 다음과 같으며, 비교시 대소문자는 구분하지 않습니다.
(트랙 번호) : 0 ~ 9 숫자,
(아티스트 명), (곡 제목) : 공백, 숫자, 영문자, 괄호 '(', ')'

문제 풀이

패턴이 주어졌으므로 주어진 패턴으로 파싱해서 String 값을 비교하면 되는 간단한 문제입니다.

트랙번호가 있는 패턴이 있고 없는 패턴이 있으므로, 파싱은 뒤에서부터 하는게 좋을 것 같네요.

뒤에서부터 char 값을 비교하여 '-' 또는 '_' 가 나올 때까지가 곡 제목.
곡 제목의 구분기호 부터 '-', '_', '.' 가 나올 때까지가 아티스트 명이 됩니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler
문제를 푸는 방법은 여러가지가 있습니다.

제가 구현한 방식처럼 속도를 크게 신경쓰지 않는다면, 위와같이 파싱 후 하나의 패턴으로 만들어서 Set 에 넣은 후 최종 Set의 size를 구하는 식으로도 구할 수 있습니다.

또한 이진탐색트리로 정렬해 가며 직접 유니크한 수를 구할 수도 있을 것 같구요.

String 자체가 비교하기에는 시간이 오래걸리니 해쉬값을 구해서 비교를 해도 좋을 것입니다.

단, 해쉬를 구하는 연산은 속도가 빠르면서 중복이 잘 되지 않도록 고려해야 겠지요.
물론 문제가 무한정 많은 것은 아니기 때문에 쉽고 단순한 연산만으로도 중복이 일어날 확률이 크지는 않을 것 같네요.

지금은 간단히 Set에 String 을 넣는 방법으로 문제를 해결했지만 다음에는 좀 더 대폭 감소하는 것에 도전을 할까 합니다.
== 소스보기 ==

결과

#
458672
문제
JEONGLIBE
언어
cpp
길이
889B
수행시간
72ms
결과
정답
제출일
2016-08-23

댓글 없음:

댓글 쓰기