자료구조 해시

프로그래머스 문제중 BestElbum 풀이과정.

일단 가장 먼저 어떻게 구상할지 생각하고 설계하였다.
가장 먼저 떠오른 것은 map을 이용해 자료를 정리하는 것이라 생각했고
즉시 코드를 쓰기 시작했다.

첫번째 코드

가장많이 들은 장르 도출

---

그렇게 해서 map을 이용해 가장 많이 들은 장르를 도출해내기까지 구현하였다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <numeric>
using namespace std;
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> m;
    vector<string>::iterator iter;
    int tmp;
    for (iter = genres.begin(); iter != genres.end(); iter++) {
        if (m.find(*iter) != m.end()) {
            tmp = m.find(*iter)->second;
            tmp += plays[iter - genres.begin()];
            m.erase(*iter);
            m.insert({ *iter, tmp});
        }
        else
            m.insert({ *iter, plays[iter - genres.begin()] });
    }
    int firstnum=0, secondnum = 0;
    string firstname, secondname;
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        if (firstnum < iter->second) {
            secondnum = firstnum;
            secondname = firstname;
            firstnum = iter->second;
            firstname = iter->first;
        }
        else if (secondnum < iter->second) {
            secondnum = iter->second;
            secondname = iter->first;
        }
    }
    cout << "제일 많은 장르 : " <<  firstname << "\n두번쨰로 많은 장르 : "<< secondname << endl;
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        cout << "key : " << iter->first << " value : " << iter->second << '\n';
    }
    return answer;
}

출력결과

원하는 결과대로 나오는 것을 확인 후, 이제 제일 많은 장르에서 제일 많이 재생된 음악 번호를 찾으려고 하는데 너무 비효율 적이라는 생각이 들었다.

그래서 구상한 것이 map을 map<stirng,vector>로 선언하면 되지 않을까 란 생각과 함께 즉시 코드를 구현하기 시작했다.

그렇게 완성한 코드

map<string,vector>사용

  #include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <numeric>
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, vector<int>> m;
    vector<string>::iterator iter;
    int tmp;
    for (iter = genres.begin(); iter != genres.end(); iter++) {
        if (m.find(*iter) != m.end()) {
            m.find(*iter)->second.push_back(plays[iter - genres.begin()]);
        }
        else {
            vector<int> tmpvec;
            tmpvec.push_back(plays[iter - genres.begin()]);
            m.insert({ *iter,tmpvec});
        }
    }
    int firstnum=0, secondnum = 0;
    string firstname, secondname;
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        int sum = accumulate(iter->second.begin(), iter->second.end(), 0);

        if (firstnum < sum) {
            secondnum = firstnum;
            secondname = firstname;
            firstnum = sum;
            firstname = iter->first;
        }
        else if (secondnum < sum) {
            secondnum = sum;
            secondname = iter->first;
        }
    }
    //cout << "제일 많은 장르 : " <<  firstname << "\n두번쨰로 많은 장르 : "<< secondname << endl;
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        sort(iter->second.begin(), iter->second.end(),greater<int>()); // vector sorting
    }
    auto it = find(plays.begin(), plays.end(), m.find(firstname)->second[0]);
    answer.push_back(it -plays.begin());
    it = find(plays.begin(), plays.end(), m.find(firstname)->second[1]);
    answer.push_back(it - plays.begin());
    
    auto ite = find(plays.begin(), plays.end(), m.find(secondname)->second[0]);
    answer.push_back(ite - plays.begin());
    ite = find(plays.begin(), plays.end(), m.find(secondname)->second[1]);
    answer.push_back(ite - plays.begin());

    return answer;
}

출력 결과

예시 결과대로 잘 나오는 것을 확인할 수 있다.

---

예외처리

