Single number

woori·2022년 11월 29일
0

leetcode_study

목록 보기
3/4

문제 내용 :
1차원 배열이 주어지고, 그 안의 numbere들은 1개를 제외하고 모두 2개씩 들어있다. 주어진 배열에서 1개만 있는 값을 리턴한다.

ex) [1,2,2,3,3][4,1,2,3,2,3,1]

문제 해결 :
두 가지방식으로 진행하였는데

1) 일단 1차원배열을 정렬 한번하고 빈 벡터 v를 하나 생성, nums 크기만큼 for문을 돌면서 v 벡터에 값을 넣어주는데, 마지막 요소와 값이 같으면 v 벡터에 저장된 요소를 삭제해준다. 마지막에 남은 요소는 1개짜리 일테니 v 벡터 0번지 값을 리턴

2) 빈벡터 하나 생성하고, nums 크기만큼 반복문을 돌면서 값을 하나 insert 할 때마다 같은값이 있는지 검사하고, 같은게 있는 경우 그 요소를 삭제하면서 추가한다.

1번, 2번 방식 두가지로 풀어봤는데 2번 방식은 accept는 되지만 속도가 느린듯.. result 다른사람과의 비교 그래프상에 표시도 안된다

1번 방식은 그나마 result 그래프상 표시되지만 중간보다 저 뒤쯤? solution을 안보고 푸니 속도가 아쉽다.

제출코드 (1번 방식 ) :

class Solution {
public:
   int singleNumber(vector<int>& nums) {

       sort(nums.begin(), nums.end());
       vector<int> v;
       v.insert(v.end(), nums[0]);
       
       cout << v[0] << endl;
       
       for(int i=1; i<nums.size(); i++) {
           //cout << "i count " << i << "nums size " << nums.size() << endl;
           
           if( v.empty() ) {
               //cout << "insert empty" << nums[i] << endl;
               v.insert(v.end(), nums[i]);
           } else {
             if( v.back() == nums[i] ) {
               // 삭제
               //cout << "erase item " << v.back() << ", " << nums[i] << endl;
               v.erase(v.end()-1);
             } else {
                 //cout << "insert " << endl;
                  v.insert(v.end(), nums[i]);
             }
           }

           
           //cout <<  v[0] << endl;
       }
       
       return v[0];
       
   }
};

profile
기록하는개발자

0개의 댓글