프로그래밍 문제 하나
2021.05.13 00:25
프로그래밍 문제
~~~~~~~~~~~~~~~~~~~~~~~~~~~
0과 1로만 이루어져 있으며, 0의 개수와 1의 개수가 동일한 문자열 S가 주어진다. 당신은 S에 다음과 같은 작업을 여러 번 수행할 수 있다:
S의 길이 2k인 연속한 부분문자열이 앞 k개 문자가 모두 동일하고, 또한 뒤 k개 문자가 서로 동일하며, 0과 1을 모두 포함할 때, 그 부분문자열을 제거할 수 있다.
예를 들어, S = “0111000011”인 경우, S의 2번째 문자부터 7번째 문자까지인 “111000”을 제거하는 것이 가능하다. 이 작업 후에는 제거된 부분의 앞부분과 뒷부분이 연결되어 S = “0011”이 된다. 그러면 이제 한 번의 작업을 통해 “0011”을 제거할 수 있으므로 초기 S = “0111000011”는 두 번의 작업을 통해 빈 문자열로 만들 수 있다.
여러분의 목표는 최소 횟수의 작업을 통해 S를 빈 문자열로 만드는 것이다. 최소 횟수의 작업으로 S를 빈 문자열로 만드는 과정을 구하여라.
~~~~~~~~~~~~~~~~~~~~~~~~~~~
댓글 [3]
-
오호라7 2021.05.13 02:30
-
메리아 2021.05.13 14:11
예시를 보니 문제가 지시하는 바가 뭔지 알겠군요.
근데 쉬운거 같으면서도 좀 어렵네요.
압축알고리즘 연습 일지도...
-
scrce 2021.05.13 15:49
1. a=0으로 초기화
2. For 문으로 돌린다.
S에 문자열 111000이 있으면 삭제 후 a를 1씩 증가
없으면 S 문자열을 공백 처리 후 종료
답: 최소 횟수는 a(char)에 들어간 수
해석: For문 첫번째는 111000 삭제 후 a=a+1 (a=1이된다.)
For문 두번째에서 111000이 없으므로 S에 문자열을 공백처리 후 종료, a=a+1 (a=2가된다.)
최소 횟수는 2
번호 | 제목 | 글쓴이 | 조회 | 등록일 |
---|---|---|---|---|
[공지] | 자유 게시판 이용간 유의사항 (정치, 종교, 시사 게시물 자제) [1] | gooddew | - | - |
47016 | 회사에서 벌어지는 요지경 [3] | 용가리266 | 1493 | 02-06 |
47015 | 이무진 - 에피소드(여자 버전) | toz21 | 744 | 02-06 |
47014 | 맥북 지름신 [4] | 긍지버림 | 611 | 02-06 |
47013 | 3개국어 외국어 무료 공부하기 채널입니다. [1] | 테리우스^^ | 839 | 02-05 |
47012 | 가끔씩 게임 다운 받는 곳이네요 .. | 나뭇꾼 | 935 | 02-05 |
47011 | SK 브로드 밴드 인터텟 사용기 [12] | gooddew | 1281 | 02-05 |
47010 | "화상 회의 후 340억 송금했는데…" 금융사 직원 ... [1] | 사이버초보 | 1280 | 02-05 |
47009 | 토스 발렌타인 이벤트 | 소녀시대 | 528 | 02-05 |
47008 | 큰나무님 공유 도구 Shares3.8 받으려 했는데 늦었군용 [2] | 라랑 | 937 | 02-04 |
47007 | 초심을 잃지 않은 생활의 달인 | FINAL | 1011 | 02-04 |
47006 | Steam AI image Generator를 실행 해보았습니다. [4] | SHIELD | 550 | 02-04 |
47005 | AFC 아시안컵 4강전 대진표 [3] | asklee | 1039 | 02-04 |
47004 | 사제 세탁기 호스 1년 사용 후기 [3] |
|
886 | 02-04 |
47003 | 사랑해요~ 이란~ [4] | 소소생 | 892 | 02-04 |
47002 | Win 11 작업표시줄 최적화 후기 [1] | ton3d | 866 | 02-04 |
47001 | 5년 만에 다녀온 볼링장 [4] | 긍지버림 | 435 | 02-03 |
47000 | 영상 [1] |
|
439 | 02-03 |
46999 | 말도 많고 탈도 많은 StartAllBack 3.7.3.4856..이렇습니다 [4] | 염라대왕 | 869 | 02-03 |
46998 | 언제까지 통할것인가 - 아시안컵 [4] | 소소생 | 536 | 02-03 |
46997 | 대한민국이 호주 를 잡았다/ [4] | kang | 888 | 02-03 |
문제가 원래 그런건지, ton3d님이 줄여 쓰느라 잘못 쓴 것인지는 알 수 없지만,
'S의 길이 2k인 연속한 부분문자열이 앞 k개 문자가 모두 동일하고, 또한 뒤 k개 문자가 서로 동일하며, ' 부분과 뒤에 예시로 든
S = “0111000011”가 서로 오류입니다.
'k개 문자가 모두 동일해야 한다'면 2k인 s문자는 00001111, 111111000000 이런식이어야 하지 않나요?
그래서 문제가 맞고 예시가 틀렸다면, 어떤 문자열이 와도 이 문제는 1번만 제거가 이루어 집니다.
설명이 잘못된듯 합니다.
오류찾기가 생활화된 프로그래머는 이런 문제를 안냅니다.