본문 바로가기
카테고리 없음

[알쓰] 백준 1475 : 방번호

돼화 2024. 10. 13. 18:11
안녕하세요 이번주도 알쓰를 작성하려고 돌아왔습니다. 개인적으로 알고리즘 문제를 풀면서 저만의 법칙을 정했는데요. 방법은 이렇습니다.

1. 굿노트에 문제를 정의하고 필요한 변수를 생각해서 psuedo code를 작성한다.
2. 노션에 생각한 내용을 정리한다.
3. 구현해본다
4. 해결과정을 모두 노션에 기록한다.

이렇게 해두면 에러가 났을때 생각의 방향을 최대한 바른쪽으로 향하게 할 수 있는것 같습니다. 다시한번 기록의 중요성을 느끼면서 제 4시간을 앗아간 백준 1475번 문제를 보겠습니다.

백준 1475 : 방번호

 

문제

접근법

문제를 읽으면 드는 생각 3가지 

 

1. 은진이는 필요없고

2. 숫자 한개가 아닌 0~9까지 한세트

3. 6과 9를 잘 처리 해야겠구나

입니다.

 

  1. 1차정리
    • 0~9가 각각 방번호에 몇개가 들어있는지 개수를 기록을 해놔야 되겠구나
    • 0 : ?, 1: ? ~ 9: ? // dictionary 자료형을 이용하자
    • dictionary안에 for문을 이용해 0~9까지의 key값을 대입
    • 입력된 문자 N을 읽으면서 key에 맞는 value를 입력해주고 6과 9의 중복만 잘 처리해보자
  2. 2차 정리
더보기
6과 9를 어떻게 계산하지?

  • 12369 → 1세트 필요
  • 12969 → 2세트 필요
  • 112969 → 2세트 필요 1: 2 6 : 1 9 : 2 흠…
  • 9가 3이면 총 숫자조합이 999 666 669 699 모두 같은거지
  • 처음에는 6을 입력받을때 if문이용해서 9가 key값인곳에 value를 +1 해줘서 처리하려고 생각함
  • 근데 이렇게 하면 딕셔너리에서 최댓값을 뽑을때
    • 9가 5개인 경우
    • 99999면 필요한 세트는 3개지만 답은 5가 나와버림;;
    • 근데 66999면 6: 2 9: 3으로 3세트가 나와서 정답이긴함
    • 뭔가 알것같음 차이가 0이나 1이면? 아니야 아니야 하면서
    • 뭔가 단순한 방법이 없을까 하다가 아래 해답발견
  • 일단 딕셔너리를 완성하고 6과 9의 개수를 합쳐버리는 것
  • 6과 9의 개수를 합친 개수가
    • 5,6인경우 3세트
    • 3, 4인경우 2세트
    • 1, 2인경우 1세트
    • 0인경우 0세트
    • 아 그러면 합친개수를 나눠서 반올림 한뒤에 다른 딕셔너리의 최댓값이랑 비교하면 되겠구나!!!!!
  • 5,6 3세트 vs 1이 3세트 아무거나 출력

이렇게 생각하고 해당 내용을 구현했지만...

폐기물

import math
# 방 번호 입력

N = input()

#### 방번호를 dic에 삽입 ####

dic = {str(i) : 0 for i in range(10)}

for i in N:
    if i in dic:
        dic[i] +=1
    else:
        dic[i] = 1
        
print(dic.items())

#### 6과 9를 처리하는 logic ####
sum = dic['6'] + dic['9']

if(sum <= max(dic.values()) and max(dic.values()) != dic['6'] and max(dic.values()) != dic['9']):
    print(max(dic.values()))
elif((sum % 2) == 0):
    print(int(sum/2))
else:
    print(int(math.ceil(sum/2)))
#나눗셈 연산시 float형이니까 정수형으로 나와야 되면 int로 변환해주기

# print(max(dic.values()))
# print(int(sum/2))
# print(int(math.ceil(sum/2)))

하나를 고치면 하나가 안되고 어떻게 수정하던지 반례가 나타나버리는 폭탄같은 코드를 만들어버렸습니다. 모든 반례를 찾아가며 이 코드 수정하는데에서 3시간을 할애. 

이제 그만하자 gpt 써보자 하다가 마지막으로 수정한게 이코드인데

답은 2

악에 받쳐서 그냥 해결안하고 나갔습니다. 그래서 친구한테 반례좀 찾아달라고 부탁했는데 친구가 이런말은 했습니다.

 

너무 복잡해~

정답코드

약속이 끝나고 돌아와서 앉아서 내가 너무 복잡하게 생각하고 있나?라고 생각했고 어디까지가 잘됐고 어디부터가 문제인지를 다시한번 짚어봤습니다.

 

결국 문제의 핵심은 '6과 9의 처리'

 

6과 9 vs 나머지 숫자들.

 

처음부터 코드를 다시 작성했고

그래서 정말 단순하게 해결법을 찾았습니다.

import math
# 방 번호 입력

N = input()

#### 방번호를 dic에 삽입 ####

dic = {str(i) : 0 for i in range(10)}

for i in N:
    if i in dic:
        dic[i] +=1
    else:
        dic[i] = 1
        
# print(dic.items())

#### 6과 9를 처리하는 logic ####
six = dic.get('6')
nine = dic.get('9')
sum = six + nine
del dic['6']
del dic['9'] #아예 6과 9를 빼서 처리해버리기, 진작에 이렇게 할걸

if(sum <= max(dic.values())):
    print(max(dic.values()))
elif(sum % 2 == 0 ):
    print(int(sum / 2))
else:
    print(int(math.ceil(sum/2)))

# print(dic.items(), six, nine)

#나눗셈 연산시 float형이니까 정수형으로 나와야 되면 int로 변환해주기

# print(max(dic.values()))
# print(int(sum/2))
# print(int(math.ceil(sum/2)))
  1. 6과 9를 dic에서 빼주고
  2. 조건문을 최대한 간결하게 가져가서
  3. 오류발생가능성을 최대한 줄여주는 것

짠

비교코드

import math
#방번호 입력
N = input()

#print(N)

#문자열 0부터 9까지 key값으로 갖는 dic 생성
dic = {str(i) : 0 for i in range(10)}
#dic 안에 방번호와 맞는 value값 입력
for num in N:
    dic[num] += 1

a = math.ceil((dic['6'] + dic['9']) / 2);
dic['6'] = a;
dic['9'] = a;

max_number = max(dic.values())
print(max_number)

이건 복잡해라고 말한 친구가 정답코드 작성후 저한테 보여준 코드입니다. code가 참 clean하네요. 

 

배운점

문제를 너무 붙잡고 있으면 가끔 생각의 경계에 갖혀서 못나올때가 있는 것 같습니다.
몰입해서 문제를 푸는 건 중요하지만 항상 열어서 생각을 하고 다른 방향으로 뻗어나가는 용기도 중요하다고 느끼면서 오늘 블로그 포스팅을 마치겠습니다~

 

잘 되면 실력이 확장되고
안 되면 실력이 확정된다
- 생활코딩 -

 

티스토리툴바