인프런 커뮤니티 질문&답변
작성한 질문수
2-F 질문드립니다.
해결된 질문
작성
·
303
·
수정됨
1
안녕하세요.
문제풀이중 궁금한 사항 있어 질문드립니다.
http://boj.kr/9422ef61745946c8873cbec2ec8a10ef
해당코드에서
if(find(arr.begin(),arr.end(),first)<find(arr.begin(),arr.end(),second))
이 부분이 sort로 정렬 중인 함수의 순서를 참조해서 틀렸다는 것은 인지했습니다.
순서를 참조 할수 있는 새 벡터를 만들어 문제는 해결하였지만 해당 코드로 인해 틀린케이스가 머리속으로 그려지지 않는데 어떤 케이스에서 오답을 나타나는지 알 수 있을까요?
답변 1
0
안녕하세요 인수님. ㅎㅎ
음... 인수님의 다음 코드 설명 더 부탁드려도 될까요?
ex) 왜 이렇게 코드를 구축하신건지, 이렇게 하면 좋은 점. 등이요.
제가 이 질문을 드리는 것은 보통의 sort의 comparator부분에 find를 쓰는 것은 처음 봐서.. 혹시 이유가 있나해서요.
sort(arr.begin(),arr.end(),[](long long int first, long long int second ){
if (mp[first]==mp[second])
return find(arr.begin(),arr.end(),first)<find(arr.begin(),arr.end(),second);
return mp[first]>mp[second];
});그렇군요.. ㅎㅎ 답변드리자면 다음과 같아요.
find는 정수를 반환할까요? 아닙니다. find는 이터레이터를 반환합니다. 근데 그 이터레이터를 기반으로 대소비교를 한다? 첫번째 틀린점입니다.
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}그리고 지금 보면 first와 second가 같은 값이 들어올 때에 대한 대소비교로직이 없어요. first와 second가 같게 들어오면 당연히 mp[first]와 mp[second]도 같고. find도 같은 값을 가질텐데 거기에 대한 로직이 없습니다. 두번째 틀린점입니다.
이러한 점들 때문에 틀린 것 같아요.
감사합니다.
http://boj.kr/b674d35824cc4d72b4428d23da205da4
같은 로직으로 find내 벡터만 변경하였고 정답으로 인정된 코드입니다.
이터레이터를 반환한다 해도 결국 벡터는 배열과 같이 주소가 순차되로 증가되기때문에 무리가 없다 생각했습니다.
find값이 같을때는 어차피 같은 실제 가지고 있는 값이 동일하니까 순서를 변경할 필요가 없지 않나요?
추가적으로 제가 최근에 공부한 자료구조 책 에서 for(auto i = v.begin() ;i<v.end(), i++){} 와 같이 이터레이트의 대소를 비교해서 구현하는 코드들이 종종 보였는데 이렇게는 많이 쓰이지 않는 방식인가요?
이터레이터를 반환한다 해도 결국 벡터는 배열과 같이 주소가 순차되로 증가되기때문에 무리가 없다 생각했습니다.
>> 저 제출을 해서 맞았다 한들, 로직이 틀렸다면 나중에 이 코드는 틀릴 확률이 높은 코드에요. 결국 주소값으로 대소비교를 하는건데 왜 주소값을 기반으로 대소 비교를 해야 하죠? 주소값은 0bba이 나올 수도 있고 baa00 이렇게 나올 수도 있습니다. 순차적인 것도 알지만.. 그러한 값들은 예상 불가능한 값들이고 이 불가능한 값들을 기반으로 대소비교를 하는 것은 옳지 않고 주소값을 기반으로 일반적으로 대소비교를 하지는 않습니다.
만약, 저렇게 할거라면 이터레이터를 기반으로 int형 index를 반환하게 해서 하시면 됩니다.
해당 부분은 교안 내의 lower_bound() 와 upper_bound() 를 참고하시면 됩니다 :)
이터레이트의 대소를 비교해서 구현하는 코드
>> 저 코드는 이터레이터 대소비교하는 코드가 아닙니다. i++ 에요.
v.end()는 의미있는 이터레이트를 반환하지 않기 때문에 위 예시는 틀린게 맞는 것 같습니다.
하지만 v.begin()은 int형 index가 아닌 이터레이트를 반환합니다. 그래서 자료형 선언을 int 가아닌 auto로 하였습니다. 아래 레퍼런스 드립니다.
vector begin()/end() reference
https://cplusplus.com/reference/vector/vector/begin/
Iterator도 대소비교가 가능합니다.(포인터 처럼 활용가능)
이터레이터 valid expressions reference
https://cplusplus.com/reference/iterator/
제가 작성한 코드가 비효율적이고 접근방식이 다른 것은 인지하고 있습니다.
코드의 옳음을떠나 제가 처음 작성한 코드에서 틀린케이스를 찾는데 힘이들어 조언을 구하고 싶었는데 나중에 시간날때 따로 디버깅 해보겠습니다. ㅎㅎ
감사합니다.
첨언을 하자면요.
인수님의 코드는 맞을 수 있는 코드에요. 다만, 주소값을 기반으로 대소비교를 하고 그걸 기반으로 어떤 요소가 앞에 있고. 뒤에 있고를 판단한다는 것은 주소값이라는 요소가 영향을 끼치기 때문에 "틀릴 수 있는" 코드가 된다는 거에요. 대소비교도 되고 저게 순차적이니까 대부분은 맞겠죠. 그러나 주소값이라는 것이 OS 기반으로 산정되기때문에 어떤 환경에서는 분명히 틀리는 경우가 발생이 됩니다. 그렇기 때문에 주소값이 아니라.
하실거면
int f = (int)(lower_bound(v.begin(),v.end(),x) - v.begin());앞의 코드처럼 (lower_bound 설명에서 나옵니다.) 이터레이터를 int로 변환해서 해야 해요. ㅎㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
감사합니다.
강사 큰돌 올림.
find() 함수의 특성이 해당 원소의 가장 첫번째 인자의 주소를 찾아 주는 특징이 있기때문에 각 주소의 크기를 비교한다면 따로 순서를 저장하는 배열을 만들지 않아도 가장 먼저들어온 숫자의 순서를 알 수 있다는 아이디어로 find()함수를 사용하였습니다.
실제로 해당 코드에서 arr벡터와 똑같은 벡터 arr2를 만들어 활용하면 정답이 뜨긴 했지만 기존에 작성했던 코드도 백준에 있는 샘플 입/출력은 다 만족하는 상황이였기 때문에 어떠한 경우에 오답이 발생한 건지 궁금하여서 질문드렸습니다!