왜 TLE가 나올까요..?;;

  • freedomJ
    freedomJ

    그리고 한가지 더 질문합니다.
    이건 다른문제인데요..
    문제 : http://goo.gl/gs8Z3
    여러 명령중에 'F' operation에 대한 색체우기구현 입니다.
    아래 함수에서 TLE가 발생합니다. ( 답답해서 주석처리하면서 찾아봤습니다 -ㅁ-;;)
    처음엔 재귀함수로 짰다가.. Stack Overflow가 떠서...;; Iteration으로 고쳤습니다.
    Stack 썼다가 push, pop연산이 많아서 TLE인줄알고, Array로 바꿨습니다만... 그래도 TLE가 뜨네요;; 음... 스택을 쓸때는 Input MAX값을 줘도 0.5초정도 걸리는 듯했습니다. 배열로 바꾸니 체감시간으로 못잴 정도로 빨라졌는데도 TLE가 뜹니다; ㄷㄷ;
    배열 크기는 전역에 충분히 큰 크기로 선언하였습니다. (65000개)

    #include<iostream>
#include<string>
using namespace std;

void fillxy(int, int, char, char);

typedef struct Point
{
    int col;
    int row;
}Point;

int m, n;
string name;
Point arr[65000];
char cmd;
char bitmap[251][251]={};

