오늘 할일
1. LeetCode
2. 창엔준비
3. 영상처리 자료파일 다운로드
4. Software Engineering과제 제출
- 챙 선물, 커피
오늘 한일
1. LeetCode
- 코드 깃허브 업로드
- Dota2 Senate는 Senator라는 인물들이 턴제로 게임을 진행하는 것인데, 매 라운드마다 senator는 한명의 투표 권한을 앗아가거나, 모든 senator를 찾아내어 승리를 공표할 수 있다. 모든 사람이 똑똑할 때 승자를 예측하는 문제이다.
/*
Radiant와 Dire라는 두개의 파티가 존재한다. 파티의 변화를 위한 투표는 공정하게 진행될 것이다.
매 라운드마다 각각의 senator는 두가지 중 하나만을 설명할 수 있다.
1. Ban one senator's right: 한명의 senator는 다른 한명의 senator가 앞으로의 모든 라운드에 모든 권한을 잃게한다
2. Announce the victory: 만약 senator가 같은 파티안의 투표가능한 senator들을 모두 찾아낸다면, 그는 승리를 알리고 게임의 변화를 결정할 수 있다.
주어지는 단어는 각 senator들이 속해진 파티 이름(Radiant, Dire)이다. n명의 senator들이 있다.
라운드는 첫번째 senator부터 마지막 senator까지 주어진 순서에 따라 시작된다. 투표가 끝날 때 까지 계속된다
자신의 권한을 상실한 모든 senator는 해당 턴을 스킵한다.
모든 senator들은 그의 파티 내에서 최고의 전략을 가지고 게임에 임할 것이고 충분히 똑똑하다.
최종적으로 어떤 팀이 승리할 것인지를 예측하라. 리턴값은 Radiant 혹은 Dire뿐이다.
*/우선 RR과 DD의 count를 비교하여 결과를 도출하는 가장 간단한 방법으로 접근해보았다. 이 때 먼저 시작한 사람은 다른 사람의 권한을 먼저 앗아갈 수 있기에 두개의 등장횟수가 같을 경우 먼저 시작한 팀이 이기게끔 작성해보았다.
class Solution {
public String predictPartyVictory(String senate) {
int rad_count=0, dire_count=0;
String result="Dire";
for(char c: senate.toCharArray()){
if(c=='R')
rad_count++;
else
dire_count++;
}
if(rad_count>dire_count) {
result = "Radiant";
} else if(rad_count==dire_count){
result= senate.charAt(0)=='R'?"Radiant":"Dire";
}
return result;
}
}
70개의 테스트를 통과하였다.
시작한사람에게 advantage주는 방식을 직접적으로 count를 ++해주는 방식으로 바꾸어 보았다.
class Solution {
public String predictPartyVictory(String senate) {
/*
Radiant와 Dire라는 두개의 파티가 존재한다. 파티의 변화를 위한 투표는 공정하게 진행될 것이다.
매 라운드마다 각각의 senator는 두가지 중 하나만을 설명할 수 있다.
1. Ban one senator's right: 한명의 senator는 다른 한명의 senator가 앞으로의 모든 라운드에 모든 권한을 잃게한다
2. Announce the victory: 만약 senator가 같은 파티안의 투표가능한 senator들을 모두 찾아낸다면, 그는 승리를 알리고 게임의 변화를 결정할 수 있다.
주어지는 단어는 각 senator들이 속해진 파티 이름(Radiant, Dire)이다. n명의 senator들이 있다.
라운드는 첫번째 senator부터 마지막 senator까지 주어진 순서에 따라 시작된다. 투표가 끝날 때 까지 계속된다
자신의 권한을 상실한 모든 senator는 해당 턴을 스킵한다.
모든 senator들은 그의 파티 내에서 최고의 전략을 가지고 게임에 임할 것이고 충분히 똑똑하다.
최종적으로 어떤 팀이 승리할 것인지를 예측하라. 리턴값은 Radiant 혹은 Dire뿐이다.
*/
int rad_count=0, dire_count=0;
String result="Dire";
for(char c: senate.toCharArray()){
if(c=='R')
rad_count++;
else
dire_count++;
}
if(senate.charAt(0)=='R')
rad_count++;
else
dire_count++;
if(rad_count>dire_count) {
result = "Radiant";
}
return result;
}
}
72까지의 테스트 케이스를 통과하였는데, 이제 진짜로 알고리즘을 이해 후 접근해봐야 할 듯 하다. 가장 간단한 방법의 구상으로는 모든 테스트 케이스를 통과하지 못했다.
다음으로는 테스트 코드를 이용해 문제를 이해해보려했는데, RDD에서 D가 이기는 로직을 잘 모르겠다. R이 D1을 ban, D2가 R을 ban한 것 까지는 이해가 되는데 round 2에서 D2가 갑자기 승리를 공표한다. 문제의 공표에 대한 설명은 다음과 같다. Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game. 여기서 공표하기위한 조건이 이 senator가 같은 파티(Dire or Radiant)내에 투표할 수 있는 권한을 가진 사람들을 모드 찾아내는 것 인데... 자기 밖에 없어지는 순간을 말하는 걸까? 아니라고 생각하는데 그 이유는 다음 테스트케이스인 DDRRR에서 Dire이 이겼다는 것이다. DD가 RR을 막으면 마지막 R은 자기 팀 내에 투표할 수 있는 사람이 마찬가지로 자기밖에 없기에 Radiant가 이겨야 했을 것이다.
과연 RDD_Dire승, DDRRR_Dire승은 어떤 규칙에 의해 결정된 것일까? 어떻게 이해하면 좋을까?
규칙을 다시 읽어보니 ban이 영구정지로 권한이 다시 생기는 게 아닌 것 같다.
그렇다면 RDD에서 R이 D1을 영구정지, D1이 R을 영구정지하여 D2가 승리를 공표한 것으로 설명이 가능하다.
다음 케이스를 보자. DDRRR은 D1이 R1을 ban, D2가 R2를 ban, R1&R2패스 R1은 D1을 ban하여 1라운드는 비기게 된다. 이때 D가 승리를 공표할 수 있다. 투표할 수 있는 사람이 자기밖에 없기에.
다음 케이스를 보자. DRDRR은 D1이 R1을 정지, D2가 R2를 정지, R3는 D1을 정지. D2는 라운드 2에서 승리를 공표할 수 있다. 하지만 이 케이스의 답은 Radiant이다. 대체 어떻게 이해해야하는 것인가...어라?? 테스트케이스를 잘못 입력했다ㅋㅋㅋ Dire승리 맞다.
위의 로직대로 코드를 재구성해보자. 근데 이 규칙을 코드로 구현하기 너무 귀찮다. 수학적으로 해겷할 수 있는 방법이 없을까?
현재 등장수도 등장수지만 순서의 영향을 어떻게 해야 쌈뽕하게 빠를지 고민중이다.
다음으로 밴을 하면 문자열에서 아예 지우는 방법을 선택해봤는데,
