chobochobo
214
2019-03-03 00:56:50 작성 2019-03-03 01:10:11 수정됨
6
657

카카오 문제 사이트에 나온건데 이거 왜 틀린걸까요?


https://programmers.co.kr/learn/courses/30/lessons/12912



두 정수 a,b가 주어지면 두 수 사이에 있는 모든 정수의 합을 구하는 문제입니다


가령 2,5가 주어지면


2+3+4+5=14 로


14를 반환하는 함수를 짜야하는 문제이지요


그래서 저는 "가우스의 덧셈"의 풀이 방법과 유사한 발상을 통해서


정답 = ((a+b)/2)*(abs(a-b)+1);


을 구하는 코드를 작성했습니다.





#include <string>

#include <cmath>


using namespace std;


long long solution(int a, int b) {

    long long answer;

     

   

    

    long long first = (long long)a;

    long long last = (long long)b;

    

    answer = ((first+last)/2)*(abs(first-last)+1);

    

    

    return answer;

}





그런데 홈페이지에서는 일부 케이스에 대해서 오답이라고 나오더라구요


다른사람들이 푼 문제랑 비교해보니까 시간이 초과되서 생긴 문제인듯한데


다른사람들의 풀이는 반복문을 통해서 a부터 b사이의 값을 모두 다 더하는 방식으로 풀었더라구요





a와 b의 자료형은 무조건 int로 고정해야 하구요


a,b를 그대로 연산에 쓰면 오버플로우가 발생하는건가 싶어서


first 와 last라는 long long 타입의 임시변수를 만들어서 연산해도 마찬가지로 오답이 나오네요...





오답나온 테스트 케이스들의 시간이 다 0ms를 넘는걸로 봐선


시간이 0ms 여야 정답이 되는듯한데


빅오 표기법으로 해보아도


제가 사용한 방법은 O(1) 인데


반복문을 쓰면 O(n) 이 되야 하는거 아닌가요??


아니면 long long 자료형의 곱셈시 연산속도가 그만큼 느리기 때문인건가요...??

 
0
0
  • 답변 6

  • 엡실론
    725
    2019-03-03 01:37:18

    시간초과가 문제가 아닙니다.
    a =2, b = 5 테스트 해보세요.

    0
  • 초무쿤
    3k
    2019-03-03 01:40:39

    전 그냥 이렇게 해버렸는데. 너무 무식한 방법가요.ㅎㅎ;


    class Solution {
      public long solution(int a, int b) {
          long answer = 0;
          int from = Math.min(a,b);
          int to = Math.max(a,b);
          for(int i = from; i <= to; i ++){
             answer += i;
          }
          return answer;
      }
    }


    0
  • Hyperglide
    392
    2019-03-03 01:43:07

    해당 사이트에서 '실패'라고 나오는 것은, 해당 케이스가 제시한 답을 맞추지 못해서 틀렸다고 알려주는 것이구요.


    시간을 초과해서 통과못했으면 '시간초과'라고 나옵니다. 따라서 실패라고 나오셨다면 시간 초과가 아니라 그냥 케이스를 못맞추셨다고 보면 되어요.


    지금 작성하신 코드 제가 돌려보니까 통과 못하는 케이스가 명확하게 나와서, 한개 적어드릴게요! 한번 이걸로 돌려보시고 무엇이 잘못되었는지 고민해보심 좋을 것 같습니다.


    a 1 b 100 -> 정답 5050

    0
  • Honowis
    354
    2019-03-03 01:46:05 작성 2019-03-03 02:02:10 수정됨

    함수는 맞습니다. 그런데 작성하신 코드 퍼포먼스가 원하는 만큼 나오질 않아서 그럴거에요.

    우선 /2 를 뒤로 보내 float * int 곱을 방지하시고,  절대값을 구할 때 long 형 을 사용 하는 labs 을 사용 하셔요 :)

    long long solution(int a, int b) {
        return (a+b)*(labs(a-b)+1)/2;
    }
    1
  • Hyperglide
    392
    2019-03-03 02:10:56

    Honowis

    사실 이 분 코드는 퍼포먼스 문제가 전혀 아니고, /2를 넣는 위치가 잘못되어서 오답이 나오는거라고 볼 수 있죠...

    ((a+b)/2) 를 해버리면 a랑 b의 합이 홀수인 케이스에서는 /2를 하는 순간 0.5가 절삭이 될테니까요.

    1
  • Honowis
    354
    2019-03-03 02:43:37

    @hyperglide 아 그렇네요 float 아니라는 걸 간과하고 있었습니다. 

    헌데 2 나눔을 마지막으로 해도 abs 를 사용하면 여전히 테스트를 통과 못 하는 점을 보아 두가지 문제가 섞여 버린 듯 합니다. 

    0
  • 로그인을 하시면 답변을 등록할 수 있습니다.