여기서 할 것은
예외처리인데
한 장르에 곡이 2곡이상 없을 경우 예외처리를 해주어야한다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <numeric>
vector<int> solution(vector<string> genres, vector<int> plays) {
  vector<int> answer;
  map<string, vector<int>> m;
  vector<string>::iterator iter;
  int tmp;
  for (iter = genres.begin(); iter != genres.end(); iter++) {
      if (m.find(*iter) != m.end()) {
          m.find(*iter)->second.push_back(plays[iter - genres.begin()]);
      }
      else {
          vector<int> tmpvec;
          tmpvec.push_back(plays[iter - genres.begin()]);
          m.insert({ *iter,tmpvec});
      }
  }
  int firstnum=0, secondnum = 0;
  string firstname, secondname;
  for (auto iter = m.begin(); iter != m.end(); iter++) {
      int sum = accumulate(iter->second.begin(), iter->second.end(), 0);

      if (firstnum < sum) {
          secondnum = firstnum;
          secondname = firstname;
          firstnum = sum;
          firstname = iter->first;
      }
      else if (secondnum < sum) {
          secondnum = sum;
          secondname = iter->first;
      }
  }
  //cout << "제일 많은 장르 : " <<  firstname << "\n두번쨰로 많은 장르 : "<< secondname << endl;
  for (auto iter = m.begin(); iter != m.end(); iter++) {
      sort(iter->second.begin(), iter->second.end(),greater<int>()); // vector sorting
  }

  if (m.size() == 1) {
      if (m.find(firstname)->second.size() == 1) {
          auto it = find(plays.begin(), plays.end(), m.find(firstname)->second[0]);
          answer.push_back(it - plays.begin());
      }
      else {
          auto it = find(plays.begin(), plays.end(), m.find(firstname)->second[0]);
          answer.push_back(it - plays.begin());
          it = find(plays.begin(), plays.end(), m.find(firstname)->second[1]);
          answer.push_back(it - plays.begin());
      }
  }
  else {
      auto it = find(plays.begin(), plays.end(), m.find(firstname)->second[0]);
      answer.push_back(it - plays.begin());
      it = find(plays.begin(), plays.end(), m.find(firstname)->second[1]);
      answer.push_back(it - plays.begin());

      auto ite = find(plays.begin(), plays.end(), m.find(secondname)->second[0]);
      answer.push_back(ite - plays.begin());
      ite = find(plays.begin(), plays.end(), m.find(secondname)->second[1]);
      answer.push_back(ite - plays.begin());
  }
  return answer;
}

1차 코드 수정

하지만 문제가 있는데 문제를 잘못 읽어 재생된 횟수가 다 고유한 값인줄 알았으나
중복된 값도 가능하다는 사실을 알게 되고 다시 코드를 수정해야한다. ㅜㅜ

