7주차 복습 문제 해설

www.acmicpc.net/group/practice/9883/18

2차원 리스트가 중요해서 2차원 리스트 3문제를 추가하였습니다. 문제는 6번이 제일 어려웠을 것이라고 생각합니다.

 

 

 

1. BOJ 12778 CTP 공국으로 이민 가자

www.acmicpc.net/problem/12778

12778번: CTP공국으로 이민 가자

 

문제를 읽어보니 1을 입력 받으면 A를 출력하고, A를 입력 받으면 1을 출력하는 아스키 코드 변환 문제입니다.

1을 입력 받아서 A를 출력하려면 chr(1 + 64)를 해주면 되는 것이고, A를 입력 받으면 1을 출력하는 방법은 ord('A') - 64를 출력하면 되겠습니다.

 

t = int(input())
for i in range(t):
    m, n = input().split()
    if n == 'C':
        arr = input().split()
        for j in range(len(arr)):
            arr[j] = ord(arr[j]) - 64
    else:
        arr = list(map(int,input().split()))
        for j in range(len(arr)):
            arr[j] = chr(arr[j] + 64)
    print(' '.join(map(str,arr)))

 

저는 arr 리스트를 재사용해서 arr 리스트에서 값을 바꾸고 출력을 했습니다.

 

 

 

2. BOJ 2204 도비의 난독증 테스트

www.acmicpc.net/problem/2204

2204번: 도비의 난독증 테스트

대소문자가 섞인 문자열이 여러개가 들어오는데, 대소문자를 구분하지 않고 사전순으로 정렬하여 가장 앞서는 단어를 출력하라고 합니다. 입력값은 대소문자 구분을 하지 않았을 때 똑같은 단어는 주어지지 않는다고 합니다.

 

우리는 대소문자가 섞인 문자열이 들어오는데, 대소문자를 구분하지 않는다는 것은 문자열을 전부 소문자, 대문자로 변환하여 정렬한다는 뜻입니다.

 

그래서 정렬 조건을 lower()나 upper() 메소드를 사용하여 정렬을 해주면 됩니다.

 

 

일단 입력값을 받는 코드를 짜보면 0을 입력 받으면 코드가 끝나는 while문이고, arr배열에 값들을 넣어주면 됩니다.

while 1:
    t = int(input())
    if t == 0: break
    ans = []
    for i in range(t):
        ans.append(input())

 

4 ~ 6 줄은 이렇게 한 줄로 만들 수 있습니다.

while 1:
    t = int(input())
    if t == 0: break
    arr = [input() for i in range(t)]

 

그리고 이제 정렬을 해주면 되는데, 정렬 조건은 lower()나 upper() 메소드를 사용해서 대소문자 관계 없이 정렬을 해주고 첫 번째 값을 출력해주면 됩니다.

while 1:
    t = int(input())
    if t == 0: break
    arr = [input() for i in range(t)]
    arr.sort(key=lambda a:a.lower())
    print(arr[0])

while 1:
    t = int(input())
    if t == 0: break
    arr = sorted([input() for i in range(t)], key=lambda a:a.lower())
    print(arr[0])

 

 

3. BOJ 1436 영화감독 숌

www.acmicpc.net/problem/1436

1436번: 영화감독 숌

666이 들어간 영화중 N번째 영화를 출력하라고 합니다.

 

N의 최대값은 10000이므로 6660000 ~ 6669999 범위에 있는 수만 해도 10000개이고, 1부터 6669999까지 돌리면 문제 조건에 부합하는 수는 10000개가 넘어가기 때문에 대충 6669999번 for문을 돌려서 N번째 수를 찾으면 됩니다.

n = int(input())
ans = []
for i in range(6669999):
    blah blah

666이 들어있는지 확인하는 방법은 숫자를 str형으로 바꾸고 멤버 연산자를 사용하면 됩니다.

 

n = int(input())
ans = []
for i in range(6669999):
    if '666' in str(i): ans.append(i)
    if len(ans) == n: break
print(ans[-1])

 

 

 

 

 

4. BOJ 1895 필터

www.acmicpc.net/problem/1895

1895번: 필터

r*c 배열을 3*3배열로 훑으면서 중앙값을 배열 J에 저장하고, 배열 J에 있는 값중에 t이상의 값이 몇 개 있는지 출력하는 문제입니다.

 

일단 입력값을 받는 코드를 짜봅시다.

r, c = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(r))
t = int(input())
ans = 0

 

r*c 배열을 3*3 배열로 훑어야하므로 for i in range(start, end)에서 end의 값은 r-2, c-2가 됩니다.

r, c = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(r))
t = int(input())
ans = 0

for i in range(0,r-2):
    for j in range(0,c-2):
        blah blah

 

그리고 이제 3*3 배열을 확인하면 됩니다.

현재 위치가 (i, j)이면 (i, j)부터 (i+2, j+2)까지 확인해야 하므로 for문을 start = i, end = i+3, start = j, end = j + 3으로 설정해줍니다.

r, c = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(r))
t = int(input())
ans = 0

for i in range(0,r-2):
    for j in range(0,c-2):
        for x in range(i, i+3):
            for y in range(j, j+3):
                blah blah

 

이제 중앙값을 찾아야하므로 val이라는 리스트를 하나를 만들어서 arr[x][y]의 값을 저장합니다.

 

r, c = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(r))
t = int(input())
ans = 0

for i in range(0,r-2):
    for j in range(0,c-2):
        val = []
        for x in range(i, i+3):
            for y in range(j, j+3):
                val.append(arr[x][y])

