고1때 만든 프로그램 다시 보기 #1

미국에서 PAP/AP Computer Science를 수강하면서 수업내에서도 많은 프로그램을 만들었지만 대학교에서 주최하는 수 많은 코딩 경기들을 참가하면서도 참 많은 프로그램들을 만들었었다(사실 프로그램이라기보다 스크립트에 가깝다). 그중에서 아직도 기억에 남는 몇몇 코드들을 다시 분석해 보려한다.

#1 겹치는 넓이 구하기

You are given two sets of coordinates that represents each rectangle, brackets around each coordinate separated by a comma and each set will be separated by a space. Return the overlapping area of the two rectangles. + coordinates will be less than 10 and the second coordinate will always be higher or at the same level as the first coordinate

간단히 말하자면 참가자들은 2개의 세트의 두 좌표를 받게 된다(예를 들어 (1,3)(3,4)  (2,4)(5,5)). 두 좌표씩 각각 사각형을 표현하는 것이고 이 두 사각형이 겹치는 넓이를 구하면 된다.

사실 이 문제를 University of Texas at Dallas Coding Competition 처음 접했을땐 코딩을 배운지 한달도 안된 '뉴비'였다(이제 막 1d array를 배우고 있었다). 그래서 결국 이 문제를 포함해서 다른 9문제 정도를 보기만 하다가 나왔다. 집에 돌아와서 이 문제를 회상하다가 '유레카'를 외치는 순간을 경험할 수 있었다. Array를 가로 세로로 겹쳐서(2d array) 그래프 비슷하게 만든 후 for loop을 사용해 숫자만 집어넣으면 되는 거였다.

Scanner console = new Scanner(System.in)

int[][] graph = new int[10][10];

//여기서 graph 라는 2d array가 int의 기본값인 0으로 10X10 으로 만들어진다

String initial = console.nextLine();

//모든 좌표를 다 받는다

String[] coordinates = str.split(" ");

//(x1,y1)(x2,y2) 꼴로 두개를 생성

        for(int k=0; k<2; k++)

        {

      //두번 실행

            int x1 = Integer.parseInt(coordinates[k].substring(1,2));

            int y1 = Integer.parseInt(coordinates[k].substring(3,4));

            int x2 = Integer.parseInt(coordinates[k].substring(6,7));

            int y2 = Integer.parseInt(coordinates[k].substring(8,9));

            for(int i = x1; i < x2; i++) {

                for(int j = y1; j < y2; j++)

                {

                    graph[i][j]+=1;

   //사각형을 1로 표현

                }

            }

        }

  결국 사각형이 겹치면 array의 값이 2가 된다

        int counter = 0;

        for(int i = 0; i<10; i++)

        {

            for(int j = 0; j<10; j++)

            {

                if(graph[i][j]==2)

                {

                    counter++;

                }

            }

        }

        System.out.println(counter);

자 이제 데이터가 (0,0)(7,7) (1,3)(5,6) 일때를 보자

처음 graph[][]의 Default Condition이다 

첫번째 사각형을 1로 표현한 모습

두번째 사각형을 프로세싱한후 겹치는 부분이 2로 나온다

결국 마지막에 리턴하는 값은 12이다.

물론 경기용 코딩이기 때문에 몇가지 보완점이 필요하긴하다 예를 들어 더 간결하게 코딩을 하려면 min이나 max를 썻을수도 있을것이다. 하지만 경기의 목적이 빠른 시간 안에 문제를 많이 맞추는 것이므로 테스팅 데이터를 올바르게 리턴만 하면 되기때문에 간결함&정확성에는 노력을 기울이지는 않았다.