(헷갈리게 써져있긴 하다..)

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <numeric>
vector<int> solution(vector<string> genres, vector<int> plays) {
  vector<int> answer;
  map<string, vector<int>> m;
  map<int, int> number;
  vector<string>::iterator iter;
  int tmp;
  int i=0;
  for (iter = genres.begin(); iter != genres.end(); iter++ ,i++) {
      if (m.find(*iter) != m.end()) {
          m.find(*iter)->second.push_back(plays[iter - genres.begin()]*100 +i);
      }
      else {
          vector<int> tmpvec;
          tmpvec.push_back(plays[iter - genres.begin()]*100+i);
          m.insert({ *iter,tmpvec});
      }
  }
  int firstnum=0, secondnum = 0;
  string firstname, secondname;
  for (auto iter = m.begin(); iter != m.end(); iter++) {
      //int sum = accumulate(iter->second.begin(), iter->second.end(), 0);
      int sum=0;
      for (auto itr = iter->second.begin(); itr != iter->second.end(); itr++) {
          sum += *itr * 0.01;
      };

      if (firstnum < sum) {
          secondnum = firstnum;
          secondname = firstname;
          firstnum = sum;
          firstname = iter->first;
      }
      else if (secondnum < sum) {
          secondnum = sum;
          secondname = iter->first;
      }
  }
  //cout << "제일 많은 장르 : " <<  firstname << "\n두번쨰로 많은 장르 : "<< secondname << endl;
  for (auto iter = m.begin(); iter != m.end(); iter++) {
      for (int j = 0; j < iter->second.size() - 1; j++) {  // vector sorting
          for (int k = 0; k < iter->second.size() - 1; k++) {
              int num1 = (iter->second[k]) * 0.01;
              int num2 = iter->second[k + 1] * 0.01;
              if (num1 < num2)
              {
                  int temp = iter->second[k];
                  iter->second[k] = iter->second[k + 1];
                  iter->second[k + 1] = temp;
              }
          }
      }
      //sort(iter->second.begin(), iter->second.end() , greater<int>());
  }
  if (m.size() == 1) {
      if (m.find(firstname)->second.size() == 1) {
          //auto it = find(plays.begin(), plays.end(), m.find(firstname)->second[0]);
          answer.push_back(m.find(firstname)->second[0]%100);
      }
      else {
          //auto it = find(plays.begin(), plays.end(), m.find(firstname)->second[0]);
          answer.push_back(m.find(firstname)->second[0] % 100);
          //answer.push_back(it - plays.begin());
          //it = find(plays.begin(), plays.end(), m.find(firstname)->second[1]);
          answer.push_back(m.find(firstname)->second[1] % 100);
          //answer.push_back(it - plays.begin());
      }
  }
  else if(m.size() ==0) {
      
  }
  else
  {
      answer.push_back(m.find(firstname)->second[0] % 100);
      answer.push_back(m.find(firstname)->second[1] % 100);
      answer.push_back(m.find(secondname)->second[0] % 100);
      answer.push_back(m.find(secondname)->second[1] % 100);


      /*auto it = find(plays.begin(), plays.end(), m.find(firstname)->second[0]);
      answer.push_back(it - plays.begin());
      it = find(plays.begin(), plays.end(), m.find(firstname)->second[1]);
      answer.push_back(it - plays.begin());

      auto ite = find(plays.begin(), plays.end(), m.find(secondname)->second[0]);
      answer.push_back(ite - plays.begin());
      ite = find(plays.begin(), plays.end(), m.find(secondname)->second[1]);
      answer.push_back(ite - plays.begin());*/
  }
  return answer;
}

---

그렇게 다시 고쳐본 코드..
총 곡의 개수가 100개 미만이라고 했으므로
100을 해주고 고유값을 더해 마킹까지 같이해주고
넣을때는 0.01을 통해 노래의 고유번호를 도출해냈다..

문제에 제시된 예시와 ["pop","pop","pop], [1,1,1]은 예상대로 잘 나오는 상황인데
하지만 여전히 통과가 안되기 때문에 뭐가 문젠지를 계속 봐야겠다.

2차 수정한 코드..

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <numeric>
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
map<string, vector<int>> m;
map<int, int> number;
vector<string>::iterator iter;
int tmp;
int i=0;
for (iter = genres.begin(); iter != genres.end(); iter++ ,i++) {
  if (m.find(*iter) != m.end()) {
      m.find(*iter)->second.push_back(plays[iter - genres.begin()]*100 +i);
  }
  else {
      vector<int> tmpvec;
      tmpvec.push_back(plays[iter - genres.begin()]*100+i);
      m.insert({ *iter,tmpvec});
  }
}
int firstnum=0, secondnum = 0;
string firstname, secondname;
for (auto iter = m.begin(); iter != m.end(); iter++) {
  //int sum = accumulate(iter->second.begin(), iter->second.end(), 0);
  int sum=0;
  for (auto itr = iter->second.begin(); itr != iter->second.end(); itr++) {
      sum += *itr * 0.01;
  };

  if (firstnum < sum) {
      secondnum = firstnum;
      secondname = firstname;
      firstnum = sum;
      firstname = iter->first;
  }
  else if (secondnum < sum) {
      secondnum = sum;
      secondname = iter->first;
  }
}
//cout << "제일 많은 장르 : " <<  firstname << "\n두번쨰로 많은 장르 : "<< secondname << endl;
for (auto iter = m.begin(); iter != m.end(); iter++) {
  for (int j = 0; j < iter->second.size() - 1; j++) {  // vector sorting
      for (int k = 0; k < iter->second.size() - 1; k++) {
          int num1 = (iter->second[k]) * 0.01;
          int num2 = iter->second[k + 1] * 0.01;
          if (num1 < num2)
          {
              int temp = iter->second[k];
              iter->second[k] = iter->second[k + 1];
              iter->second[k + 1] = temp;
          }
      }
  }
  //sort(iter->second.begin(), iter->second.end() , greater<int>());
}
if (m.size() == 1) {
  if (m.find(firstname)->second.size() == 1) {
      answer.push_back(m.find(firstname)->second[0]%100);
  }
  else {
      answer.push_back(m.find(firstname)->second[0] % 100);
      answer.push_back(m.find(firstname)->second[1] % 100);
  }
}
else if(m.size() ==0) {
}
else
{
  if (m.find(firstname)->second.size() == 1) {
      answer.push_back(m.find(firstname)->second[0] % 100);
  }
  else {
      answer.push_back(m.find(firstname)->second[0] % 100);
      answer.push_back(m.find(firstname)->second[1] % 100);
  }
  if (m.find(secondname)->second.size() == 1) {
      answer.push_back(m.find(secondname)->second[0] % 100);
  }
  else {
      answer.push_back(m.find(secondname)->second[0] % 100);
      answer.push_back(m.find(secondname)->second[1] % 100);
  }
}
return answer;
}

