📌문제
존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다.
이 소들은 자신의 습관대로 매일 똑같은 방법으로 길을 건넌다. 각각의 소는 원형 길의 정해진 한 점을 지나 들어오고, 다른 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이걸 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 총 26마리고, A, B, ... Z라는 이름이 붙는다. 존은 52개의 점을 시계방향으로 보면서 각 점을 어떤 소가 지나가는지 기록했다. 이렇게 만들어 낸 52글자의 문자열에는 각 알파벳이 두 번씩 나타날 것이다.
어떤 두 소는 어떤 방법으로 걷든 그 경로가 어딘가에서 만나야 될 수도 있다. 그런 소가 총 몇 쌍인지 구해 보자.
입력
첫 줄에 52글자의 문자열이 주어진다. 각 글자는 알파벳 대문자이며, 각 알파벳이 정확히 두 번씩 나타난다.
출력
경로가 무조건 만나는 소가 몇 쌍인지 출력한다.
예제 입력
ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ예제 출력
1💡Idea
아래 사진과 같이 지나 들어오는 점과 지나 나가는 점이 서로 엇갈리는 소🐄들을 찾아주면 됩니다.
💻코드
- ⏰ 시간 : 72 ms / 메모리 : 30840 KB
import sys
cows = sys.stdin.readline().strip()
answer = [] # 경로가 만나는 소들의 쌍 리스트
dic = {chr(i): [-1, -1] for i in range(65, 91)} # 각 소들이 나타나는 인덱스를 기록
for i, c in enumerate(cows):
if dic[c][0] == -1: # 소가 처음 나타난 경우
dic[c][0] = i
else: # 소가 두 번째 나타난 경우
dic[c][1] = i
for i in range(52):
for j in range(i+1, 52): # i번째 소와 j번째 소의 인덱스가 서로 엇갈리는지 확인
if dic[cows[i]][0] < dic[cows[j]][0] < dic[cows[i]][1] < dic[cows[j]][1] or dic[cows[i]][0] > dic[cows[j]][0] > dic[cows[i]][1] > dic[cows[j]][1]:
if cows[i] != cows[j] and set([cows[i], cows[j]]) not in answer:
answer.append(set([cows[i], cows[j]])) # 경로가 만나고, 이미 찾은 답이 아니라면 추가
print(len(answer))
📝코드 설명
사실 분명 더 좋은 코드가 있을 것 같아 고민 중인데, 우선은 문제에서 찾아야 하는 바를 그대로 구현해보았습니다😥
dic은 소 : [첫 번째 지나가는 점, 두 번째 지나가는 점] 으로 구성된 딕셔너리입니다.
숫자를 문자로 바꾸어주는 chr를 사용하여 A부터 Z까지의 소들을 만들어주었습니다
그리고, 입력받은 52글자의 문자열인 cows를 다시 하나씩 읽으면서, 어느 소의 경로가 다음에 나오는 소들의 경로와 겹치는지를 dic의 값을 통해서 확인해줍니다.
만약 경로가 겹치고, 이미 찾은 정답이 아니라면 set의 형태로 묶어서 answer에 넣어줍니다.
최종적으로 answer의 길이를 출력하면 됩니다.