그리고 val을 정렬하여 가운데 값을 뽑아주면 됩니다. 인덱스가 0, 1, 2, 3, 4, 5, 6, 7, 8이므로 가운데 인덱스는 4가 됩니다.

 

val[4]가 t 값 이상인지 확인해보고, t보다 크거나 같으면 ans에 1을 더해준다음 마지막 줄에 ans를 출력해주면 됩니다.

 

r, c = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(r))
t = int(input())
ans = 0

for i in range(0,r-2):
    for j in range(0,c-2):
        val = []
        for x in range(i, i+3):
            for y in range(j, j+3):
                val.append(arr[x][y])
        val.sort()
        if val[4] >= t: ans += 1
print(ans)

 

r, c = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(r))
t = int(input())
ans = 0

for i in range(0,r-2):
    for j in range(0,c-2):
        val = []
        for x in range(i, i+3):
            for y in range(j, j+3):
                val.append(arr[x][y])
        if sorted(val)[4] >= t: ans += 1
print(ans)

 

8 ~ 11줄은 아래와 같이 한 줄로 표현할 수 있습니다.

r, c = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(r))
t = int(input())
ans = 0

for i in range(0,r-2):
    for j in range(0,c-2):
        val = sorted([arr[x][y] for y in range(j, j+3) for x in range(i, i+3)])
        if val[4] >= t: ans += 1
print(ans)

 

 

 

 

5. BOJ 2799 블라인드

www.acmicpc.net/problem/2799

2799번: 블라인드

5가지 상태가 각각 몇 번 나오는지 출력하는 문제입니다.

 

블라인드 상태를 구하는 방법은 아래 그림과 같이 각 창문마다 세로로 한 줄만 확인하면 됩니다.

입력값을 받고, 답을 출력할 ans 리스트를 만들어줍니다.

n, m = map(int,input().split())
arr = list(input() for _ in range(5*n+1))
ans = [0] * 5

여기서 이제 빨간 사각형만 확인하면 됩니다.

각 사각형의 맨 위 좌표만 확인하면 행은 5칸 차이, 열도 5칸 차이가 나는 것을 알 수 있습니다. 시작 좌표는 (1, 1)입니다.

그래서 2중 for문을 (1,1)부터 시작해서 end는 각각 5*n+1, 5*m+1로 설정하고 step을 전부 5씩 설정하면 됩니다.

n, m = map(int,input().split())
arr = list(input() for _ in range(5*n+1))
ans = [0]*5

for i in range(1,5*n+1,5):
    for j in range(1,5*m+1,5):
        blah blah

여기서 for문을 한번 더 사용하여 사각형을 확인하면 됩니다. 블라인드 상태를 저장하는 방법은 *의 개수를 저장하면 됩니다. *이 하나도 없으면 ans[0]이고, *이 4개면 ans[4]이니까요.

 

n, m = map(int,input().split())
arr = list(input() for _ in range(5*n+1))
ans = [0]*5

for i in range(1,5*n+1,5):
    for j in range(1,5*m+1,5):
        x = 0
        for k in range(4):
            if arr[i+k][j] == '*': x += 1
        ans[x] += 1

이제 ans를 출력하면 됩니다.

n, m = map(int,input().split())
arr = list(input() for _ in range(5*n+1))
ans = [0]*5

for i in range(1,5*n+1,5):
    for j in range(1,5*m+1,5):
        x = 0
        for k in range(4):
            if arr[i+k][j] == '*': x += 1
        ans[x] += 1
print(' '.join(map(str,ans)))

 

 

 

 

 

6.  BOJ 1051 숫자 정사각형

www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

4개의 꼭지점이 전부 같은 값인 정사각형중에서 넓이가 제일 큰 정사각형을 구하라고 합니다.

예제 입력 값을 보면 알듯이 띄어쓰기가 되어 있지 않아서 0 ~ 9 까지의 수만 사용하여 정사각형을 만들 수 있는 것을 알 수 있습니다.

정사각형의 한 변의 길이는 N, M중에서 작은 값이 최대 정사각형의 크기가 됩니다.

그래서 정사각형의 크기는 1부터 min(N, M)의 제곱이 되겠습니다.

 

이 문제는 3중 for문으로 해결할 수 있습니다.

첫 번째 for문은 정사각형 한 변의 길이인 1 ~ min(N, M)을 확인할 수 있게 합니다.

두 번째와 세 번째 for문은 해당 길이만큼 2차원 배열을 돌릴 수 있는 부분까지 돌려주면 됩니다.

 

이것을 코드로 옮기면 아래와 같습니다.

n, m = map(int,input().split())
arr = list(input() for _ in range(n))
ans = 0

for i in range(min(n,m)):
    for x in range(n - i):
        for y in range(m - i):
            blah blah

5번째 줄의 for문의 범위가 왜 그러냐면 문제 본문에서는 꼭지점이라고 하지만 그림을 그려보면 정확히는 꼭지점을 구하는 것이 아니기 때문입니다.

 

그리고 이제 꼭지점 좌표의 값이 서로 같으면 ans의 값을 업데이트 해주면 됩니다.

n, m = map(int,input().split())
arr = list(input() for _ in range(n))
ans = 0

for i in range(min(n,m)):
    for x in range(n - i):
        for y in range(m - i):
            if arr[x][y] == arr[x+i][y] == arr[x][y+i] == arr[x+i][y+i]:
                ans = (i+1)**2
print(ans)