어렵게 생각해서 막혔던 문제


문제를 너무 어렵게 꼬아서 해답을 찾으려고 하면 오히려 늪에 빠져서 답이 보이지 않고 재미가 없어지면서 자심감도 뚝뚝 떨어지는 문제들이 있다.

지금 실력에서 이런 문제들을 겪었다고 하기에는 부끄러운 문제이지만 1032번 문제가 나에게는 그랬다.

제대로 파이썬을 접하고 공부하기 시작한지 이제 2~3주차가 되어가는 것 같은데 아직도 이런 문제에서 해맨다는 사실이 좀 서글프긴 하다.

 

아무튼, 현재 문제를 너무 꼬아서 생각해버리는 바람에 완전히 막혔던 문제이다.

내가 하려던 방법의 코드를 먼저 적고 시작하겠다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
= int(input())  # 파일 이름의 갯수
string = [0]*N  # string을 input으로 받기 때문에(그리고 input은 문자열을 한 줄로 받는다.) *N이 필요하다.
 
# 단어를 입력한다.
for i in range(N):
    string[i] = input()
    # print(string)
 
# 단어들에서 같은 부분 찾기
same = list()
cnt_one = 0
for i in string[0]:  # 기준이 되는 string을 첫 번재 입력 string으로 하도록 한다.
    # print(i)
    for j in string[cnt_one+1]:
        if i == j:
            same.append(i)
        else:
            break
    same.append('?')
 
cnt_two = 1
= 0
for i in same:
    for j in string[cnt_two+1]:
        if i == j:
            same[n].append(i)
            n += 1
 
cs

참고로 당연히 오류 가득하고 실행도 안되면서 복잡하기만 한 미완성의 코드이다.

이걸 올리는 이유는 추후에 내가 이 문제를 다시 보게 되었을 때, 내가 얼마나 복잡하게 문제들을 접근하려고 했는지 정리하기 위함이다.

 

위의 코드에서 내가 노렸던 것은 배열을 사용하는 것이다(결국 주력언어인 C에서 벗어나지 못한 나의 보습이 보인다. 파이썬에서는 배열이라기보다는 "list"이기 때문...)

배열을 통해서 첫 번째 입력했던 단어와 다음 단어를 비교해서 같으면 same이라는 배열에 넣고, 그렇지 않으면 ?로 채우고자 하였다.

그 다음에 하고 자 한 것은 line 23에서부터이다. same에서 만들어진 것을 이제 그 다음 단어와 비교를 하는 것이다. 그리고 그것을 다시 same에 똑같이 대입하는 형태...

아무튼 망했다.

 


 

깔끔하게 정확하게(?) 문제를 해결한 코드는 다음과 같다:

1
2
3
4
5
6
7
8
9
10
= int(input())
pivot_word = list(input())
pivot_word = len(pivot_word)
for i in range(N - 1):
    other_words = list(input())
    for j in range(pivot_word):
        if pivot_word[j] != other_words[j]:
            pivot_word[j] = '?'
print(''.join(pivot_word))
 
cs

 

사실 이 코드 또한 스스로 해내었다기보다는 다른 분들이 해낸 것을 토대로 공부를 통해 도출한 코드나 다름없다.

그런데 보면 아이디어는 굉장히 간단하다.

나의 경우, 새로운 배열을 생성해서 거기에 넣으려고 한데에 반해, 위의 코드는 pivot_word인 첫번째로 입력한 리스트변수에 바로 처리를 하는 것이다.

 

암튼 반성해야 할 점은 명확하다.

문제가 해결이 되지 않을 때 조금 더 다른 방법을 생각해보려는 노력이 필요하다.

결국 논리력을 기를 필요가 있다... 

 

 

문제출처: https://www.acmicpc.net/problem/1032

 

1032번: 명령 프롬프트

첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은

www.acmicpc.net


제목에 써있는 그대로 조금 햇갈렸던 문제이다.

문제를 푸는데 있어서 이 문제야말로 구현이 어려운 것이 아니라 규칙을 찾는 컴퓨팅적 사고 및 논리력이 필요한 문제가 아닌가 싶다.

즉, 문제를 제대로 이해하고 반례까지 없도록 잘 만드는 것이 관건이다.

나는 일부만 제대로 하고, 반례가 생기도록 처음에 만들어서 고생했다.

 

나의 첫 시도(잘못된 코드)는 다음과 같다:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 틀렸다고 나오는 코드
# 1 1 1  ==>  답 101  ==>  출력 102
= int(input())
for i in range(a):  # 몇 개의 출력물을 원하는가
    H, W, N = map(int, input().split())  #입력
    hundred = int(N % H)  #몇 층인지 찾기(백의 자리수 시작)
    decimal = int(N // H) + 1  #몇 호인지 찾기(일의 자리수 시작)
    if (hundred == 0):  # 예를 들어, N층인데 나머지가 0이면, N을 출력한다.
        hundred = H
        if(len(str(decimal)) == 1):  # 일의 자리수 시작해서 십의자리까지 넘어가지 않으면(==> 1~9이면)
            print(f"{hundred}0{decimal}")  # 0을 십의 자리수에 출력한다.
        else:
            print(f"{hundred}{decimal}")  # 십의자리수까지 출력한다.
    else:
        if(len(str(decimal)) == 1):
            print(f"{hundred}0{decimal}")
        else:
            print(f"{hundred}{decimal}")
 
cs

이 코드의 반례는 1 1 1이다. 101이라는 숫자가 나와야 하는데 decimal = int(N//H)+1을 해버렸기 때문에 틀려버렸다.

추가적으로, if~else문을 통해서 print문을 복잡하게 짠 것도 가독성이 떨어지며 속도에도 별로 좋지 않다.


고민을 하고 인터넷을 검색한 결과 다음과 같은 코드가 깔끔하다는 것을 깨닫게 되었다.

1
2
3
4
5
6
7
8
9
10
11
12
= int(input())
for i in range(a):
    H, W, N = map(int, input().split())
    hundred = N % H
    if (hundred == 0):
        hundred = H * 100
        decimal = N // H
    else:
        hundred = (N % H) * 100
        decimal = N // H + 1
    print(hundred + decimal)
 
cs

딱 봐도 깔끔하다. 특히, 내가 위에서 틀린 부분이 확연히 보인다.

decimal이라고 되어있는 부분은 hundred변수가 0일 때와 아닐 때에 따라서 다르게 처리가 되도록 해야한다.

 

이 문제의 경우, 구현의 문제나 파이썬이라는 공부에 있어서의 문제라기보다 논리적 해결의 차원에 문제로 분석할 수 있다 (물론 매우 간단한 문제이지만...).

이런 형태의 문제가 있음을 인지하고, 끊임없이 컴퓨팅적 사고를 기를 필요성을 다시 한 번 느끼게 된다.

 

 

문제출처: https://www.acmicpc.net/problem/10250

 

10250번: ACM 호텔

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수

www.acmicpc.net

+ Recent posts