int main()
{

    while(cin>>cmd)
    {
        if(cmd=='X' ) 
        {
            break;
        }
        // m, n을 새로 받아서 알파벳 O로 채움
        else if(cmd=='I' ) 
        {
            cin >> m >> n;
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                    bitmap[i][j]='O';
        }
        // 기존 m, n으로 bitmap을 O로 초기화
        else if(cmd=='C' ) 
        {
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                    bitmap[i][j]='O';
        }
        // x,y 좌표를 받아서 그곳을 c로 채움
        else if(cmd=='L' )
        {
            int x, y;
            char c;
            cin >> x >> y >> c;
            bitmap[y][x] = c;
        }
        // 좌표를 받아서 가로로 채우기(y including)
        else if(cmd=='V')
        {
            int x, y1, y2;
            char c;
            cin >> x >> y1 >> y2;
            cin >> c;
            for(int i=y1; i<=y2; i++)
                bitmap[i][x]=c;
        }
        // 좌표를 받아서 세로 채우기(x including)
        else if(cmd=='H' )
        {
            int x1, x2, y;
            char c;
            cin >> x1 >> x2 >> y;
            cin >> c;
            for(int i=x1; i<=x2; i++)
                bitmap[y][i]=c;
        }
        // 두 좌표를 받아서 사각형채우기(including)
        else if(cmd=='K' )
        {
            int x1, y1, x2, y2;
            char c;
            cin >> x1 >> y1 >> x2 >> y2;
            cin >> c;
            for(int i=y1; i<=y2; i++)
                for(int j=x1; j<=x2; j++)
                    bitmap[i][j]=c;
        }
        // fill operation
        else if(cmd=='F' )
        {
            int x, y;
            char c;
            cin >> x >> y >> c;
            fillxy(x, y, bitmap[y][x], c);
        }
        // naming & print
        else if(cmd=='S' )
        {
            cin >> name;
            cout << name << endl;
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=m; j++)
                    cout << bitmap[i][j];
                cout << endl;
            }
        }

    }
    return 0;
}
void fillxy(int x, int y, char original, char newColor)
{
    int k=0;
    Point tmp={y, x};
    arr[k++] = tmp;
    do
    {
        tmp = arr[--k];
        y = tmp.col;
        x = tmp.row;
        bitmap[y][x] = newColor;

        if( bitmap[y][x+1]== original && x<m) 
        {
            Point tmp={y, x+1};
            arr[k++]=tmp;
        }
        if( bitmap[y+1][x]== original && y<n) 
        {
            Point tmp={y+1, x};
            arr[k++]=tmp;
        }
        if( bitmap[y][x-1]== original && x>1) 
        {
            Point tmp={y, x-1};
            arr[k++]=tmp;
        }
        if( bitmap[y-1][x]== original && y>1) 
        {
            Point tmp={y-1, x};
            arr[k++]=tmp;
        }
    }while(k>0);
}

    해결된 문제를 뒤로 뺐습니다.;;

    LCD Display
    문제 : http://goo.gl/fynA1
    (( 이 문제는 해결됬습니다 !! ^^ 도움주신 분들 감사합니다.!)

    왜 계속 WA가 뜨는지 도저히 모르겠습니다.
    (출력문제 인것같아 다음 사항은 이미 모두 체크해보았습니다.)

    • Minesweeper와 같은 한 줄 더 추가해서 문제가 생기는지 여부
    • 00000001234 input시 1234로 출력
    • 마지막 숫자 출력 후 1줄 띄워져 있는지 여부

    로직은 아래와 같습니다.
    1. 숫자를 string으로 받는다.
    2. 첫번째값이 0이고, 길이가 1이 아닌경우 첫번째 값을 pop()하는 작업을 while() loop로 돌린다. ( 숫자앞에 0 제거) ex> 000015를 15로 출력..
    3. 숫자가 필요한 size만큼 space를 채운다.( s+3열, 2s+3행 ) -> s+3열인 이유는 문자사이마다 1줄의 공백이 들어가기 때문이다. 그리고 마지막 문자의 경우는 s+2열만 space로 채워서 마지막 숫자 출력하고 공백1줄이 들어가지 않는다.
    4. 숫자가 출력될 공간의 가장 왼쪽 위지점을 함수로 넘겨서 숫자에 따라 달라지는 Seven Segment에 따라 '-'또는 '|'를 출력한다. (이미 공백이 위치한 값을 '-' 또는 '|'로 바꿔주는 것이다.) : 자료형은 char[][] 이다.
    5. char[][] 배열을 출력한다.

    소스를 짜는 시간의 몇배인 4시간 가까이 로직을 차근차근 살펴보기도 하고, 반례를 찾아보려 노력도하고,, 다른사람의 소스를 보고, 실행시켜 비교해봐도 WA인 이유를 모르겠습니다..
    누군가 시원하게 답변해주길 기다립니다.. (( 해결됬습니다 !! ^^ 도움주신 분들 감사합니다.!)

    혹시몰라 코드 첨부 합니다. 하지만 indentation이 않좋아서 보기 않좋으실듯..;;;

    #define SIZE 97
#define CHARH '|'
#define CHARV '-'
#include<iostream>
#include<string>
using namespace std;
/* Seven Segment */
void top(char[][SIZE], int, int, int);
void left_up(char[][SIZE], int, int, int);
void left_down(char[][SIZE], int, int, int);
void right_up(char[][SIZE], int, int, int);
void right_down(char[][SIZE], int, int, int);
void middle(char[][SIZE], int, int, int);
void bottom(char[][SIZE], int, int, int);
int main()
{
    int s, cnt=0;
    string input;

while(cin >> s >> input)
 {
  int i, j, k;
  char number[23][SIZE]={};
  if( s==0 && input.length()==1 && input[0]=='0') break;

  // 숫자 앞의 0제거
  while(input[0]=='0' && input.length()!=1) input.erase(0,1);

  for(i=0; i<input.length(); i++)
  {
   // space로 필요한 공간만큼 채우고
   int tmp = i*(s+3)+s+3;
   if( i==input.length()-1) tmp--;
   for(j=0; j<2*s+3; j++)
   {
    for(k=i*(s+3); k<tmp; k++)
     number[j][k] = ' ';
   }
   // 숫자별로 Seven Segment 적용
   if( input[i]=='0')
   {
    top(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='1')
   {
    right_up(number, 0, i*(s+3), s); 
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='2')
   {
    top(number, 0, i*(s+3), s); 
    right_up(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
   }
   else if( input[i]=='3')
   {
    top(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='4')
   {
    left_up(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='5')
   {
    top(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
   }
   else if( input[i]=='6')
   {
    top(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
   }
   else if( input[i]=='7')
   {
    top(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='8')
   {
    top(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    left_down(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
   else if( input[i]=='9')
   {
    top(number, 0, i*(s+3), s);
    middle(number, 0, i*(s+3), s);
    bottom(number, 0, i*(s+3), s);
    left_up(number, 0, i*(s+3), s);
    right_up(number, 0, i*(s+3), s);
    right_down(number, 0, i*(s+3), s);
   }
  }

  //Output
  if(cnt) cout << endl;
  for(int i=0; i<2*s+3; i++)
  {
   cout << number[i]<<  endl;
  }
  //cout << endl;
  cnt++;
 }
return 0;
} 
void top(char num[][SIZE], int x, int y, int size) // up
{
 for(int i=1; i<1+size; i++) num[x][y+i] = CHARV;
}
void left_up(char num[][SIZE], int x, int y, int size) // left-up
{
 for(int i=1; i<1+size; i++) num[x+i][y] = CHARH;
}
void left_down(char num[][SIZE], int x, int y, int size) // left-down
{
 for(int i=size+2; i<2*size+2; i++) num[x+i][y] = CHARH;
}
void right_up(char num[][SIZE], int x, int y, int size) // right-up
{
 for(int i=1; i<1+size; i++) num[x+i][y+size+1] = CHARH;
}
void right_down(char num[][SIZE], int x, int y, int size) // right-down
{
 for(int i=size+2; i<2*size+2; i++) num[x+i][y+size+1] = CHARH;
}
void middle(char num[][SIZE], int x, int y, int size) // middle
{
 for(int i=1; i<1+size; i++) num[x+size+1][y+i] = CHARV;
}
void bottom(char num[][SIZE], int x, int y, int size) // down
{
 for(int i=1; i<1+size; i++) num[x+2*size+2][y+i] = CHARV;
}

    소스 하일라이팅이 안되네요 ;ㅇ;...;; 어떻게하는지 모르겠습니다 ㅜ [code cpp][/code]로 묶으면 되는거 아니었나요?;;
    꺽쇠로하니까 무언가 Box로 묶이긴 했는데 줄간격도 너무 길고 .. ;ㅇ; ... 죄송합니다 ㅠ


    13년 전
6개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    일단 답변에 벗어난 것이지만 하나 부탁을 드립니다.
    1. 코드는 최대한 간결하게 짜는게 좋지 않을 것 같습니다. LCD display의 경우에는 생각보다 복잡하게 구현이 되어 있는것 같네요.
    2. 소스코드를 올리실 때는 compile이 가능한 코드로 올려주시는게 좋을 것 같습니다. 테스트를 해보려고 소스코드를 긁어봤는데, 이것 저것 덧붙이다 보니 결국 GG를 치게 되네요.

    그리고 programming challenges 사이트의 경우에는 제가 기억하기론 채점이 조금 이상하게 됩니다. 혹시 그 문제일지도 모르겠다는 생각이 드네요. 아마 http://uva.onlinejudge.org 여기에 문제를 가져 온것 같은데, 그 쪽에서 채점을 받아보심이 어떨련지 싶네요.

    UVa 온라인 채점 시스템에서 두 문제의 번호는 다음과 같습니다.
    LCD display : 706
    Graphical editor : 10267


    13년 전 link
  • freedomJ
    freedomJ

    전체코드를 올리지 않은것은 글이 조금이라도 덜 산만해지게 하려고 그런건데 오히려 도움주시는 분들에게 역효과만 났네요 ..;;
    간단하게 짠다고 로직을 만들었는데,, 디버깅하다보니 하나 둘 덕지덕지 붙어서 지저분해진점은 인정합니다 ㅠ..

    uva채점사이트에서도 WA판정이 나는군요 ㅠ 에고..; 전체소스로 수정하겠습니다.

    남의 소스 보는게 정말 쉬운일이 아닌데..; (평소 제 습관은 프로그래밍때 주석을 상세히 달지만 대회용 소스에는 유독 주석이 없네요;;;) 도움 주셨으면 감사합니다.


    13년 전 link
  • helloneo
    helloneo

    UVa 706번

    input:

    1 01

    제가 짠 code의 output은 다음과 같이 나오네요..

     -
    | |   |

    | |   |
     -


    13년 전 link
  • freedomJ
    freedomJ

    helloneo님// 네오님은 AC받으셨죠?... 음;; 그 문제로만은 해결이 안되는것 같아요.
    숫자 앞에 무의미한 0을 제거하는 (예를들어 01은 1로 출력) 코드를 없애고 제출해도 WA가 나오네요.. ;; 찬찬히 한번 더 살펴봐야겠어요..


    13년 전 link
  • helloneo
    helloneo

    10 99999999 을 넣어보세요.. SIZE 가 작은 것 같네요


    13년 전 link
  • freedomJ
    freedomJ

    허허....... 그문제 였군요!!! ㅠㅠ SIZE를 나름 계산한다고 97로 줬었는데 그 계산이 잘못되었네요.. SIZE를 충분히 큰 200으로 주니 Presentation Error가 뜨고, 출력UI(Enter치는시점) 약간 수정하니 AC 받았습니다. helloneo님 감사합니다!!
    정말이지 여기서 도움만 받고 가네요 ^^;;

    그래픽에디터 문제도 약간 조언을 주셨으면 ^^... -글 약간 수정했습니다. -


    13년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.