정보올림피아드 초등 - 지역예선] 2009년도 33-35번문제

 

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. (1) 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. (2) 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. (3) X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 주어진 괄호열을 읽어, 그것이 올바른 괄호열인지를 출력하는 프로그램을 작성하시오. 입력 형식 입력 파일의 이름은 INPUT.TXT로 한다. 첫 째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단, 그 길이는 1 이상, 30 이하이다. 출력 형식 출력 파일의 이름은 OUTPUT.TXT로 한다. 입력이 올바른 괄호열이면 1을, 그렇지 않으면 0을 출력한다. 입력과 출력의 예 입력(INPUT.TXT)     (()[[]])([]) 출력(OUTPUT.TXT)   1  프로그램   33. ㉠에 들어갈 내용은 무엇인가? ①p[i] = data[cnt]; ②p[i] = data[i]; ③p[cnt] = p[cnt - 1]; ④p[cnt] = data[cnt]; ⑤p[cnt] = data[i];   34. ㉡에 들어갈 내용은 무엇인가? ①cnt < 0 ②cnt <= 0 ③cnt == 0 ④cnt >= 0 ⑤cnt > 0   35. 다음 중 위 프로그램의 입력으로 주어졌을 때 ㉢의 문장이 실행되는 것은? ①((())) ②(([))) ③([[]]] ④[((())) ⑤(([]))]

문제풀이)

위의 문제의 알고리즘을 살펴 보면

데이터를 data 배열에 입력을 받은 후

데이터 길이 만큼 루프를 돌면서 쌍이 맞는지를 비교 한다.

만약 현재의 위치의 데이터가 '(' 또는 '[' 이라면 p 의 배열에 현재의 데이터를 추가 한다.

만약 ')' 또는 ']' 이라면 p 의 마지막 데이터가 쌍이 맞는지 확인 한다.

따라서 ㉠ 의 위치는 p[cnt] = data[i]; 가 되어야 하며

㉡ 의 위치는 cnt < 0 인 경우로 p에 데이터가 없는 경우이므로 while 문을 빠져 나간다.

㉢ 의 위치가 실행 되려면 cnt 가 0 보다 커야 하므로 cnt 가 0보다 큰 경우는  

뒷부분이 쌍이 모두 맞으면서 '(' 또는 '['  이 더 많은 경우에 해당 한다.

정답)

33번) 5번

34번) 1번

35번) 4번