프로그래밍 문제 하나
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 | - | - |
43106 | 8.1에서 윈도10 정품인증 하신분들.. [2] |
|
2840 | 07-18 |
43105 | 6년된 컴퓨터 살리기 (윈 8.1 업그레이드) [4] | 도감 빈나 | 2840 | 11-08 |
43104 | 하드를 그냥버려버렸네요....제대로 폐기했어야하는데 [9] |
|
2840 | 05-09 |
43103 | 트래픽많으면 인터넷선 끊나요.? [7] | 펔탄 | 2840 | 05-11 |
43102 | 부팅시디 만들기 힘드네요 [3] |
|
2840 | 10-15 |
43101 | 김용환님 글... [8] | ... | 2840 | 01-02 |
43100 | WD A/S ㅠ.ㅠ [2] | 직장인 | 2839 | 02-13 |
43099 | 이번에 윈도우7 64비트 깔았네요. [6] | 위두리 | 2839 | 05-16 |
43098 | 바탕화면에서 마우스 오른쪽 버튼에 cmd 명령 추가 [4] | 꼬망꼬망 | 2839 | 03-10 |
43097 | 조금 신기한사이트 [17] | 비오는날 | 2839 | 03-28 |
43096 | 요즘 누가 그냥 윈도우10 까냐? 게이밍 전용 윈도우10 나왔... [16] | 와로 | 2838 | 02-06 |
43095 | 모니터 HDMI 연결 사용자분.... [9] | 알미뜽 | 2838 | 03-07 |
43094 | 비대칭 인터넷 정말 불편하네요.. [8] |
|
2838 | 06-23 |
43093 | SSD 쓰시는분들 슈퍼패치(프리패치) 끄시나요? [16] | 윈라 | 2837 | 05-11 |
43092 | 공무원들의 복지부동한 태도에 미치겠군요... [5] | 라이타 | 2837 | 05-10 |
43091 | ...지마켓 신용카드결제안되네요 ㅠㅠ [8] |
|
2837 | 07-23 |
43090 | 사블오디지 LS 윈도8 드라이버 깔리네요 [1] |
|
2836 | 10-07 |
43089 | 원도우8 탐색기 대체 프로그램 [10] |
|
2836 | 09-16 |
43088 | 해외에서도 난리네요 [5] | ojhcn | 2836 | 08-18 |
43087 | 하드디스크에 문제가 생겼었는데.... [6] | 포인트 | 2836 | 01-09 |
문제가 원래 그런건지, ton3d님이 줄여 쓰느라 잘못 쓴 것인지는 알 수 없지만,
'S의 길이 2k인 연속한 부분문자열이 앞 k개 문자가 모두 동일하고, 또한 뒤 k개 문자가 서로 동일하며, ' 부분과 뒤에 예시로 든
S = “0111000011”가 서로 오류입니다.
'k개 문자가 모두 동일해야 한다'면 2k인 s문자는 00001111, 111111000000 이런식이어야 하지 않나요?
그래서 문제가 맞고 예시가 틀렸다면, 어떤 문자열이 와도 이 문제는 1번만 제거가 이루어 집니다.
설명이 잘못된듯 합니다.
오류찾기가 생활화된 프로그래머는 이런 문제를 안냅니다.