| [ QuizWit ] in KIDS 글 쓴 이(By): fenris (늑대) 날 짜 (Date): 2000년 9월 25일 월요일 오후 10시 08분 29초 제 목(Title): Re: 이건 과제물인데.. 풀어보세요. mkjung님이 올리신 답은 잘못된 것 같네요. 그런식으로는 majority를 구할 수 없는거 같은데요.. 예를들어 aaaabbbbccccdddd..... 식으로 된것은 aaaaaaaaaa... 식으로 모든 원소가 같은경우와 동일한 결과를 가져 오게 되잖아요. 모두 true로.. 그리고 이곳에 과제물을 올리는 것은 문제가 있겠네요.. 죄송합니다. 그래도 혹시 제 문제를 생각해 본 분도 있을지 모르니 제가 알고 있는 답을 올립니다. 게시물은 내일 삭제하지요. =============================== 만일 원소가 abccdcdaaa 식으로 된 것이 있다면 우선 첫번째 원소인 a를 기준으로 같은지의 여부를 따집니다. 같으면 +1, 다르면 -1을 매깁니다. 위의 원소의 경우는 처음에 a니까 +1이고 두번째는 다르니까 -1 입니다. 그럼 지금까지 나온 숫자의 합이 0이 됩니다. 0이 되면 지금까지 나온 것은 무시하고 같은 방법을 다시 적용합니다. 두번째 까지 따져 보았으니까 세번째 원소인 c가 다시 기준이 됩니다. 세번째가 c이므로 +1, 네번째도 c이니까 +1, 다섯번째는 다르므로 -1, 여섯번째는 같으므로 +1, 일곱번째는 -1, 여덟번째는 -1, 이제 다시 숫 자의 합이 0입니다. 그러면 아홉번째를 기준으로 다시합니다. 그러면 +1, +1로 끝까지 왔습니다. 이 결과가 +인 값이 나온다면 이것은 majority가 될 가능성이 있는 것입니다. 현재는 +이므로 현재 기준으로 잡고 있는 a가 majority element인지를 다시 비교하면서 확인합니다. 결과값이 - 이거나 0이면 majority는 존재하지 않는다고 볼수 있습니다. 이와 같은 방법으로 비교를 하면 처음에 계산하면서 비교할때, n-1번의 비교가 필요하고 끝에 비교된 수가 majority인지의 여부를 알아보기 위해 n번 비교하여, 최악의 경우도 2n-1번으로 알아낼 수 있습니다. |