마지막에 어긋나게 있던 코드도 다시 한 번 고쳤다.. 근데 아직도.. 통과가 안돼서 계속 생각해봐야겠다..

3차 수정 코드

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <numeric>
vector<int> solution(vector<string> genres, vector<int> plays) {
  vector<int> answer;
  map<string, vector<int>> m;
  map<int, int> number;
  vector<string>::iterator iter;
  int tmp;
  int i=0;
  for (iter = genres.begin(); iter != genres.end(); iter++ ,i++) {
      if (m.find(*iter) != m.end()) {
          m.find(*iter)->second.push_back(plays[iter - genres.begin()]*100 +i);
      }
      else {
          vector<int> tmpvec;
          tmpvec.push_back(plays[iter - genres.begin()]*100+i);
          m.insert({ *iter,tmpvec});
      }
  }
  int firstnum = 0, secondnum = 0;
  map<int, string, greater<int>> hashnum;
  string firstname, secondname;
  for (auto iter = m.begin(); iter != m.end(); iter++) {
      int sum=0;
      for (auto itr = iter->second.begin(); itr != iter->second.end(); itr++) {
          sum += *itr * 0.01;
      };
      hashnum.insert({ sum, iter->first });
      
  }
  
  for (auto iter = m.begin(); iter != m.end(); iter++) {
      for (int j = 0; j < iter->second.size() - 1; j++) {  // vector sorting
          for (int k = 0; k < iter->second.size() - 1; k++) {
              int num1 = (iter->second[k]) * 0.01;
              int num2 = iter->second[k + 1] * 0.01;
              if (num1 < num2)
              {
                  int temp = iter->second[k];
                  iter->second[k] = iter->second[k + 1];
                  iter->second[k + 1] = temp;
              }
          }
      }
  }
  for (auto iter = hashnum.begin(); iter != hashnum.end(); iter++) {
      if (m.find(iter->second)->second.size() == 1) {
          answer.push_back(m.find(iter->second)->second[0] % 100);
      }
      else {
          answer.push_back(m.find(iter->second)->second[0] % 100);
          answer.push_back(m.find(iter->second)->second[1] % 100);
      }
  }


  return answer;
}

문제점

문제점을 찾았다.
왜 통과가 안되지 하고 이것저것 찾아보다 원인을 찾았다.
그 이유는 내가 문제를 잘못 이해했기 때문이다.

내가 이해한 것은 상위 2개 장르에 있는 상위2개 노래를 담는 것이였는데
문제는 장르별 상위 2개 노래를 담는 것이였다. 그래서 hash를 하나 더 만들어 사용했고,

코드를 수정해 주었다.

후기

오늘 하루종일 이것만 매달렸는데 해결해서 넘넘 좋다.
앞으로 더 열심히 하게 될 것 같다.
근데 문제 설명이 조금 더 구체적이면 좋을 것 같다.